Concurrent flowshop scheduling to minimize makespan

This paper considers the concurrent flowshop scheduling problem with the makespan objective function. In this problem each job consists of several components each of which is processed on a dedicated flowshop. Equivalently, each component requires a series of consecutive operations in a prespecified order as in the standard serial flowshop. We assume that each component has the same number of indexed operations and that these operations must be processed in the same order for each component. We first show that this problem is strongly NP-hard and then, using compact vector summation techniques, we construct schedules using a quadratic time heuristic with an absolute performance guarantee independent of the number of jobs. This makes our schedules asymptotically optimal as the number of jobs becomes very large.