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 $\frac{3}{2}$ .