MULTI-MODE RESOURCE CONSTRAINED MULTI PROJECT SCHEDULING PROBLEM OPTIMIZATION WITH SYMBIOTIC ORGANISMS SEARCH
DOI:
https://doi.org/10.9744/duts.9.1.77-96Keywords:
Multi-mode Resource Constrained Multi Project Scheduling Problem (MRCMPSP), Metaheuristic, Symbiotic Organisms Search (SOS)Abstract
Multi-mode resource-constrained multi project scheduling problem (MRCMPSP) is the extension of standard resource constrained project scheduling problem which considers multiple activity execution modes and multiple projects, subject to precedence and resource constraints. Multiple execution modes allow the activities to have different duration and resource requirement. Furthermore, companies and project managers normally also handle many projects. This study proposed metaheuristic method Symbiotic Organisms Search (SOS) along with random-key (RK) representations, parallel schedule generation scheme (P-SGS), and forward backward scheduling, to find the feasible schedule and minimal project duration of the project portfolio. The evaluation results from standard benchmark instances shows that SOS can get the best solution in most of the tested instances and also achieve better solution in some of them. The validation results from real project case MRCMPSP show that SOS has better performance than other tested metaheuristic methods, namely GA and PSO. Thus, validate the performance of SOS.
References
Alcaraz, J., & Maroto, C. (2001). A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research, 102(1), 83-109. doi:10.1023/A:1010949931021
Bettemir Önder, H., & Sonmez, R. (2015). Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling. Journal of Management in Engineering, 31(5), 04014082. doi:10.1061/(ASCE)ME.1943-5479.0000323
Blazewicz, J., Lenstra, J. K., & Kan, A. H. G. R. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5(1), 11-24. doi:https://doi.org/10.1016/0166-218X(83)90012-4
Browning, T. R., & Yassine, A. A. (2010). Resource-constrained multi-project scheduling: Priority rule performance revisited. International Journal of Production Economics, 126(2), 212-228. doi:https://doi.org/10.1016/j.ijpe.2010.03.009
Chen, P.-H., & Shahandashti, S. (2009). Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction, 18, 434-443. doi:10.1016/j.autcon.2008.10.007
Cheng, M.-Y., & Prayogo, D. (2014). Symbiotic organisms search: A new metaheuristic optimization algorithm. Computers & Structures, 139, 98-112. doi:https://doi.org/10.1016/j.compstruc.2014.03.007
Cheng, M.-Y., Tran, D.-H., & Wu, Y.-W. (2014). Using a fuzzy clustering chaotic-based differential evolution with serial method to solve resource-constrained project scheduling problems. Automation in Construction, 37, 88-97. doi:https://doi.org/10.1016/j.autcon.2013.10.002
Gonçalves, J. F., Mendes, J. J. M., & Resende, M. G. C. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research, 189(3), 1171-1190. doi:https://doi.org/10.1016/j.ejor.2006.06.074
Habibi, F., Barzinpour, F., & Sadjadi, S. (2018). Resource-constrained project scheduling problem: review of past and recent developments. Journal of Project Management, 3, 55-88. doi:10.5267/j.jpm.2018.1.005
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. doi:https://doi.org/10.1016/j.ejor.2009.11.005
Herroelen, W., & Leus, R. (2005). Identification and illumination of popular misconceptions about project scheduling and time buffering in a resource-constrained environment. Journal of the Operational Research Society, 56(1), 102-109. doi:10.1057/palgrave.jors.2601813
Homberger, J. (2007). A multi-agent system for the decentralized resource-constrained multi-project scheduling problem. International Transactions in Operational Research, 14(6), 565-589. doi:https://doi.org/10.1111/j.1475-3995.2007.00614.x
Kannimuthu, M., Raphael, B., Ekambaram, P., & Kuppuswamy, A. (2020). Comparing optimization modeling approaches for the multi-mode resource-constrained multi-project scheduling problem. Engineering, Construction and Architectural Management, 27(4), 893-916. doi:10.1108/ECAM-03-2019-0156
Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), 320-333. doi:https://doi.org/10.1016/0377-2217(95)00357-6
Kolisch, R., & Drexl, A. (1997). Local search for nonpreemptive multi-mode resource-constrained project scheduling. Iie Transactions, 29(11), 987-999. doi:10.1023/A:1018552303415
Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis. In J. Węglarz (Ed.), Project Scheduling: Recent Models, Algorithms and Applications (pp. 147-178). Boston, MA: Springer US.
Kolisch, R., & Sprecher, A. (1997). PSPLIB - A project scheduling problem library: OR Software - ORSEP operations research software exchange program. European Journal of Operational Research, 96(1), 205-216. doi:https://doi.org/10.1016/S0377-2217(96)00170-1
Kurtulus, I., & Davis, E. W. (1982). Multi-project scheduling: categorization of heuristic rules performance. Management Science, 28(2), 161-172. Retrieved from https://EconPapers.repec.org/RePEc:inm:ormnsc:v:28:y:1982:i:2:p:161-172
Li, F., Xu, Z., & Li, H. (2021). A multi-agent based cooperative approach to decentralized multi-project scheduling and resource allocation. Computers & Industrial Engineering, 151, 106961. doi:https://doi.org/10.1016/j.cie.2020.106961
Li, K. Y., & Willis, R. J. (1992). An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research, 56(3), 370-379. doi:https://doi.org/10.1016/0377-2217(92)90320-9
Linyi, D., & Yan, L. (2007, 15-19 Dec. 2007). A particle swarm optimization for resource-constrained multi-project scheduling problem. Paper presented at the 2007 International Conference on Computational Intelligence and Security (CIS 2007).
Lova, A., & Tormos, P. (2001). Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling. Annals of Operations Research, 102(1), 263-286. doi:10.1023/A:1010966401888
Maroto, C., Tormos, P., & Lova, A. (1999). The evolution of software quality in project scheduling. In J. Węglarz (Ed.), Project Scheduling: Recent Models, Algorithms and Applications (pp. 239-259). Boston, MA: Springer US.
MMLIB. Retrieved from https://www.projectmanagement.ugent.be/research/data
MPSPLib. Retrieved from http://www.mpsplib.com/index.php
Özdamar, L., & Ulusoy, G. (1995). A survey on the resource-constrained project scheduling problem. Iie Transactions, 27, 574-586. doi:10.1080/07408179508936773
Payne, J. H. (1995). Management of multiple simultaneous projects: a state-of-the-art review. International Journal of Project Management, 13(3), 163-168. doi:https://doi.org/10.1016/0263-7863(94)00019-9
Pritsker, A. A. B., Waiters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: a zero-one programming approach. Management Science, 16(1), 93-108. doi:10.1287/mnsc.16.1.93
PSPLIB. Retrieved from http://www.om-db.wi.tum.de/psplib/getdata_mm.html
RCMPSPLIB. Retrieved from https://www.eii.uva.es/elena/RCMPSPLIB.htm
Sonmez, R., & Gürel, M. (2016). Hybrid optimization method for large-scale multimode resource-constrained project scheduling problem. Journal of Management in Engineering, 32(6), 04016020. doi:10.1061/(ASCE)ME.1943-5479.0000468
Sonmez, R., & Uysal, F. (2015). Backward-forward hybrid genetic algorithm for resource-constrained multiproject scheduling problem. Journal of Computing in Civil Engineering, 29(5), 04014072. doi:10.1061/(ASCE)CP.1943-5487.0000382
Van Peteghem, V., & Vanhoucke, M. (2014). An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research, 235(1), 62-72. doi:https://doi.org/10.1016/j.ejor.2013.10.012
Vázquez, E. P., Calvo, M. P., & Ordóñez, P. M. (2015). Learning process on priority rules to solve the rcmpsp. Journal of Intelligent Manufacturing, 26(1), 123-138. doi:10.1007/s10845-013-0767-5
Villafáñez, F., López-Paredes, A., & Pajares, J. (2014). From the rcpsp to the drcmpsp : methodological foundations.
Villafáñez, F., Poza, D., López-Paredes, A., Pajares, J., & Olmo, R. d. (2019). A generic heuristic for multi-project scheduling problems with global and local resource constraints (rcmpsp). Soft Computing, 23(10), 3465-3479. doi:10.1007/s00500-017-3003-y
Wauters, T., Kinable, J., Smet, P., Vancroonenburg, W., Vanden Berghe, G., & Verstichel, J. (2014). The multi-mode resource-constrained multi-project scheduling problem. Journal of Scheduling, 19, 1-13. doi:10.1007/s10951-014-0402-0
Yang, B., Geunes, J., & O'Brien, W. (2001). Resource-Constrained Project Scheduling: Past Work and New Directions1.
Zhang, H. (2012). Ant colony optimization for multimode resource-constrained project scheduling. Journal of Management in Engineering, 28(2), 150-159. doi:10.1061/(ASCE)ME.1943-5479.0000089
Bettemir Önder, H., & Sonmez, R. (2015). Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling. Journal of Management in Engineering, 31(5), 04014082. doi:10.1061/(ASCE)ME.1943-5479.0000323
Blazewicz, J., Lenstra, J. K., & Kan, A. H. G. R. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5(1), 11-24. doi:https://doi.org/10.1016/0166-218X(83)90012-4
Browning, T. R., & Yassine, A. A. (2010). Resource-constrained multi-project scheduling: Priority rule performance revisited. International Journal of Production Economics, 126(2), 212-228. doi:https://doi.org/10.1016/j.ijpe.2010.03.009
Chen, P.-H., & Shahandashti, S. (2009). Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction, 18, 434-443. doi:10.1016/j.autcon.2008.10.007
Cheng, M.-Y., & Prayogo, D. (2014). Symbiotic organisms search: A new metaheuristic optimization algorithm. Computers & Structures, 139, 98-112. doi:https://doi.org/10.1016/j.compstruc.2014.03.007
Cheng, M.-Y., Tran, D.-H., & Wu, Y.-W. (2014). Using a fuzzy clustering chaotic-based differential evolution with serial method to solve resource-constrained project scheduling problems. Automation in Construction, 37, 88-97. doi:https://doi.org/10.1016/j.autcon.2013.10.002
Gonçalves, J. F., Mendes, J. J. M., & Resende, M. G. C. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research, 189(3), 1171-1190. doi:https://doi.org/10.1016/j.ejor.2006.06.074
Habibi, F., Barzinpour, F., & Sadjadi, S. (2018). Resource-constrained project scheduling problem: review of past and recent developments. Journal of Project Management, 3, 55-88. doi:10.5267/j.jpm.2018.1.005
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. doi:https://doi.org/10.1016/j.ejor.2009.11.005
Herroelen, W., & Leus, R. (2005). Identification and illumination of popular misconceptions about project scheduling and time buffering in a resource-constrained environment. Journal of the Operational Research Society, 56(1), 102-109. doi:10.1057/palgrave.jors.2601813
Homberger, J. (2007). A multi-agent system for the decentralized resource-constrained multi-project scheduling problem. International Transactions in Operational Research, 14(6), 565-589. doi:https://doi.org/10.1111/j.1475-3995.2007.00614.x
Kannimuthu, M., Raphael, B., Ekambaram, P., & Kuppuswamy, A. (2020). Comparing optimization modeling approaches for the multi-mode resource-constrained multi-project scheduling problem. Engineering, Construction and Architectural Management, 27(4), 893-916. doi:10.1108/ECAM-03-2019-0156
Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), 320-333. doi:https://doi.org/10.1016/0377-2217(95)00357-6
Kolisch, R., & Drexl, A. (1997). Local search for nonpreemptive multi-mode resource-constrained project scheduling. Iie Transactions, 29(11), 987-999. doi:10.1023/A:1018552303415
Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis. In J. Węglarz (Ed.), Project Scheduling: Recent Models, Algorithms and Applications (pp. 147-178). Boston, MA: Springer US.
Kolisch, R., & Sprecher, A. (1997). PSPLIB - A project scheduling problem library: OR Software - ORSEP operations research software exchange program. European Journal of Operational Research, 96(1), 205-216. doi:https://doi.org/10.1016/S0377-2217(96)00170-1
Kurtulus, I., & Davis, E. W. (1982). Multi-project scheduling: categorization of heuristic rules performance. Management Science, 28(2), 161-172. Retrieved from https://EconPapers.repec.org/RePEc:inm:ormnsc:v:28:y:1982:i:2:p:161-172
Li, F., Xu, Z., & Li, H. (2021). A multi-agent based cooperative approach to decentralized multi-project scheduling and resource allocation. Computers & Industrial Engineering, 151, 106961. doi:https://doi.org/10.1016/j.cie.2020.106961
Li, K. Y., & Willis, R. J. (1992). An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research, 56(3), 370-379. doi:https://doi.org/10.1016/0377-2217(92)90320-9
Linyi, D., & Yan, L. (2007, 15-19 Dec. 2007). A particle swarm optimization for resource-constrained multi-project scheduling problem. Paper presented at the 2007 International Conference on Computational Intelligence and Security (CIS 2007).
Lova, A., & Tormos, P. (2001). Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling. Annals of Operations Research, 102(1), 263-286. doi:10.1023/A:1010966401888
Maroto, C., Tormos, P., & Lova, A. (1999). The evolution of software quality in project scheduling. In J. Węglarz (Ed.), Project Scheduling: Recent Models, Algorithms and Applications (pp. 239-259). Boston, MA: Springer US.
MMLIB. Retrieved from https://www.projectmanagement.ugent.be/research/data
MPSPLib. Retrieved from http://www.mpsplib.com/index.php
Özdamar, L., & Ulusoy, G. (1995). A survey on the resource-constrained project scheduling problem. Iie Transactions, 27, 574-586. doi:10.1080/07408179508936773
Payne, J. H. (1995). Management of multiple simultaneous projects: a state-of-the-art review. International Journal of Project Management, 13(3), 163-168. doi:https://doi.org/10.1016/0263-7863(94)00019-9
Pritsker, A. A. B., Waiters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: a zero-one programming approach. Management Science, 16(1), 93-108. doi:10.1287/mnsc.16.1.93
PSPLIB. Retrieved from http://www.om-db.wi.tum.de/psplib/getdata_mm.html
RCMPSPLIB. Retrieved from https://www.eii.uva.es/elena/RCMPSPLIB.htm
Sonmez, R., & Gürel, M. (2016). Hybrid optimization method for large-scale multimode resource-constrained project scheduling problem. Journal of Management in Engineering, 32(6), 04016020. doi:10.1061/(ASCE)ME.1943-5479.0000468
Sonmez, R., & Uysal, F. (2015). Backward-forward hybrid genetic algorithm for resource-constrained multiproject scheduling problem. Journal of Computing in Civil Engineering, 29(5), 04014072. doi:10.1061/(ASCE)CP.1943-5487.0000382
Van Peteghem, V., & Vanhoucke, M. (2014). An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research, 235(1), 62-72. doi:https://doi.org/10.1016/j.ejor.2013.10.012
Vázquez, E. P., Calvo, M. P., & Ordóñez, P. M. (2015). Learning process on priority rules to solve the rcmpsp. Journal of Intelligent Manufacturing, 26(1), 123-138. doi:10.1007/s10845-013-0767-5
Villafáñez, F., López-Paredes, A., & Pajares, J. (2014). From the rcpsp to the drcmpsp : methodological foundations.
Villafáñez, F., Poza, D., López-Paredes, A., Pajares, J., & Olmo, R. d. (2019). A generic heuristic for multi-project scheduling problems with global and local resource constraints (rcmpsp). Soft Computing, 23(10), 3465-3479. doi:10.1007/s00500-017-3003-y
Wauters, T., Kinable, J., Smet, P., Vancroonenburg, W., Vanden Berghe, G., & Verstichel, J. (2014). The multi-mode resource-constrained multi-project scheduling problem. Journal of Scheduling, 19, 1-13. doi:10.1007/s10951-014-0402-0
Yang, B., Geunes, J., & O'Brien, W. (2001). Resource-Constrained Project Scheduling: Past Work and New Directions1.
Zhang, H. (2012). Ant colony optimization for multimode resource-constrained project scheduling. Journal of Management in Engineering, 28(2), 150-159. doi:10.1061/(ASCE)ME.1943-5479.0000089
Downloads
Published
2022-04-27
How to Cite
Hodianto, V. A., & I-Tung, Y. (2022). MULTI-MODE RESOURCE CONSTRAINED MULTI PROJECT SCHEDULING PROBLEM OPTIMIZATION WITH SYMBIOTIC ORGANISMS SEARCH. Dimensi Utama Teknik Sipil, 9(1), 77–96. https://doi.org/10.9744/duts.9.1.77-96
Issue
Section
Articles
