حل مسئله زمانبندی پروژه با هدف کمینه سازی زمان اتمام پروژه با محدودیت منابع با الگوریتم فراابتکاری قورباغه
الموضوعات :
Alireza Haji Akhondi
1
(PhD student, Department of Industrial Engineering, Malek Ashtar University, Tehran, Iran)
Gholam Reza Tavakoli
2
(Assistant Professor, Malek Ashtar University, Tehran, Iran)
Peyman Akhavan
3
(Associate Professor, Malek Ashtar University, Tehran, Iran)
Manouchehr Manteghi
4
(Associate Professor, Malek Ashtar University, Tehran, Iran)
تاريخ الإرسال : 05 الإثنين , شعبان, 1438
تاريخ التأكيد : 27 الثلاثاء , محرم, 1439
تاريخ الإصدار : 06 الأحد , ربيع الثاني, 1439
الکلمات المفتاحية:
Project Scheduling,
SFLA,
Meta-heuristic Algorithm,
زمانبندی پروژه,
RCPSP,
الگوریتم فراابتکاری,
ملخص المقالة :
الگوریتم جهش ترکیبی قورباغه (SFLA) یک الگوریتم مبتنی بر ممتیک متاهیوریستیکِ است. این الگوریتم در سالهای اخیر توسط Eusuff و Lansey ایجاد شد. الگوریتم SFLA از نحوه‌ی جستجوی غذای گروه‌های قورباغه سرچشمه می‌گیرد. این الگوریتم برای جستجوی محلی میان زیرگروه‌های قورباغه از روش نمو ممتیک استفاده می‌کند. SFLA از استراتژی ترکیب استفاده می‌کند و امکان مبادله پیام در جستجوی محلی را فراهم می‌سازد. الگوریتم جهش ترکیبی قورباغه مزایای الگوریتم نمو ممتیک و بهینه‌سازی گروه ذرات (PSO) را ترکیب می‌کند. یکی از مسائل مشهور در زمینه کنترل پروژه، زمانبندی پروژه با محدودیت منابع و سایر محدودیتها می باشد که زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسائل دارای پیشینه تحقیقاتی غنی است. مساله زمانبندی پروژه با منابع محدود در واقع کلی ترین مساله زمانبندی است. مسائل زمانبندی کارگاهی، جریان کارگاهی ، زمانبندی و سایر مسائل زمانبندی همگی زیر مجموعه ای از این مسئله به حساب می آیند. زمانبندی پروژه یکی از وظایف اصلی و فعالیت‌های اصلی در مدیریت پروژه است. وجود محدودیت منابع و همچنین روابط پیش نیازی بین فعالیت‌ها مسئله زمانبندی پروژه را امری دشوار می‌سازد. زمانبندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسائل با ادبیات غنی در حوزه مسائل تحقیق در عملیات است.این مسئله توجه محققان را در سالهای اخیر بشدت بخود جلب کرده است و تاکنون با الگوریتم های مختلف حل شده است. در این مقاله به بررسی و عملکرد الگوریتم جهش قورباغه (SFLA) در حل مسائل زمانبندی پروژه با محدودیت منابع پایه پرداخته می شود که نتایج حاکی از عملکرد مناسب و قوی این الگوریتم فراابتکاری جدید می باشد.
المصادر:
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.
