Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21097
Title: Parallel machine batching and scheduling with deadlines
Authors: Cheng, TCE 
Kovalyov, MY
Keywords: Approximation scheme
Batching
Parallel machine scheduling
Issue Date: 2000
Publisher: Springer
Source: Journal of scheduling, 2000, v. 3, no. 2, p. 109-123 How to cite?
Journal: Journal of scheduling 
Abstract: In this paper, we study the problem of scheduling n independent jobs non-preemptively on m unrelated parallel machines. Each job j has a processing time and a deadline, the time at which the job must be completed. On each machine, jobs may be grouped to form batches containing continuously scheduled jobs. For each batch, a constant set-up time is needed before the first job of the batch is processed. The completion time of each job in a batch is equal to the time when the latest job in the batch has finished its processing. A schedule stipulates the sequence of batches on each machine. The objective is to find a schedule which is feasible with respect to the deadlines assuming one exists. We note that the problem is strongly NP- complete, establish a number of useful properties of a feasible schedule and present a dynamic programming algorithm and a family of approximation algorithms {Ag}. For any ε > 0, Ag constructs a schedule in which the completion times of each job is at most (1 + ε) times the value of its deadline if there exists a feasible schedule with respect to the deadlines. The time complexity of Ag is O(n2m + 1/εm). We prove that the problem with identical jobs and uniform machines, unlike its polynomially solvable classical counterpart, in which the set-up time is zero, is strongly NP-complete. We also show that this problem is solvable in O(m2n2m + 1) time, while the problem with identical machines and identical set-up and job processing times is solvable in O(n log n) time.
URI: http://hdl.handle.net/10397/21097
ISSN: 1094-6136
EISSN: 1099-1425
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

13
Last Week
0
Last month
Citations as of May 14, 2018

Page view(s)

77
Last Week
0
Last month
Citations as of May 20, 2018

Google ScholarTM

Check


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