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

The paper studies 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 binding the minijum finish time schedule is considered here in a flowshop conisting 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 heuritics are presented with tight performance guarantees of and 2. When both centers have m machines, a heuritic is presented with an upper bound performance guarantee of It is also shown that this bound can be reduced to . For the flowshop with any number of machines in each center, the paper provides a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.