|
|||||
|
|
Scheduling jobs with release dates on parallel batch processing machines |
|
| Authors: | L.L. Liu T.C.E. Cheng |
| Affiliation: | a Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China b School of Science, Shanghai Second Polytechnic University, No.2360 Jinhai Road, Pudong, Shanghai 201209, China |
| 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. |
| Keywords: | Scheduling Release dates Parallel batch processing machines Computational Complexity PTAS |
| 本文献已被 ScienceDirect 等数据库收录！ | |