Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard

Guohua Wan, Benjamin P.C. Yen, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

29 Citations (Scopus)


This article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard.
Original languageEnglish
Pages (from-to)273-280
Number of pages8
JournalInformation Processing Letters
Issue number6
Publication statusPublished - 30 Sep 2001
Externally publishedYes


  • Computational complexity
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this