Minimizing total completion time on uniform machines with deadline constraints

Teofilo F. Gonzalez, Joseph Y.T. Leung, Michael Pinedo

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Σ Cj. In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt, d̄j | Σ Cj. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

Original languageEnglish (US)
Pages (from-to)95-115
Number of pages21
JournalACM Transactions on Algorithms
Issue number1
StatePublished - 2006

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)


  • Deadline constraints
  • Mean flow time
  • Polynomial-time algorithms
  • Uniform machines


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

Cite this