Flow-shops with a dominant machine (Q1203800)

Flow-shop problems with a dominant machine are considered. It is shown that for this kind of problems the search for an optimal schedule can be restricted to permutation schedules if the optimality criterion is regular. An expression for the completion time of a job with respect to a permutation schedule is given. Two fast algorithms for the weighted completion times and the maximal lateness criteria are suggested. It should be mentioned that similar questions were considered in many papers and their generalization was obtained before by \textit{V. A. Strusevich} [e.g., Izv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk 1982, No. 1, 28-33 (1982; Zbl 0505.90033)]. His results, including a polynomial-time algorithm for the weighted completion times, overlap with some results of the reviewed article and may be found also in the book of \textit{V. S. Tanaev}, \textit{Yu. N. Sotskov} and \textit{V. A. Strusevich} [``Scheduling theory. Multistage systems (Russian) (1989; Zbl 0673.90023)]. However, there are also merits in this article. A polynomial-time algorithm for an optimal schedule with respect to the maximal lateness criterion is suggested for the first time. A property of a flow-shop problem with more than one dominant machine is also considered.