Please use this identifier to cite or link to this item:
Title: Single-machine batch scheduling with job processing time compatibility
Authors: Li, SS
Cheng, TCE 
Ng, CT 
Yuan, JJ
Keywords: Batch machine
Release date
Approximation algorithm
Issue Date: 2015
Publisher: Elsevier
Source: Theoretical computer science, 2015, v. 583, p. 57-66 How to cite?
Journal: Theoretical computer science 
Abstract: We consider scheduling problems with job processing time compatibility on a single unbounded batch machine. Each job's processing time is characterized by an interval. Any number of jobs can be processed in a batch under the condition that the processing time intervals of the jobs in the same batch have a nonempty intersection. The processing time of a batch is given by the left endpoint of the intersection of the processing time intervals of the jobs in the batch. For the makespan minimization problem with individual job release dates, we design a pseudo-polynomial dynamic programming algorithm for the case where the number of distinct release dates is fixed. We also present a class of online algorithms that are 2-competitive and a polynomial-time approximation scheme for the case where the number of release dates is arbitrary. For the problem to minimize the weighted number of tardy jobs under a common due date, we show that it is binary NP-hard and provide a polynomial-time algorithm when the jobs have a common weight.
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2015.03.043
Appears in Collections:Journal/Magazine Article

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

Page view(s)

Last Week
Last month
Checked on Jul 16, 2017

Google ScholarTM



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