Schedules for performing tasks in interconnected sequential production systems

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.