ارائه یک روش فرا ابتکاری مؤثر جهت زمانبندی پروژه با حالت های چندگانه

نوع مقاله : پژوهشی

نویسندگان

دانشگاه صنعتی امیرکبیر

چکیده

در این مقاله الگوریتم دسته پرندگان کاملاً آگاه (FIPS) برای حل مساله زمان بندی پروژه، تحت محدودیت منابع در حالت چندگانه (MRCPSP)، با هدف حداقل نمودن زمان پروژه پیشنهاد شده است. در FIPS پیشنهادی، روش نمایش کلید تصادفی و روش نمایش لیست حالات اجرایی مربوطه، جهت کدگذاری استفاده می گردد و جهت رمزگشایی نیز، از روش تولید زمان‌بندی سری چندحالته، کمک گرفته خواهد شد. بویژه، تابع تناسب جدیدی برای کاهش زمان محاسبات برنامه و انحراف متوسط ارایه می شود. مجموعه های پایه و شناخته شده کتابخانه مسایل زمان بندی پروژه‌ها (PSBLIB)، جهت آزمایش الگوریتم‌ FIPS پیشنهادی، به کار گرفته شده‌اند که نتایج محاسباتی حاصله از آن‌ و مقایسات انجام شده، کارآمدی الگوریتم پیشنهادی را نشان می‌دهد.

کلیدواژه‌ها

عنوان مقاله [English]

An efficient meta-heuristic algorithm for project scheduling with multiple modes

نویسندگان [English]

  • Mohammad Hassan Sebt
  • Mohammad Reza Afshar
  • Yagub Alipouri
Amirkabir University of Technology
چکیده [English]

In this paper, a Fully Informed Particle Swarm (FIPS) algorithm is proposed for solving the Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. In the proposed FIPS, A random key and the related mode list (ML) representation scheme are used as encoding schemes and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. In particular, a new fitness function which reduces the average deviation from optimality and CPU-time is presented. Comparing the results of the proposed FIPS with other approaches using the well-known benchmark sets in PSPLIB validate the effectiveness of the proposed algorithm to solve the MRCPSP.

کلیدواژه‌ها [English]

  • Multi-mode Resource Constrained Project Scheduling Problem
  • Precedence constraints
  • Resource constraints
  • Fully informed particle swarm (FIPS) algorithm
  • Random key representation

مراجع

Chen, P. and Weng, H., "A two-phase GA model for resource-constrained project scheduling", Automation in Construction, Vol. 28, pp. 485-498, (2009).
2. Zhang, H., "Ant Colony Optimization for Multimode Resource-Constrained Project Scheduling", American Society of Civil Engineers, Vol. 28, pp. 150-159, (2012).
3. Sprecher, A. and Drexl, A., "Solving multi-mode resource-constrained project scheduling problems by a simple, general and powerful sequencing algorithm", European Journal of Operational Research, Vol. 107, pp. 431–450, (1998).
4. Glover, F. and Greenberg H.J., "New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence", European Journal of Operational Research, Vol. 39, pp. 119-130, (1989).
5. Jo´ zefowska, J. Mika, M. Rozycki, R. Waligora, G. and Weglarz, J., "Simulated annealing for multi-mode resource-constrained project scheduling", Annals of Operations Research, Vol. 102, pp. 137–155, (2001).
6. Zhang, H. Tom, C.M. and Li, H., "Multimode Project Scheduling Based on Particle Swarm Optimization", Computer-Aided Civil and Infrastructure Engineering, Vol. 21, pp. 93– 103, (2006).
7. Lova, A. Tormos, P. Cervantes, M. and Barber, F., "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes", International Journal of Production Economics, Vol. 117 (2), pp. 302– 316, (2009).
8. Peteghme, V.V. and Vanhoucke, M., "An artificial immune system for the multi-mode resource-constrained project scheduling problem", in: EvoCOP, Springer, Berlin, Tubingen, Germany, pp. 100-107, (2009).
9. Peteghem, V.V. and Vanhoucke, M., "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 201, pp. 409–418, (2010).
10. Elloumi, S. and Fortemps, P., "A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 205, pp. 31–41, (2010).
11. Wang, L. and Fang, C. "An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem", Information Sciences, Vol. 181, pp. 4804–4822, (2011).
12. Wang, L. and Fang, C., "An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem", Computers and Operations Research, Vol. 39, pp. 449–460, (2012).
13. Lee, K. and El-Sharkawi, M., "Modern heuristic optimization techniques", Hoboken, New Jersey, John Wiley and Sons, pp. 50-157, (2008).
14. Damak, N. Jarboui, B. Siarry, P. and Loukil, T., "Differential evolution for solving multi-mode resource constrained project scheduling problems", Computers and Operations Research, Vol. 36, pp. 2653-2659, (2009).
15. Mendes, R. Kennedy, J. and Neves, J., "The Fully Informed Particle Swarm: Simpler, Maybe Better", IEEE Transactions on Evolutionary Compution, Vol. 14, pp. 204-210, (2004).
16. Sprecher, A. Hartmann, S. and Drexl, A., "An exact algorithm for project scheduling with multiple modes", OR Spektrum: Organ der Deutschen Gesellschaft fur Operations Research, Vol. 19(3), pp. 195-203, (1997).
17. Kolisch, R., "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation", European Journal of Operational Research, Vol. 43, pp. 23–40, (1996).
18. Tormos, P. and Lova, A., "A competitive heuristic solution technique for resource-constrained project scheduling", Annals of Operations Research, Vol. 102, pp. 65–81, (2001).
19. Ranjbar, M. Reyck, B. and De Kianfar, F., "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling", European Journal of Operational Research, Vol. 193(1), pp. 35–48, (2009).
20. Alcaraz, J. Maroto, C. and Ruiz, R., "Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms", Journal of the Operational Research Society, Vol. 54, pp. 614–626, (2003).
ارسال نظر در مورد این مقاله
CAPTCHA Image

فایل ها

هم رسانی

ارجاع به این مقاله

آمار