В работе описывается модифицированный генетический алгоритм решения задачи составления расписания выполнения проекта с учетом ресурсных ограничений. Актуальность исследования обусловлена обширной распространенностью проектной формы организации деятельности и крайне высокой вычислительной сложностью рассматриваемой задачи, что требует дальнейшего улучшения существующих эвристических алгоритмов для возможности эффективного планирования крупных проектов. Имеющиеся генетические алгоритмы основаны на методах кодирования порядка работ и реализациях генетических операторов, которые слабо учитывают особенности задачи. В связи с этим предлагается использование альтернативного метода кодирования и соответствующего оператора кроссовера, которые, в отличие от классических подходов, позволяют вычленять в качестве наследуемых признаков относительные, а не абсолютные положения работ. В работе рассматриваются основные свойства подобного кодирования, представимого в виде квадратных булевых матриц. Представлен оператор отображения, позволяющий привести булевы матрицы к каноническому строчному виду. Было проведено сравнение полученного генетического алгоритма и классических реализаций на тестовой выборке задач. Предложенные подходы продемонстрировали потенциальную эффективность, особенно при планировании крупных проектов. Результаты работы могут представлять практическую ценность при разработке систем поддержки принятия решений в проектном менеджменте.
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. Зацаринный А.А., Коротков В.В., Матвеев М.Г. Моделирование процессов сетевого планирования портфеля проектов с неоднородными ресурсами. Информатика и её применения. 2019;13(2):92–99. DOI:10.14357/19922264190213.
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.
Коротков Владислав Владимирович
ORCID |
Воронежский государственный университет
Воронеж, Российская федерация
