Cover Image

THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE

We consider the problem of minimizing the total late work $(\sum_{j=1}^{n}\, V_j)$ on an unbounded batch processing machine, where Vj = min {Tj, pj} and Tj = max {Cj - dj, 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|B \geq n|\sum_{j=1}^{n}V_j$ is NP-hard.
Year of publication:
2009
Authors: REN, JIANFENG ; ZHANG, YUZHONG ; SUN, GUO
Published in:
Asia-Pacific Journal of Operational Research (APJOR). - World Scientific Publishing Co. Pte. Ltd., ISSN 1793-7019. - Vol. 26.2009, 03, p. 351-363
Publisher: World Scientific Publishing Co. Pte. Ltd.
Subject: Scheduling | batching machine | late work | NP-hardness
Check full text access |
Extent:
application/pdf
text/html
Type of publication: Article
Source:
Similar items by subject
Similar items by person