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

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

نویسندگان

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

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

چکیده

زمان بندی پروژه با در نظر گرفتن محدودیت منابع از جمله مسائل با ادبیات غنی در حوزه تحقیق در عملیات و مدیریت پروژه است. تاکنون مقالات و کتب بسیاری در این زمینه به چاپ رسیده است که دو دلیل عمده بر این امر می‌توان برشمرد: نخست آنکه این مسائل بسیار متنوع هستند و دیگر اینکه با توجه به NP-Hard بودن این مسائل، محققین همواره به دنبال راه حل های کاراتر برای حل این مسایل بوده اند.این پژوهش به منظور ارائه مدلی چند هدفه با در نظر داشتن انواع روابط پیش نیازی و همچنین سنجش کارایی الگوریتم کرم شب تاب در حل مسائل RCPSP انجام شده است. از اینرو ابتدا یک مدل ریاضی دو هدفه شامل زمان و هزینه با در نظر گرفتن روابط پیش‌نیازی کلی، جهت زمان‌بندی پروژه های استاندارد با محدودیت منابع ارائه شده است و سپس با استفاده از الگوریتم‌ فراابتکاری کرم شب‌تاب ترکیب شده با یک الگوریتم ابتکاری جواب‌های پاره تو برای مساله در نرم افزار متلب نسخه R2014a بدست آمده است و همچنین جهت سنجش کارایی الگوریتم کرم شب تاب، مساله با الگوریتم تبرید شبیه سازی‌شده نیز حل شد که نتایج به دست آمده حاکی از عملکرد مطلوب الگوریتم کرم شب تاب و عملکرد قابل قبول تبرید شبیه سازی شده در حل مساله فوق الذکر در مقایسه با بهترین جواب‌های موجود برای مسائل استاندارد تاکنون می باشد.

کلیدواژه‌ها


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

Proposing a Multi-Objective Mathematical Model for RCPSP and Solving It with Firefly and Simulated Annealing algorithms

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

  • saeed ghafoori 1
  • mohammadreza taghizadeh yazdi 2
1 M.S. of Industrial Management, Department of Industrial Management, Faculty of Management, University of Tehran,Tehran, Iran
2 Assistant Professor, Department of Industrial Management, Faculty of Management, University of Tehran, Tehran, Iran
چکیده [English]

Timing a project with taking the limitations of resources into account is one of the issues with rich literature in the field of research in operation and project management. A great number of books and articles has been published regarding this field and two reasons can account for such an action: First, these issues are of high variety and second, since these issues are NP-Hard, scientists have also been looking for some more efficient ways to deal with these problems. The present study aims to propose a mathematical model with considering precedence relations; furthermore, it also aims at evaluating the efficiency of the firefly algorithm in solving RCPSP. To this end, a bi-objective mathematical model including time and cost, with regard to general precedence relations (GPR), has been proposed to time and manage the standard projects with resource constraint and then, using firefly metaheuristic algorithm composed with heuristic algorithm, relative answers in MATLAB software, version R2014a, have been acquired; moreover, in order to evaluate the efficiency of the firefly algorithm, the problem was solved using simulated annealing algorithm. The results reveled the accurate efficiency of the firefly algorithm as well as the acceptable function of the simulated annealing algorithm in solving the aforementioned problem; these results are way supreme when compared to those of best ways currently deployed.

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

  • Project scheduling
  • Resource Constraint
  • Meta-heuristic algorithms
  • Multi-Objective Firefly Algorithm (MOFA)
  • Multi-Objective Simulated Annealing Algorithm (MOSA)
