Flowshop scheduling with dominant machines (Q1342341)

This paper considers two special cases of the permutation flowshop scheduling problem: the flowshop with an increasing series of dominating machines \((M_1\prec M_2\prec\cdots\prec M_m)\) and the flowshop with a decreasing series of dominating machines \((M_1\succ M_2\succ\cdots\succ M_m)\). Machine \(a\) dominates machines \(b\) \((M_a\succ M_b)\) if \(\min\{t(i, a)\mid i\in \mathbb{N}\}\geq \max\{t(i, b)\mid i\in \mathbb{N}\}\), where \(t(i, a)\), the processing time of job \(i\) on machine \(a\) and \(N= \{1,2,\dots, n\}\), set of all \(n\) jobs. The authors discuss these two special cases with the following objective functions: the maximum flowtime (makespan) \(C_{\max}\), the mean flowtime (equivalent to the sum of completion times of all jobs at the last machine \(\sum C_i\)), the sum of completion times of the last job of all machines \(\sum C_{[n]j}\), the total number of tardy jobs \(\sum U_i\), the maximum lateness \(L_{\max}\) or tardiness \(T_{\max}\). Based on the analysis of the special cases, simple polynomial-time algorithms are given.