RUS  ENG
Full version
JOURNALS // Problemy Upravleniya // Archive

Probl. Upr., 2020 Issue 5, Pages 71–80 (Mi pu1212)

Administration of engineering systems and technological processes

Schedules for performing tasks in interconnected sequential production systems

Yu. A. Zak


Abstract: The problem, which is classical in scheduling theory, of constructing a sequence of tasks execution on one machine under conditions of restrictions on the start and end times of tasks execution and which takes into account not only the time spent on equipment operation, but also the losses for post-processing, is considered for multistage production systems consisting of an interconnected chain of sections and workshops of an industrial enterprise. The criterion for the optimality of the task is the implementation of the multistage schedule in the shortest possible time. The problems considered in this paper belong to the class of NP-complete problems of exponential complexity. The properties of admissible and optimal task execution sequences are investigated. Methods for calculating the lower bound for the length of the optimal schedule and the rules for rejecting inadmissible and non-optimal extensions are proposed. Algorithms for the exact and approximate solution of the problem by modified branch and bound methods have been developed. The proposed algorithms are illustrated with numerical examples. The computational experiments performed by the author have shown that the presence of a system of strict restrictions on the timing of tasks when implementing the algorithms proposed in the paper in a number of cases significantly reduces the number of options under consideration.

Keywords: sequence of task execution, multistage schedule, minimum time, heuristic algorithm, lower bound of the optimality criterion, screening out unpromising continuations, branch and bound method.

UDC: 519.8

Received: 19.02.2020
Revised: 07.07.2020
Accepted: 16.07.2020

DOI: 10.25728/pu.2020.5.9



© Steklov Math. Inst. of RAS, 2025