Please use this identifier to cite or link to this item:
Title: Parallel machine batching and scheduling with deadlines
Authors: Cheng, TCE 
Kovalyov, MY
Keywords: Approximation scheme
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.
ISSN: 1094-6136
EISSN: 1099-1425
Appears in Collections:Journal/Magazine Article

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


Last Week
Last month
Citations as of Dec 13, 2018

Page view(s)

Last Week
Last month
Citations as of Dec 9, 2018

Google ScholarTM


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