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 number 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 considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 - (1/m) and 2. When both centers have m machines, a heuristic 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 provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.