Approximation algorithms for parallel open shop scheduling

This paper investigates the parallel open shop scheduling problem. In this problem each job consists of two independent operations, which must be non-preemptively processed by one of m parallel identical two-machine open shops. The objective is to minimize the makespan. Because of NP-hardness, we provide polynomial time approximation algorithms for the problem. If there are m   open shops, our algorithm has a worst case ratio of 2. If only two open shops are valid, it can be improved to 32.

► We introduce a new combination of parallel-machine scheduling model and open shop scheduling model, namely the parallel open shop.
► In this model each job consists of two independent operations, which must be non-preemptively processed by one of m   parallel identical two-machine open shops.
► For the problem of minimizing the makespan, we design and analyze approximation algorithms for both the case of m=2m=2 and the general m  -machine case.
► The worst case ratio is shown to be 32 and 2, respectively.