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

Jianfeng Ren (), Yuzhong Zhang and Guo Sun
Additional contact information
Jianfeng Ren: College of Operations Research and Management Sciences, Qufu Normal University, Shangdong, 276826, China
Yuzhong Zhang: Department of Mathematics, Qufu Normal University, Shangdong, 276826, China
Guo Sun: Department of Mathematics, Qufu Normal University, Shangdong, 276826, China

Asia-Pacific Journal of Operational Research (APJOR), 2009, vol. 26, issue 03, 351-363

Abstract: We consider the problem of minimizing the total late work$(\sum_{j=1}^{n}\, V_j)$on an unbounded batch processing machine, whereVj=min{Tj, pj}andTj=max{Cj- dj, 0}. The batch processing machine can process up toB (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.

Keywords: Scheduling; batching machine; late work; NP-hardness (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595909002249
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:26:y:2009:i:03:n:s0217595909002249

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595909002249

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().