[en] The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for these tasks on a single processor? This result establishes a sharp borderline between NP-complete and polynomially solvable versions of this problem with respect to the parameters \tau and k.
Disciplines :
Production, distribution & supply chain management Quantitative methods in economics & management
Author, co-author :
Crama, Yves ; Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Spieksma, Frits C.R.
Language :
English
Title :
The complexity of scheduling short tasks with few starting times
