42731

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Тезисы доклада

Название: 

Evaluating Typical Algorithms of Combinatorial Optimization to Solve Continuous-Time Based Scheduling Problem

Электронная публикация: 

Да

Наименование конференции: 

  • 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017, Petrovac, Montenegro)

Наименование источника: 

  • Proceedings of the 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017)

Город: 

  • Москва

Издательство: 

  • ВЦ им. А.А.Дородницына РАН

Год издания: 

2017

Страницы: 

93
Аннотация
This paper considers one approach to formalize the resource-constrained project scheduling problem (RCPSP) in terms of combinatorial optimiza- tion theory. The conversion of initial problem into combinatorial setting is based on interpreting each operation as an atomic entity that has a defined duration and has to be resided on the continuous time axis meet- ing additional restrictions The simplest case of continuous-time schedul- ing assumes one-to-one correspondence of resources and operations and equals to the linear programming problem setting. However real schedul- ing problems include many-to-one relations which leads to additional com- binatorial component in the formalization due to operations competition. We research how to apply typical algorithms to solve the resulted combi- natorial optimization problem: enumeration including branch-and-bound method, dynamic programming, greedy algorithms, genetic algorithms. The research ends with comparison of the results of the examined meth- ods

Библиографическая ссылка: 

Лазарев А.А., Некрасов И.В., Правдивец Н.А. Evaluating Typical Algorithms of Combinatorial Optimization to Solve Continuous-Time Based Scheduling Problem / Proceedings of the 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017). М.: ВЦ им. А.А.Дородницына РАН, 2017. С. 93.