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, Agconstructs 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 Agis 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.
Original language | English |
---|---|
Pages (from-to) | 109-123 |
Number of pages | 15 |
Journal | Journal of Scheduling |
Volume | 3 |
Issue number | 2 |
Publication status | Published - 1 Dec 2000 |
Keywords
- Approximation scheme
- Batching
- Parallel machine scheduling
ASJC Scopus subject areas
- Software
- General Engineering
- Management Science and Operations Research
- Artificial Intelligence