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.

MoreLess

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 |

More access options

www.worldscinet.com

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Extent:	application/pdf text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10004963998