×

zbMATH — the first resource for mathematics

On the properties of optimal schedules in the flow shop problem with interruptions and an arbitrary regular criterion. (Russian) Zbl 1249.90067
Summary: We study the properties of optimal solutions of the NP-hard flow shop scheduling problem with interruptions and an arbitrary regular objective function. We show that, for any particular problem under study, its optimal solution can be found by choosing appropriate job priority orders on each machine. The number of interruptions in such schedule is estimated from above. It is also shown that the length of the optimal schedule (for a specified regular criterion) is always equal to the total length of operations from a certain subset. The results of the paper significantly extend previously known results established for the flow shop problem with the minimum makespan objective.

MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite