A multiple-criterion model for machine scheduling

Kenneth R. Baker, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

310 Scopus citations


We consider a scheduling problem involving a single processor being utilized by two or more customers. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated based on their individual criteria. We examine three basic scheduling criteria: minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. Although determining a minimum-cost schedule according to any one of these criteria is polynomially solvable, we demonstrate that when minimizing a mix of these criteria, the problem becomes NP-hard.

Original languageEnglish (US)
Pages (from-to)7-16
Number of pages10
JournalJournal of Scheduling
Issue number1
StatePublished - Jan 2003
Externally publishedYes


  • Complexity
  • Multiple criteria
  • Sequencing
  • Single machine

ASJC Scopus subject areas

  • Software
  • General Engineering
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'A multiple-criterion model for machine scheduling'. Together they form a unique fingerprint.

Cite this