Parallel machine batching and scheduling with deadlines

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)

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 languageEnglish
Pages (from-to)109-123
Number of pages15
JournalJournal of Scheduling
Volume3
Issue number2
Publication statusPublished - 1 Dec 2000

Keywords

  • Approximation scheme
  • Batching
  • Parallel machine scheduling

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this