مدلسازی ریاضی مسأله زمان‌بندی پروژه با رویکرد محدودیت منابع و حل آن با استفاده از الگوریتم‌های فراابتکاری

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

نویسندگان

1 1- دانشیار، گروه مدیریت صنعتی، دانشکده مدیریت، دانشگاه تهران، تهران، ایران

2 کارشناس ارشد مدیریت صنعتی، دانشکده مدیریت، دانشگاه تهران، تهران، ایران

چکیده

مسئله زمان‌بندی پروژه با محدودیت منابع یکی از مسائل بسیار معروف و مطرح در زمینه تحقیق در عملیات و مدیریت پروژه است. در پژوهش حاضر، این مسئله با در نظر گرفتن اهداف مهمی  شامل کمینه‌کردن زمان اتمام پروژه و همچنین کمینه‌کردن حداکثر هزینه انجام پروژه در یک روز مدل‌سازی شده است. در این راستا، تمامی روابط پیش‌‌‌نیازی ممکن بین فعالیت‌های یک پروژه موردتوجه قرار گرفته است. مدل پیشنهادی برای سه پروژه واقعی در اندازه‌‌‌های متفاوت و با استفاده از الگوریتم‌های فراابتکاری شامل الگوریتم ژنتیک، بهینه‌سازی ازدحام ذرات و تکامل تفاضلی اجرا شده است. نتایج حاصل از اجرای مدل نشان می‌دهد که الگوریتم تکامل تفاضلی برای پروژه‌‌‌های با مقیاس بزرگ و الگوریتم ازدحام ذرات برای پروژه‌‌‌های با مقیاس متوسط، از کارایی مطلوبی در مقایسه با الگوریتم‌ ژنتیک برخوردار است. استفاده از الگوریتم‌های فراابتکاری برای حل پروژه‌های با مقیاس کوچک توصیه نمی‌شود.

کلیدواژه‌ها


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

Mathematical Modeling of Resource-Constrained Project Scheduling Problem and Solving It by Using Metaheuristic Algorithms

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

  • Aliyeh Kazemi 1
  • Fatemeh Sarvandi 2
1 Associate Professor, Industrial Management Department, Faculty of Management, University of Tehran, Tehran, Iran
2 Master of Science (MSc) in Industrial Management, Faculty of Management, Tehran University, Tehran, Iran
چکیده [English]

One of the popular problems in operations research and project management is resource-constrained project scheduling problem. In the present study, this problem is modeled considering important goals consisted of minimization of the project completion time, as well as minimization of the maximum cost of the project in one day. In this regard, all the possible prerequisite relations between the activities of a project are considered. The proposed model has been implemented for three real projects in different sizes and by using metaheuristic algorithms including genetic algorithm, particle swarm optimization and differential evolution. The results showed that differential evolution and particle swarm optimization algorithms have efficient performances compared to the genetic algorithms for large- and medium-scale projects respectively. The use of metaheuristic algorithms for solving small-scale projects is not recommended.

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

  • Project scheduling
  • resources constraint
  • genetic algorithm
  • Particle Swarm Optimization Algorithm
  • Differential Evolution Algorithm

[1]      Bineshian, M., Safari, S., Abbasi, R., Momeni, M., (1397), Optimization of organization portfolio; clustering approach and fuzzy multi-criteria decision making, Modern Researches in decision making, 3(2), 81-106.

[2]      Hartmann, S., Briskorn, D. (2010), A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207(1), 1–14.

[3]      Wiest, J.D. (1963), The scheduling of large projects with limited resources, PhD dissertation, Carnegie Institute of Technology, 10–15.

[4]      Fahmy, A., Hassan, T.M., Bassioni, H. (2014), Improving RCPSP solutions quality with Stacking Justification – Application with particle swarm optimization, Expert Systems with Applications, 41(13), 5870–5881.

[5]      Jiang, G., Shi, J. (2005), Exact algorithm for solving project scheduling problems under multiple resource constraints, Journal of Construction Engineering and Management, 131(9), 986–992.

[6]      Zhang, H., Li, H., Tam, C.M. (2006), Particle swarm optimization for resource-constrained project scheduling, International Journal of Project Management, 24, 83-92.

[7]      Damak, J., Jarboui, B., Siarry, P., Loukil, T., (2009), Differential evolution for solving multi-mode resource-constrained project scheduling problems, Computers and Operations Research., 36, 2653–2659.

[8]      Wu, L., Wang, Y., Zhou, S. (2010), Improved differential evolution algorithm for resource-constrained project scheduling problem, Journal of Systems Engineering and Electronics, 21, 798-805.

