A multiple-criterion model for machine scheduling

Kenneth R. Baker, J. Cole Smith

Research output: Contribution to journalArticle

256 Scopus citations

Abstract

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
Volume6
Issue number1
DOIs
StatePublished - Jan 1 2003
Externally publishedYes

Keywords

  • Complexity
  • Multiple criteria
  • Sequencing
  • Single machine

ASJC Scopus subject areas

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

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

  • Cite this