On the complexity of high multiplicity scheduling problems
Brauner, Nadia ; Crama, Y. ; Grigoriev, A. ; Van De Klundert, J.
HAL, hal-00083365 / Harvested from HAL
Text on HAL
The purpose of this note is to propose a definition of several complexity classes which could prove useful for the analysis of high multiplicity scheduling problems. Part of this framework relies on previous work, aiming at the definition of output-sensitive complexity measures for the analysis of algorithms producing ``large'' outputs. However, the classes differ according as we look at schedules as sets of processing intervals, or as related (single-valued or set-valued) mappings.
Publié le : 2001-07-05
Classification:  complexité,  recherche opérationnelle,  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 
@article{hal-00083365,
     author = {Brauner, Nadia and Crama, Y. and Grigoriev, A. and Van De Klundert, J.},
     title = {On the complexity of high multiplicity scheduling problems},
     journal = {HAL},
     volume = {2001},
     number = {0},
     year = {2001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00083365}
}

Brauner, Nadia; Crama, Y.; Grigoriev, A.; Van De Klundert, J. On the complexity of high multiplicity scheduling problems. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-00083365/