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 3/2. (C) 2013 Elsevier B.V. All rights reserved.
approximation algorithm open shop worst-case analysis