A framework for the complexity of high-multiplicity scheduling problems

N. Brauner, Y. Crama, A. Grigoriev, J. Van De Klundert

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive complexity measures for the analysis of algorithms which produce "large" outputs. However, different classes emerge according as we look at schedules as sets of starting times, or as related single-valued mappings.

Original languageEnglish
Pages (from-to)313-323
Number of pages11
JournalJournal of Combinatorial Optimization
Issue number3
StatePublished - May 2005
Externally publishedYes


  • Computational complexity
  • Design of algorithms
  • High multiplicity
  • Scheduling


Dive into the research topics of 'A framework for the complexity of high-multiplicity scheduling problems'. Together they form a unique fingerprint.

Cite this