PERFORMANCE OF SCHEDULING ALGORITHMS FOR NO-WAIT FLOWSHOPS WITH PARALLEL MACHINES

We study the performance of scheduling algorithms for a manufacturing system, called the 'no-wait flowshop', which consists of a certain num ber of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center . The problem of finding the minimum finish time schedule is considere d here in a flowshop consisting of two machine centers. Heuristic algo rithms are presented and are analyzed in the worst case performance co ntext. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guar antees of 3 - (1/m) and 2. When both centers have m machines, a heuris tic is presented with an upper bound performance guarantee of 8/3 - 2/ (3m). It is also shown that this bound can be reduced to 2(1 + epsilon ). For the flowshop with any number of machines in each center, we pro vide a heuristic algorithm with an upper bound performance guarantee t hat depends on the relative number of machines in the centers.