Complexity of two dual criteria scheduling problems

Yumei Huo, J. Y.T. Leung, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


In this article we answer the complexity question of two dual criteria scheduling problems which had been open for a long time. We show that both problems are binary NP-hard.

Original languageEnglish (US)
Pages (from-to)211-220
Number of pages10
JournalOperations Research Letters
Issue number2
StatePublished - Mar 2007

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


  • Dual criteria
  • NP-hard
  • Single machine


Dive into the research topics of 'Complexity of two dual criteria scheduling problems'. Together they form a unique fingerprint.

Cite this