46514

Автор(ы): 

Автор(ов): 

3

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

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

Статья в журнале/сборнике

Название: 

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

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

Да

ISBN/ISSN: 

1999-4893

DOI: 

10.3390/a11040050

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

  • Algorithms

Обозначение и номер тома: 

No.11(4)

Город: 

  • Bazel, Швейцария

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

  • MDPI

Год издания: 

2018

Страницы: 

http://www.mdpi.com/1999-4893/11/4/50
Аннотация
We consider one approach to formalize the Resource-Constrained Project Scheduling Problem (RCPSP) in terms of combinatorial optimization theory. The transformation of the original 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 meeting additional restrictions. The simplest case of continuous-time scheduling assumes one-to-one correspondence of resources and operations and corresponds to the linear programming problem setting. However, real scheduling problems include many-to-one relations which leads to the additional combinatorial component in the formulation due to operations competition. We research how to apply several typical algorithms to solve the resulted combinatorial optimization problem: enumeration including branch-and-bound method, gradient algorithm, random search technique.

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

Лазарев А.А., Некрасов И.В., Правдивец Н.А. Evaluating Typical Algorithms of Combinatorial Optimization to Solve Continuous-Time Based Scheduling Problem // Algorithms. 2018. No.11(4). С. http://www.mdpi.com/1999-4893/11/4/50.