Evaluating typical algorithms of combinatorial optimization to solve continuous-time based scheduling problem (Q2331454)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Evaluating typical algorithms of combinatorial optimization to solve continuous-time based scheduling problem |
scientific article |
Statements
Evaluating typical algorithms of combinatorial optimization to solve continuous-time based scheduling problem (English)
0 references
29 October 2019
0 references
Summary: 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.
0 references
RCPSP
0 references
combinatorial optimization
0 references
scheduling
0 references
linear programming
0 references
MES
0 references
job shop
0 references