A Hybridized Metaheuristic Algorithm to Solve the Robust Resource Constrained Multi-Project Scheduling Problem

Document Type : Research Article

Authors

1 Industrial Engineering Faculty, K.N.Toosi University of Technology, Tehran, Iran

2 Industrial Engineering Faculty, K. N. Toosi University of Technology, Tehran, Iran

Abstract

In this paper, the multi-project scheduling problem is studied. The duration of the activities is subjected to the considerable uncertainty and the robust optimization approach is considered to deal with the uncertainty. The maximum total tardiness of the projects is defined as the objective function which should be minimized. In order to allocate the constrained resources to the multi-projects, two models are proposed. In the first model, the projects are scheduled separately while in the second model, the multi-project approach is applied and the resource sharing policy is used. It is demonstrated that how the tardiness of the projects will be decreased when the multi-project approach is applied. Also, the Adaptive Bee Genetic Algorithm (ABGA) is designed as a hybrid metaheuristic algorithm and proposed in this paper to solve the first stage model of the Robust Resource Constrained Multi-Project Scheduling Problem (RRCMPSp ). The results of ABGA is compared with the results of scenario-relaxation algorithm as an exact algorithm for the small size problems. Also, the performance of ABGA is studied compared to the Genetic Algorithm (GA) and Artificial Bee Colony (ABC) as two basic algorithms for the large size problems. The results show the effectiveness of the proposed algorithm in solving the RRCMPSp .

Keywords

Main Subjects

References

