| Article ID: | iaor20061247 |
| Country: | United States |
| Volume: | 30 |
| Issue: | 4 |
| Start Page Number: | 817 |
| End Page Number: | 831 |
| Publication Date: | Nov 2005 |
| Journal: | Mathematics of Operations Research |
| Authors: | Sviridenko Maxim, Bansal Nikhil, Mahdian Mohammad |
| Keywords: | job shop |
In this paper, we study polynomial time approximation schemes (PTASes) for the no-wait job shop scheduling problem with the makespan objective function. It is known that the problem is MaxSNP-hard in the case when each job is allowed to have three operations or more. We show that if each job has at most two operations, the problem admits a PTAS if the number of machines is a constant (i.e. not part of the input). If the number of machines is not a constant, we show that the problem is hard to approximate within a factor better than 5/4.