Preeti Malakar, Thomas George, et al.
SC 2012
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.
Preeti Malakar, Thomas George, et al.
SC 2012
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine