Minimizing total completion time on parallel machines with deadline constraints

Joseph Y.T. Leung, Michael Pinedo

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Consider n independent jobs and m identical machines in parallel. Job j has a processing time pj and a deadline d̄j. It must complete its processing before or at its deadline. All jobs are available for processing at time t = 0 and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines; such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time Σ Cj. In the classical α |β| γ scheduling notation this problem is referred to as P |prmt, d̄j| Σ Cj. Lawler (Recent Results in the Theory of Machine Scheduling, in Mathematical Programming: The State of the Art, A. Bachem, M. Grötschel, and B. Korte, eds., Springer, Berlin, 1982, pp. 202-234) raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every m ≥ 2, and we show that the more general problem with m unrelated machines, i.e., R |prmt, d̄j| Σ Cj, is strongly NP-hard.

Original languageEnglish (US)
Pages (from-to)1370-1388
Number of pages19
JournalSIAM Journal on Computing
Issue number5
StatePublished - Aug 2003

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Deadline constraints
  • Maximum lateness
  • Parallel and identical machines
  • Polynomial-time algorithm
  • Preemptive scheduling
  • Total completion time
  • Unrelated machines


Dive into the research topics of 'Minimizing total completion time on parallel machines with deadline constraints'. Together they form a unique fingerprint.

Cite this