Flowshop scheduling with limited temporary storage

Abstract

We examine the problem of scheduling 2-machine flowshops in order to minimize makespan, using a limited amount of intermediate storage buffers. Although there are efficient algorithms for the extreme cases of zero and infinite buffer capacities, it is shown that all the intermediate (finite-capacity) cases are NP-complete. Exact bounds are proved for the relative improvement of execution times when a given buffer capacity is used. An efficient heuristic for solving the I-buffer problem is also analyzed, and it is shown that it has a ~ worst-case performance. Furthermore, it is shown that the "no-wait" (i.e., zero buffer) flowsbop scheduling problem with four machines is NP-complete. This partly settles a well-known open question, although the 3-machine case is left open here.