Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time

J.A. Hoogeveen, S.L. van de Velde

Research output: Contribution to journalArticleAcademicpeer-review

61 Citations (Scopus)
203 Downloads (Pure)

Abstract

We prove that the bicriteria single-machine scheduling problem of minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Our result settles a long-standing open problem.
Original languageEnglish
Pages (from-to)205-208
JournalOperations research letters
Volume17
Issue number5
DOIs
Publication statusPublished - 1995

    Fingerprint

Keywords

  • Single-machine scheduling
  • Bicriteria scheduling
  • Total completion time
  • Maximum cost
  • Maximum lateness

Cite this