1. Lova, A., and Tormos, P., “Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling”, Annals of Operations Research, Vol. 102, pp. 263–286, 2001.
2. Blismass, N., Sher, WD., Thorpe, A., and Baldwin, AN., “Factors influencing delivery within construction clients’ multi-project environments”, Engineering, Construction and Architectural Management, Vol. 11, No. 2, pp. 113–125, 2004a.
3. Aritua, B., Smith, N.J., and Bower, D., “Construction client multi-projects – A complex adaptive systems perspective”, International Journal of Project Management, Vol. 27, pp. 72–79 (2009).
4. Zheng, Z., Shumin, L., Ze, G., and Yueni, Z., “Resource constraint multi project scheduling with priority and uncertain activity durations”, International Journal of Computational intelligence systems, Vol. 6, No. 3, pp. 530-547, 2013.
5. Singh, A., “Resource Constrained Multi-Project Scheduling with Priority Rules & Analytic Hierarchy Process”, Procedia Engineering, Vol. 69, pp. 725 – 734, 2014.
6. Wei-xin, W., Xu, W., Xian-long, G., and Lei, D., “Multi-objective optimization model for multi-project scheduling on critical chain”, Advances in Engineering Software, Vol. 68, pp. 33–39, 2014.
7.  Wauters, T., Kinable, J., Smet, P., Vancroonenburg, W., Berghe, G., and Verstichel, J., “The Multi-Mode Resource-Constrained Multi-Project Scheduling Problem”, Journal of Scheduling, The MISTA 2013 challenge, 2013.
8. Besikci, U., Bilge, U., and Ulusoy, G., “Multi-mode resource constrained multi-project scheduling and resource portfolio problem”, European Journal of Operational Research, Vol. 240, pp. 22–31, 2015.
9. Zheng, Z., Shumin, L., Ze, G., Yueni, Z., and Zhang, X., “A critical chains-based distributed multi-project scheduling approach”, Neurocomputing, Vol. 143, pp. 282–293, 2014.
10. Klerides, E., and Hadjiconstantinou, E., “A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off settings and uncertain durations”, Computers and Operations Research, Vol. 37, No. 12, pp. 2131–2140, 2010.
11. Bertsimas, D., and Sim, M., “The price of robustness”, Operations Research, Vol. 52, No. 1, pp. 35-53, 2004.
12. Bruni, M.E., Puglia Pugliese, L., Di Beraldi, P., and Guerriero, F., “An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations”, Omega, Vol. 71, pp. 66-84, 2017.
13. Herroelen, W., and Leus, R., “Project scheduling under uncertainty: Survey and research potentials”, European Journal of Operational Research, Vol. 165, pp. 289–306, 2005.
14. Klerides, E. and Hadjiconstantinou, E. “A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off settings and uncertain durations”, Computers and Operations Research, 37(12), pp. 2131–2140 (2010).
15. Chiang, A.J., and Jeang, A., “Stochastic project management via computer simulation and optimisation method”, International Journal of Systems Science: Operations & Logistics, Vol. 2, No. 4, pp. 211–230, 2015.
16. Xiong, J., Chen, Y. W., Yang, K. W., Zhao, Q. S., and Xing, L. N., “A hybrid multi objective genetic algorithm for robust resource constrained project scheduling with stochastic durations”, Mathematical Problems in Engineering, 24 pages, 2012.
17. Duc Long, L., and Ohsato, A., “Fuzzy critical chain method for project scheduling under resource constraints and uncertainty”, International Journal of Project Management, Vol. 26, pp. 688–698, 2008.
18. Knyazeva, M., Bozhenyuk, B., and Rozenberg, I., “Resource-constrained project scheduling approach under fuzzy conditions”, Procedia Computer Science, Vol. 77, pp. 56-64, 2015.
19. Dixit, V., Srivastava, R.K., and Chaudhuri, A., “Procurement scheduling for complex projects with fuzzy activity durations and lead times”, Computers & Industrial Engineering, Vol. 76, pp. 401–414, 2014.
20.  Masmoudi, M., and Haït,  A., “Project scheduling under uncertainty using fuzzy modelling and solving techniques”, Engineering Applications of Artificial Intelligence, Vol. 26, No. 1, pp. 135–149, 2013.
21. Artigues, C., Leus, R., and Nobibon, F. T., “Robust optimization for resource-constrained project scheduling with uncertain activity durations”, Flexible Services and Manufacturing Journal, Vol. 25, pp. 175–205, 2013.
22. Yamashita, D.S., Armentano, V. A., and Laguna, M., “Robust optimization models for project scheduling with resource availability cost”, Journal of scheduling, Vol. 10, pp. 67–76, 2007.
23. Chakrabortty, R.K., Sarker, R.A., and Essam, D.L., “Resource constrained project scheduling with uncertain activity durations”, Computers & Industrial Engineering, http://dx.doi.org/10.1016/j.cie.2016.12.040, 2017.
24. Bruni, M. E. Di Puglia Pugliese, L. Beraldi, P., and Guerriero, F. A., “computational study of exact approaches for the adjustable robust resource constrained project scheduling problem”. Computers & Operations Research, Vol. 99, pp. 178-190, 2008.
25.Balas, E., “Project scheduling with resource constraints”, In E.M.L. Beale, (Ed.), Applications of Mathematical Programming Techniques, pp. 187-200, The English Universities Press Ltd, 1971.
26. Assavapokee, T., Realff, M.J., Ammons, J.C. and Hong, I-H. “Scenario relaxation algorithm for finite scenario-based min–max regret and min–max relative regret robust optimization”, Computers & Operations Research, Vol. 35, pp. 2093 – 2102, 2008.
27. Patterson, J. H., “Project Scheduling: The Effects of Problem Structure on Heuristic Performance”, Naval Research Logistic, Vol. 23, No. 1, pp. 95-123, 1976.
28. Blazewicz, J. Lenstra, J. K., and Rinnooy Kan, A. H. G., “Scheduling subject to resource constraints: classification and complexity”. Discrete Applied Mathematics, Vol. 5, No. 1, pp. 11 – 24, 1983.
29. Goncalves, J. F., Mendes, J. J. M., and Resende, M. G. C., “A genetic algorithm for the resource constrained multi-project scheduling problem”. European Journal of operational Research, 189, pp. 1171-1190, 2008.
30. Kim-Fung, M., Tang, K., and Kwong, S. "Genetic algorithms: concepts and applications [in engineering design”. IEEE transactions on Industrial Electronics, Vol. 43, No. 5, pp. 519-534, 1996.
31. Dervis, K., “An idea based on honey bee swarm for numerical optimization”. Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, Vol. 200, 2005.
32. Demeulemeester, E., Vanhoucke, M. and Herroelen, W. “A random network generator for activity-on-the-node networks”. Journal of Scheduling, 6, pp. 13-34, 2003.
33. Nabipoor Afruzi, E. Aghaie, A., and Najafi, A. A., “Robust Optimization for the Resource Constrained Multi-Project Scheduling Problem with Uncertain Activity Durations”. Scientia Iranica,
Articles in Press, Accepted Manuscript, Available Online from 05 August 2018.
34. Srinivas, M., and Patnaik, L. M. “Adaptive Probabilities of Crossover Genetic in Mutation and Algorithms”. IEEE Transactions on Systems, Man and Cybernetics, Vol. 24, No. 4, pp. 656-667, 1994.
35. Eiben, A. E. Marchiori, E., and Valko, V. A., “Evolutionary Algorithms with on-the-fly Population Size Adjustment”. In X. Yao et al., editors, Parallel Problem Solving from Nature PPSN VIII, LNCS 3242, pp. 41–50, 2004.
AUT Journal of Modeling and Simulation
Volume 51, Issue 1
June 2019
Pages 15-32

Files

Share

How to cite

Statistics