A framework for the complexity of high-multiplicity scheduling problems

Abstract. 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