Fan Jing Meng, Ying Huang, et al.
ICEBE 2007
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. © 2005 INFORMS.
Fan Jing Meng, Ying Huang, et al.
ICEBE 2007
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
S.M. Sadjadi, S. Chen, et al.
TAPIA 2009
Zohar Feldman, Avishai Mandelbaum
WSC 2010