[1]   Sabzeparvar M. (2014) "Project management and control", 11th Edition, Termeh Press, Tehran.
[2]   Shirmohammadi A. (2010) Management and control of project, 2nd Edition, Esfahan, Jahad Daneshgahi Press.
[3]   Demeulemeester E. L. (2002) Project scheduling: A research handbook, Vol. 102, Springer.
[4]   Deckro R. F. Winkofsky E. P, Hebert J. E., Gagnon R. (1991) "A decomposition approach to multi-project scheduling", Eur. J. Oper. Res., Vol. 51, No. 1: 110–118.
[5]   Chiu H. N., Tsai D. M. (2002) "An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows", Constr. Manag. Econ., Vol. 20, No. 1: 55–66.
[6]   Kim K. W., Gen M., Yamazaki G. (2003) "Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling", Appl. Soft Comput., Vol. 2, No. 3: 174–188.
[7]   Kumanan S., Jose G. J., Raja K. (2006) "Multi-project scheduling using an heuristic and a genetic algorithm", Int. J. Adv. Manuf. Technol, Vol. 31, No. 3–4, pp. 360–366.
[8]   Tseng L.-Y., Chen S.-C. (2006) "A hybrid metaheuristic for the resource-constrained project scheduling problem", Eur. J. Oper. Res., Vol. 175, No. 2: 707–721.
[9]   Gonçalves J. F., Mendes J. J. M., Resende M. G. C. (2008) "A genetic algorithm for the resource constrained multi-project scheduling problem", Eur. J. Oper. Res., Vol. 189, No. 3: 1171–1190.
[10] Ziarati K., Akbari R., Zeighami V. (2011) "On the performance of bee algorithms for resource-constrained project scheduling problem", Appl. Soft Comput., Vol. 11, No. 4: 3720–3733.
[11] Wu S., Wan H.-D., Shukla S. K., Li B. (2011) "Chaos-based improved immune algorithm (CBIIA) for resource-constrained project scheduling problems", Expert Syst. Appl., Vol. 38, No. 4: 3387–3395.
[12] Wang L., Fang C. (2012) "A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem", Expert Syst. Appl., Vol. 39, No. 3: 2451–2460.
[13] Nasiri M. M. (2013) "A pseudo particle swarm optimization for the RCPSP,” Int. J. Adv. Manuf. Technol., Vol. 65, No. 5–8: 909–918.
[14] Koulinas G., Kotsikas L., Anagnostopoulos K. (2014) "A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem", Inf. Sci. (Ny)., Vol. 277, pp. 680–693.
[15] Fahmy A., Hassan T. M., Bassioni H. (2014) "Improving RCPSP solutions quality with Stacking Justification – Application with particle swarm optimization", Expert Syst. Appl., Vol. 41, No. 13, pp. 5870–5881.
[16] Zhang L., Luo Y., Zhang Y. (2015) “Hybrid particle swarm and differential evolution algorithm for solving multimode resource-Constrained project scheduling problem", Joural Control Sci. nad Eng., Vol. 2015.
[17] Jafarnejad Chaghoshi A. (2012) Modern production and operation management’ University of Tehran press, Tehran, Iran.
[18] Mehregan M. (2012) ‘Mathematical modeling’ 4th edition, SAMT press, Tehran, Iran.
 [19]        Cheng M., Tran D., Cao M. (2014) "Hybrid multiple objective artificial bee colony with differential evolution for the time-cost-quality tradeoff problem", KNOWLEDGE-BASED SYSTEMS. Elsevier B.V.
[20] Shahsavari por N., Modarres M., Aryanejad M. B., Tavakoli Moghadam R. (2010) “The discrete time-cost-quality trade-off problem using a novel hybrid genetic algorithm", Appl. Math. Sci., Vol. 4, No. 42, pp. 2081–2094.
[21] Wolpert D. H., Macready W. G. (1997) "No free lunch theorems for optimization", Evol. Comput. IEEE Trans., Vol. 1, No. 1, pp. 67–82.
[22] Kolisch R., Sprecher A. (1997) "PSPLIB - A project scheduling problem library", Eur. J. Oper. Res., Vol. 96, No. 1, pp. 205–216.
[23] Yang X.-S. (2010) "Firefly algorithm, stochastic test functions and design optimisation", Int. J. Bio-Inspired Comput., Vol. 2, No. 2, pp. 78–84.
[24] Yousefi A. A., Ebrahim khani H. (2011) "Evaluation and development of firefly algorithm to solve the scheduling of workshop production problem’ 9th international conference of industrial engineering", Tehran, Iran.
[25] Yang X. (2012) "Multiobjective firefly algorithm for continuous optimization", pp. 13–15.
[26] Cerny V. (1985) "Thermodynamical approach to the traveling salesman problem : An efficient simulation algorithm", J. Optim. THEORY Appl., Vol. 45, No. l, pp. 41–51.
[27] Kirkpatrick S., Gelatt C. D.,. Vecchi M. P.(1983) "Optimization by Simulated Annealing", Sceince, Vol. 220, No. 4598, pp. 671–682.
[28] J. Doreo, Petrowski A., Siarry P., Taillard E. (2006) Metaheuristics for Hard Optimization: Methods and Case Studies, Springer-Verlang.
[29] Sajjadi S. Kh. A., Azimi P. (2015) "Optimizing the equipment of the bank brach with simulation and annealing algorithm", Journal of Management Researches in Iran (MRIJ), Vol. 58, pp. 65-86, (in Persian).
[30] Moraga R. J., DePuy G. W., Whitehouse G. E. (2006) A Solution Methodology for Optimization Problems, Taylor and Francis Group LLC.
[31] Talbi E.-G. (2009) Metaheuristics: from design to implementation, John Wiley & Sons.
[32] Tavana M., Abtahi A., Khalili-Damghani K. (2014) "A new multi-objective multi-mode model for solving preemptive time–cost–quality trade-off project scheduling problems", Expert Syst. Appl., Vol. 41, pp. 1830–1846.
[33] Sadeghi A. (2010) "Solving the resource coonstrained project scheduling problem with firefly algorithm", Master thesis, University of Payam-e-Noor, Tehran, Iran.