Two-stage planning tasks for the flow line

The problem is formulated of constructing schedules of the two-stage processing of large number of products on two machine systems arranged into a sequential chain, keeping the same sequence for all products. The number of machines at each stage of processing can be different. None of the operations performed allows for interruptions during its execution. Post-processing time losses after completion of the 1st stage of manufacturing are also taken into account. As the optimality criterion, the implementation of the whole range of work in the shortest possible time is considered. Estimates are obtained of the lower bound of the optimal sequence of products processing, ensuring the implementation of all works at two stages of the processing in the shortest possible time. Algorithms are proposed of the exact and the approximate solution of the problem by the branch and bound method and the dynamic programming method, as well as a heuristic algorithm of polynomial complexity for obtaining the approximate solutions. The decision algorithms are illustrated with a numerical example. The results obtained can be widely used in work scheduling systems for the production sectors and workshops of machine-building and instrument-making production, as well as for the processes in woodworking, electronics and light industry.