The paper describes a modified genetic algorithm for solving resource-constrained project scheduling problem. The relevance of the study is due to the widespread prevalence of project organization of activities and the extremely high computational complexity of the problem under consideration. Further improvement of existing heuristic algorithms is needed to enable efficient planning of large projects. The available genetic algorithms are based on activity order encoding methods and implementations of genetic operators, which does not fully take into account the specifics of the problem. Therefore, the paper proposes an alternative encoding method and the corresponding crossover operator, which, unlike classical approaches, highlights relative rather than absolute positions of activities as inherited features. The study regards the main properties of such encoding which can be represented as square Boolean matrices. A mapping operator that helps to reduce Boolean matrices to a canonical row form is also introduced. The resulting genetic algorithm and classical implementations were compared using a test set of tasks. The suggested approach has shown potential efficiency, especially with large projects. The findings can be of practical importance in the development of decision support systems for project management.
1. Artigues C. The Resource-Constrained Project Scheduling Problem. In: Artigues C., Demassey S., Neron E. (eds.). Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. Hoboken: ISTE; 2008:21–35. DOI:10.1002/9780470611227.ch1.
2. Kolisch R., Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling. European Journal of Operational Research. 2006;174(1):23–37. DOI:10.1016/j.ejor.2005.01.065.
3. Pellerin R. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research. 2020;280(2):395–416. DOI:10.1016/j.ejor.2019.01.063.
4. Kolisch R., Hartmann S. Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis. In: Węglarz J. (eds.). Project Scheduling. Boston, MA: Springer; 1999:147–178. DOI:10.1007/978-1-4615-5533-9_7.
5. Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics. 1998;45:733–750. DOI:10.1109/ICMLC.2005.1527446.
6. Kim J., Ellis R. Comparing Schedule Generation Schemes in Resource-Constrained Project Scheduling Using Elitist Genetic Algorithm. Journal of Construction Engineering and Management. 2010;136(2):160–169. DOI:10.1061/(ASCE)0733-9364(2010)136:2(160).
7. Zatsarinnyi A.A., Korotkov V.V., Matveev M.G. Modeling the process of network planning of a portfolio of projects with heterogeneous resources under fuzziness. Informatika i ee primeneniya = Informatics and its Applications. 2019;13(2):92–99. DOI:10.14357/19922264190213. (In Russ.)
8. Korotkov V.V., Matveev M.G. Individual Scheduling for the Multi-Mode Resource-Constrained Multi-Project Scheduling Problem. In: Becker J., Matveev M., Taratukhin V. (eds.). Proceedings of the 1st International Conference of Information Systems and Design. 2019. Available by: http://ceur-ws.org/Vol-2570/paper5.pdf.
9. Altenberg L. The Schema Theorem and Price's Theorem. Foundations of Genetic Algorithms. 1995;3:23–49. DOI:10.1016/B978-1-55860-356-1.50006-6.
10. Kolisch R., Sprecher A. PSPLIB – A project scheduling library. European Journal of Operational Research. 1996;96(1):205–216. DOI:10.1016/S0377-2217(96)00170-1.
Korotkov Vladislav Vladimirovich
ORCID |
Voronezh State University
Voronezh, Russian Federation
