Модифицированный генетический алгоритм построения расписания проекта
Работая с нашим сайтом, вы даете свое согласие на использование файлов cookie. Это необходимо для нормального функционирования сайта, показа целевой рекламы и анализа трафика. Статистика использования сайта отправляется в «Яндекс» и «Google»
Научный журнал Моделирование, оптимизация и информационные технологииThe scientific journal Modeling, Optimization and Information Technology
cетевое издание
issn 2310-6018

Модифицированный генетический алгоритм построения расписания проекта

idКоротков В.В.

УДК 519.85
DOI: 10.26102/2310-6018/2022.38.3.007

  • Аннотация
  • Список литературы
  • Об авторах

В работе описывается модифицированный генетический алгоритм решения задачи составления расписания выполнения проекта с учетом ресурсных ограничений. Актуальность исследования обусловлена обширной распространенностью проектной формы организации деятельности и крайне высокой вычислительной сложностью рассматриваемой задачи, что требует дальнейшего улучшения существующих эвристических алгоритмов для возможности эффективного планирования крупных проектов. Имеющиеся генетические алгоритмы основаны на методах кодирования порядка работ и реализациях генетических операторов, которые слабо учитывают особенности задачи. В связи с этим предлагается использование альтернативного метода кодирования и соответствующего оператора кроссовера, которые, в отличие от классических подходов, позволяют вычленять в качестве наследуемых признаков относительные, а не абсолютные положения работ. В работе рассматриваются основные свойства подобного кодирования, представимого в виде квадратных булевых матриц. Представлен оператор отображения, позволяющий привести булевы матрицы к каноническому строчному виду. Было проведено сравнение полученного генетического алгоритма и классических реализаций на тестовой выборке задач. Предложенные подходы продемонстрировали потенциальную эффективность, особенно при планировании крупных проектов. Результаты работы могут представлять практическую ценность при разработке систем поддержки принятия решений в проектном менеджменте.

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 |

Воронежский государственный университет

Воронеж, Российская федерация

Ключевые слова: генетический алгоритм, оператор кроссовера, планирование проекта, комбинаторная оптимизация, теория расписаний

Для цитирования: Коротков В.В. Модифицированный генетический алгоритм построения расписания проекта. Моделирование, оптимизация и информационные технологии. 2022;10(3). Доступно по: https://moitvivt.ru/ru/journal/pdf?id=1214 DOI: 10.26102/2310-6018/2022.38.3.007

247

Полный текст статьи в PDF

Поступила в редакцию 19.07.2022

Поступила после рецензирования 23.08.2022

Принята к публикации 07.09.2022

Опубликована 08.09.2022