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
    0 references
    0 references
    0 references
    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

    Identifiers