حل مسئله زمانبندی پروژه با هدف کمینه سازی زمان اتمام پروژه با محدودیت منابع با الگوریتم فراابتکاری قورباغه
محورهای موضوعی :
مدیریت صنعتی
Alireza Haji Akhondi
1
,
Gholam Reza Tavakoli
2
,
Peyman Akhavan
3
,
Manouchehr Manteghi
4
1 - PhD student, Department of Industrial Engineering, Malek Ashtar University, Tehran, Iran
2 - Assistant Professor, Malek Ashtar University, Tehran, Iran
3 - Associate Professor, Malek Ashtar University, Tehran, Iran
4 - Associate Professor, Malek Ashtar University, Tehran, Iran
تاریخ دریافت : 1396/02/11
تاریخ پذیرش : 1396/07/25
تاریخ انتشار : 1396/10/03
کلید واژه:
Project Scheduling,
SFLA,
Meta-heuristic Algorithm,
زمانبندی پروژه,
RCPSP,
الگوریتم فراابتکاری,
چکیده مقاله :
الگوریتم جهش ترکیبی قورباغه (SFLA) یک الگوریتم مبتنی بر ممتیک متاهیوریستیکِ است. این الگوریتم در سالهای اخیر توسط Eusuff و Lansey ایجاد شد. الگوریتم SFLA از نحوه‌ی جستجوی غذای گروه‌های قورباغه سرچشمه می‌گیرد. این الگوریتم برای جستجوی محلی میان زیرگروه‌های قورباغه از روش نمو ممتیک استفاده می‌کند. SFLA از استراتژی ترکیب استفاده می‌کند و امکان مبادله پیام در جستجوی محلی را فراهم می‌سازد. الگوریتم جهش ترکیبی قورباغه مزایای الگوریتم نمو ممتیک و بهینه‌سازی گروه ذرات (PSO) را ترکیب می‌کند. یکی از مسائل مشهور در زمینه کنترل پروژه، زمانبندی پروژه با محدودیت منابع و سایر محدودیتها می باشد که زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسائل دارای پیشینه تحقیقاتی غنی است. مساله زمانبندی پروژه با منابع محدود در واقع کلی ترین مساله زمانبندی است. مسائل زمانبندی کارگاهی، جریان کارگاهی ، زمانبندی و سایر مسائل زمانبندی همگی زیر مجموعه ای از این مسئله به حساب می آیند. زمانبندی پروژه یکی از وظایف اصلی و فعالیت‌های اصلی در مدیریت پروژه است. وجود محدودیت منابع و همچنین روابط پیش نیازی بین فعالیت‌ها مسئله زمانبندی پروژه را امری دشوار می‌سازد. زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسائل با ادبیات غنی در حوزه مسائل تحقیق در عملیات است.این مسئله توجه محققان را در سالهای اخیر بشدت بخود جلب کرده است و تاکنون با الگوریتم های مختلف حل شده است. در این مقاله به بررسی و عملکرد الگوریتم جهش قورباغه (SFLA) در حل مسائل زمانبندی پروژه با محدودیت منابع پایه پرداخته می شود که نتایج حاکی از عملکرد مناسب و قوی این الگوریتم فراابتکاری جدید می باشد.
چکیده انگلیسی:
Frog leaping algorithm combination (SFLA) is an algorithm based on memetic Meta-heuristic. Created in recent years by Eusuff and Lansey, SFLA algorithm works in a way that the frog groups search for food. The development of memetic algorithms for local search method is similar to the activities of a frog among subgroups. SFLA uses a combination of strategy and provides the ability to exchange messages in local search. Frog leaping algorithm combines the advantages of particle swarm optimization algorithm and memetic development (PSO). Since the resource-constrained project scheduling problem is the timing issue, scheduling issues in the construction sites and plants is highly considered. One of the main duties of the project scheduling and project management is to reduce the completion time. Because of the resource constraints and precedence relationships between activities, project scheduling problem is difficult. In this paper, the algorithm performance LeapFrog (SFLA) is applied to reduce the project scheduling problems with resource constraints. The findings prove the robust performance of the new meta-heuristic algorithm.
منابع و مأخذ:
Demeulemeester W S., Herrolen W S.(2002). Project Scheduling. Kluwer Academic Publishers.
Brucker P. Drexl A. Mohring R. Neumann K. Pesch E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112, 3–41.
Sprecher A. (1997). Exact algorithm for RCPSP in multi-mode case. OR Spectrum, 19(3), 95-203.
Buddhakulsomsiria J., Kim D.S. (2006). Properties of multi-mode resource constrained project scheduling problems with resource vacations and activity splitting, European Journal of Operational Research, 175, 279–295.
Buddhakulsomsiria J. Kim D.S. (2007).Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. European Journal of Operational Research, 178,374–390.
Schultmann F. Rentz O. (2001). Environment-oriented project scheduling for the dismantling of buildings. OR Spectrum, 23(1), 51–78.
Demeulemeester E.L. de Reyck B. Herroelen W.S.(2000). The discrete time/resource trade-off problem in project networks – A branch-and-bound approach. IIE Transactions, 32,1059–1069.
Ranjbar M. Kianfar F. (2007). Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms. Applied Mathematics and Computation, 191, 451–456.
Ranjbar M. de Reyck B. Kianfar F. (2009). A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. European Journal of Operational Research, 193, 35–48.
Akkan C., Drexl A., Kimms A., (2005). Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, European Journal of Operational Research, 165, 339–358.
Maniezzo V. Mingozzi A.(1999). The project scheduling problem with irregular starting time costs. Operations Research Letters, 25(4), 175–182.
Mohring R.H. Schulz A.S. Stork F. Uetz M. (2001). On project scheduling with irregular starting time costs. Operations Research Letters, 28 (4): 149–154.
Wang Qiusheng, Autom. Sci. & Electr. Eng., Beihang Univ., Beijing. (2013). China Browse Conference Publications .Instrumentation, Measurement. A Modified Shuffled Frog Leaping Algorithm with Convergence of Update Process in Local Search,IEEE,1016 - 1019
Alghazi A.. Shokri Z. Selim. And Elazouni A. .(2012).Performance of Shuffled Frog-Leaping Algorithm in Finance-Based Scheduling, Journal of Computing in Civil Engineering, 396-408.
Eusuffa M. Lanseyb K. And Pashab F. (2006).Shuffled frog-leaping algorithm: a mimetic meta-heuristic for discrete optimization. Engineering Optimization, 38(2), 129-154.
Tavakolan M.(2011).Applying the Shuffled Frog-Leaping Algorithm to Improve Scheduling Of Construction Projects With Activity Spliting Allowed. Management and Innovation for a Sustainable Built Environment.
Afshar A. Kasaeian Ziaraty A. Kaveh A. Sharifi F. Nondominated .(2009).Archiving Multicolony Ant Algorithm in Time-Cost Trade-Off Optimization. J. Constr. Eng. Mgmt., 135(7), 668-674.
Duan Q. Sorooshian S. and Gupta V. (1992).Effective and Efficient Global Optimization for Conceptual Rainfall Runoff models. Journal of Water Resources Res, 28,1015-1031.
Elbeltagi E. Hegazy T. and Grierson D. (2005).Comparison Among Five Evolutionary-based Optimization Algorithms, Adv. Eng. Inf., 19 (1), 43-53.
Elbeltagi, E. (2016). A Modified Shuffled Frog Leaping Algorithm for Optimizing Bridge-Deck Repairs, Int. Conference on Bridge Mgmt. Systems. Egypt, Cairo, 1-10.
Eusuff M. M., Lansey K.E. (2003). Optimizing of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm, J. Water Resource Plan Mgmt., 129(3), 210-225.
Zamani, R. (2013). A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem. European Journal of Operational Research, 229, 552-559.
Sadeghi A. Kalanaki A. Noktehdan A, Safi Samghabadi A. Barzinpour F.(2011).Using Bees Algorithm to Solve the Resource Constrained Project Scheduling Problem in PSPLIB, Communications in Computer and Information Science, 164:486-494.
Brucker P. Drexl A.Mohring R. Neumann K. Pesch E. (1999).Resource-constrained project scheduling: Notation, classication, models, and methods, European Journal of Operational Research: 3-41.
Wang A. Wang Xu A. GeXian-long B. Lei D. (2014).Multi-objective optimization model for multi-project scheduling on critical chain. Advances in Engineering Software, 31-48.
Afshar B., Nadjafi J., Rahimi A., Karimi H. (2013). A genetic algorithm for mode identity and the resource constrained project scheduling problem.
Alcaraz J.Maroto C. Ruiz R.(2003).Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of Operation Research Society, 54, 614-626.
Elloumi S. Fortemps P.(2012).A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 205: 31-41.
Jarboui B. Damak N. Siarry P.Rebai A. (2012). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, 195, 299-308.
Jozefowska J., Mika M., Rozycki R., Waligora G. (2006). Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102, 137-155.
Kolisch R. Drexl A. (2010).Local search for non-preemptive multi-mode resource-constrained project scheduling. IIE Transactions 29, 987-999.
Kolisch R. Hartmann S. (1999). Heuristic algorithms for solving the resource-constrained project scheduling problem: classification. Computational, analysis. Project Scheduling: Recent Models, Algorithms and Applications. Kluwer Press, Berlin, 147-178.
Kolisch R.(2002). Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. European Journal of Operational Research, 90:320-333.
_||_
Demeulemeester W S., Herrolen W S.(2002). Project Scheduling. Kluwer Academic Publishers.
Brucker P. Drexl A. Mohring R. Neumann K. Pesch E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112, 3–41.
Sprecher A. (1997). Exact algorithm for RCPSP in multi-mode case. OR Spectrum, 19(3), 95-203.
Buddhakulsomsiria J., Kim D.S. (2006). Properties of multi-mode resource constrained project scheduling problems with resource vacations and activity splitting, European Journal of Operational Research, 175, 279–295.
Buddhakulsomsiria J. Kim D.S. (2007).Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. European Journal of Operational Research, 178,374–390.
Schultmann F. Rentz O. (2001). Environment-oriented project scheduling for the dismantling of buildings. OR Spectrum, 23(1), 51–78.
Demeulemeester E.L. de Reyck B. Herroelen W.S.(2000). The discrete time/resource trade-off problem in project networks – A branch-and-bound approach. IIE Transactions, 32,1059–1069.
Ranjbar M. Kianfar F. (2007). Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms. Applied Mathematics and Computation, 191, 451–456.
Ranjbar M. de Reyck B. Kianfar F. (2009). A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. European Journal of Operational Research, 193, 35–48.
Akkan C., Drexl A., Kimms A., (2005). Network decomposition-based benchmark results for the discrete time-cost tradeoff problem, European Journal of Operational Research, 165, 339–358.
Maniezzo V. Mingozzi A.(1999). The project scheduling problem with irregular starting time costs. Operations Research Letters, 25(4), 175–182.
Mohring R.H. Schulz A.S. Stork F. Uetz M. (2001). On project scheduling with irregular starting time costs. Operations Research Letters, 28 (4): 149–154.
Wang Qiusheng, Autom. Sci. & Electr. Eng., Beihang Univ., Beijing. (2013). China Browse Conference Publications .Instrumentation, Measurement. A Modified Shuffled Frog Leaping Algorithm with Convergence of Update Process in Local Search,IEEE,1016 - 1019
Alghazi A.. Shokri Z. Selim. And Elazouni A. .(2012).Performance of Shuffled Frog-Leaping Algorithm in Finance-Based Scheduling, Journal of Computing in Civil Engineering, 396-408.
Eusuffa M. Lanseyb K. And Pashab F. (2006).Shuffled frog-leaping algorithm: a mimetic meta-heuristic for discrete optimization. Engineering Optimization, 38(2), 129-154.
Tavakolan M.(2011).Applying the Shuffled Frog-Leaping Algorithm to Improve Scheduling Of Construction Projects With Activity Spliting Allowed. Management and Innovation for a Sustainable Built Environment.
Afshar A. Kasaeian Ziaraty A. Kaveh A. Sharifi F. Nondominated .(2009).Archiving Multicolony Ant Algorithm in Time-Cost Trade-Off Optimization. J. Constr. Eng. Mgmt., 135(7), 668-674.
Duan Q. Sorooshian S. and Gupta V. (1992).Effective and Efficient Global Optimization for Conceptual Rainfall Runoff models. Journal of Water Resources Res, 28,1015-1031.
Elbeltagi E. Hegazy T. and Grierson D. (2005).Comparison Among Five Evolutionary-based Optimization Algorithms, Adv. Eng. Inf., 19 (1), 43-53.
Elbeltagi, E. (2016). A Modified Shuffled Frog Leaping Algorithm for Optimizing Bridge-Deck Repairs, Int. Conference on Bridge Mgmt. Systems. Egypt, Cairo, 1-10.
Eusuff M. M., Lansey K.E. (2003). Optimizing of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm, J. Water Resource Plan Mgmt., 129(3), 210-225.
Zamani, R. (2013). A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem. European Journal of Operational Research, 229, 552-559.
Sadeghi A. Kalanaki A. Noktehdan A, Safi Samghabadi A. Barzinpour F.(2011).Using Bees Algorithm to Solve the Resource Constrained Project Scheduling Problem in PSPLIB, Communications in Computer and Information Science, 164:486-494.
Brucker P. Drexl A.Mohring R. Neumann K. Pesch E. (1999).Resource-constrained project scheduling: Notation, classication, models, and methods, European Journal of Operational Research: 3-41.
Wang A. Wang Xu A. GeXian-long B. Lei D. (2014).Multi-objective optimization model for multi-project scheduling on critical chain. Advances in Engineering Software, 31-48.
Afshar B., Nadjafi J., Rahimi A., Karimi H. (2013). A genetic algorithm for mode identity and the resource constrained project scheduling problem.
Alcaraz J.Maroto C. Ruiz R.(2003).Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of Operation Research Society, 54, 614-626.
Elloumi S. Fortemps P.(2012).A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 205: 31-41.
Jarboui B. Damak N. Siarry P.Rebai A. (2012). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, 195, 299-308.
Jozefowska J., Mika M., Rozycki R., Waligora G. (2006). Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102, 137-155.
Kolisch R. Drexl A. (2010).Local search for non-preemptive multi-mode resource-constrained project scheduling. IIE Transactions 29, 987-999.
Kolisch R. Hartmann S. (1999). Heuristic algorithms for solving the resource-constrained project scheduling problem: classification. Computational, analysis. Project Scheduling: Recent Models, Algorithms and Applications. Kluwer Press, Berlin, 147-178.
Kolisch R.(2002). Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. European Journal of Operational Research, 90:320-333.