[9]      Chen, R.M., Wu, C.L., Wang, C.M., Lo, S.T. (2010), Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB. Expert Systems with Applications, 37, 1899-1910.

[10]   Liu, Y.C., Gao, H.M., Yang, S.M., Chuang, C.Y. (2014), Application of genetic algorithm and fuzzy Gant chart to project scheduling with resource constraints, Intelligent Computing Methodologies, 8589, 241-252.

[11]   Yan, R., Li, W., Jiang, P., Zhou, Y., Wu, G. (2014), A modified differential evolution algorithm for resource constrained multi-project scheduling Problem, Journal of Computers, 9, 1922-1927.

[12]   Fahimy, A., Hassan, T. M., Bassioni, H., (2014), Improving RCPSP solutions quality with stacking justification–Application with particle swarm optimization, Expert Systems with Applications, 41(13), 5870–5881.

[13]   Kumar, N., Vidyarthi, D. P. (2015), A model for resource-constrained project scheduling using adaptive PSO, Soft Computing, 19, 1-16.

[14]   Kadri, R.L., Boctor, F.F., (2017), An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case, European Journal of Operational Research, 265(2), 454-462.

[15]   Ghafoori, S., Taghizadeh.Y, MR., (2017), Proposing a multi-objective   mathematical model for RCPSP and solving It with firefly and simulated annealing algorithms, Modern Researches in Decision Making, 1(4), 117 142.

[16]   Karimi, N., Zandieh, M., Karamooz, H.R. (2010), Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach, Expert Systems with Applications, 37(6), 4024–4032.

[1]      Bineshian, M., Safari, S., Abbasi, R., Momeni, M., (1397), Optimization of organization portfolio; clustering approach and fuzzy multi-criteria decision making, Modern Researches in decision making, 3(2), 81-106.[AaH1] 

[2]      Hartmann, S., Briskorn, D. (2010), A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207(1), 1–14.

[3]      Wiest, J.D. (1963), The scheduling of large projects with limited resources, PhD dissertation, Carnegie Institute of Technology, 10–15.

[4]      Fahmy, A., Hassan, T.M., Bassioni, H. (2014), Improving RCPSP solutions quality with Stacking Justification – Application with particle swarm optimization, Expert Systems with Applications, 41(13), 5870–5881.

[5]      Jiang, G., Shi, J. (2005), Exact algorithm for solving project scheduling problems under multiple resource constraints, Journal of Construction Engineering and Management, 131(9), 986–992.

[6]      Zhang, H., Li, H., Tam, C.M. (2006), Particle swarm optimization for resource-constrained project scheduling, International Journal of Project Management, 24, 83-92.

[7]      Damak, J., Jarboui, B., Siarry, P., Loukil, T., (2009), Differential evolution for solving multi-mode resource-constrained project scheduling problems, Computers and Operations Research., 36, 2653–2659.

[8]      Wu, L., Wang, Y., Zhou, S. (2010), Improved differential evolution algorithm for resource-constrained project scheduling problem, Journal of Systems Engineering and Electronics, 21, 798-805.

[9]      Chen, R.M., Wu, C.L., Wang, C.M., Lo, S.T. (2010), Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB. Expert Systems with Applications, 37, 1899-1910.

[10]   Liu, Y.C., Gao, H.M., Yang, S.M., Chuang, C.Y. (2014), Application of genetic algorithm and fuzzy Gant chart to project scheduling with resource constraints, Intelligent Computing Methodologies, 8589, 241-252.

[11]   Yan, R., Li, W., Jiang, P., Zhou, Y., Wu, G. (2014), A modified differential evolution algorithm for resource constrained multi-project scheduling Problem, Journal of Computers, 9, 1922-1927.

[12]   Fahimy, A., Hassan, T. M., Bassioni, H., (2014), Improving RCPSP solutions quality with stacking justification–Application with particle swarm optimization, Expert Systems with Applications, 41(13), 5870–5881.

[13]   Kumar, N., Vidyarthi, D. P. (2015), A model for resource-constrained project scheduling using adaptive PSO, Soft Computing, 19, 1-16.

[14]   Kadri, R.L., Boctor, F.F., (2017), An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case, European Journal of Operational Research, 265(2), 454-462.

[15]   Ghafoori, S., Taghizadeh.Y, MR., (2017), Proposing a multi-objective   mathematical model for RCPSP and solving It with firefly and simulated annealing algorithms, Modern Researches in Decision Making, 1(4), 117 142.

[16]   Karimi, N., Zandieh, M., Karamooz, H.R. (2010), Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach, Expert Systems with Applications, 37(6), 4024–4032.


 [AaH1]ارجاع ناقص است

اصلاح شد.