| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420564 | Discrete Applied Mathematics | 2009 | 6 Pages |
Abstract
In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
L.L. Liu, C.T. Ng, T.C.E. Cheng,