Abstract | ||
---|---|---|
We consider the problem of minimizing the total late work (Sigma(n)(j=1) V-j) on an unbounded batch processing machine, where V-j = min{T-j, p(j)} and T-j = max{C-j-d(j), 0}. The batch processing machine can process up to B (B >= n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time, respectively. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we prove that the problem 1 vertical bar B >= n vertical bar Sigma(n)(j=1) V-j is NP-hard. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1142/S0217595909002249 | ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH |
Keywords | Field | DocType |
Scheduling,batching machine,late work,NP-hardness | Scheduling (computing),Real-time computing,Mathematics,Batch processing machine | Journal |
Volume | Issue | ISSN |
26 | 3 | 0217-5959 |
Citations | PageRank | References |
6 | 0.52 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jianfeng Ren | 1 | 291 | 16.97 |
Yuzhong Zhang | 2 | 252 | 25.71 |
Guo Sun | 3 | 6 | 1.20 |