|
|||||
|
|
The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan |
|
| Authors: | J J Yuan Z H Liu C T Ng T C E Cheng |
| Affiliation: | a Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China b Department of Mathematics, East China University of Science and Technology, Shanghai 200237, People's Republic of China c Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, People's Republic of China |
| Abstract: | In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)m) time dynamic programming algorithm and an O(mkk+1P2k?1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem. |
| Keywords: | Scheduling Family Batching Makespan |
| 本文献已被 ScienceDirect 等数据库收录！ | |