| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428980 | Information Processing Letters | 2013 | 5 Pages |
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.
