Performance of scheduling algorithms for no-wait flowshops with parallel machines (Q1310022)

The paper deals with particular cases of a no-wait flowshop problem with parallel machines. The general problem consists in scheduling a set of jobs \(\{1,\dots,n\}\) when processing of the \(i\)th job requires time \(p(i,j)\) at each machine center \(j\), \(1\leq j\leq k\) of the flowshop. Machine center \(j\) of the flowshop has \(m(j)\geq 1\) parallel machines. There is considered that each job has to be processed sequentially starting with cetner 1 and ending at the \(k\)th center. The job must be processed continuously from the beginning of its processing without any interruption on machines and without any waiting between the centers. The object is to find the minimum finish time schedule. The author presents worst case analyses of two heuristics for a flowshop problem with two centers when \(m(1)=1\) and \(m(2)>1\) and proves that the found upper bounds of the ratio \(f/f^*\) are the best possible. (The values \(f\) and \(f^*\) are objective function values of a feasible and optimal schedule respectively.) Similarly, worst case analyses of two another heuristics solving a flowshop problem with two centers for the case when \(m(1)= m(2)>1\) were done and their upper bounds \(f/f^*\) were found. The last part of the paper comprises a description and worst case performance analysis of a heuristic algorithm for a two center flowshop problem with \(m(1)>1\) and \(m(2)>1\).