|
|||||
|
|
A Framework for the Complexity of High-Multiplicity Scheduling Problems |
|
| Authors: | |
| Institution: | (1) Laboratoire Leibniz-IMAG, 46 avenue F’elix Viallet, 38031 Grenoble cedex, France;(2) HEC Management School, University of Liège, Boulevard du Rectorat 7 (B31), 4000 Liège, Belgium;(3) Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD, Maastricht, The Netherlands;(4) Department of Mathematics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands |
| 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. |
| Keywords: | computational complexity design of algorithms scheduling high multiplicity |
| 本文献已被 SpringerLink 等数据库收录！ | |