Performance of scheduling algorithms for no-wait flowshops with parallel machines Academic Article uri icon

abstract

  • 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 + ε{lunate}). 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. © 1993.

author list (cited authors)

  • Sriskandarajah, C.

citation count

  • 29

complete list of authors

  • Sriskandarajah, C

publication date

  • November 1993