Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/32065
Title: Scheduling jobs with agreeable processing times and due dates on a single batch processing machine
Authors: Liu, LL
Ng, CT 
Cheng, TCE 
Keywords: Agreeable
Batch processing
Scheduling
Issue Date: 2007
Publisher: Elsevier
Source: Theoretical computer science, 2007, v. 374, no. 1-3, p. 159-169 How to cite?
Journal: Theoretical computer science 
Abstract: In this paper we study the problems of scheduling jobs with agreeable processing times and due dates on a single batch processing machine to minimize total tardiness, and weighted number of tardy jobs. We prove that the problem of minimizing total tardiness is NP-hard even if the machine capacity is two jobs and we develop a pseudo-polynomial-time algorithm for an NP-hard special case of this problem. We also develop a pseudo-polynomial-time algorithm for the NP-hard problem of minimizing weighted number of tardy jobs, which suggests that this problem cannot be strongly NP-hard unless P=NP.
URI: http://hdl.handle.net/10397/32065
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2006.12.039
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

12
Last Week
0
Last month
0
Citations as of Sep 24, 2017

WEB OF SCIENCETM
Citations

8
Last Week
0
Last month
0
Citations as of Sep 21, 2017

Page view(s)

49
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.