Reference : The complexity of scheduling short tasks with few starting times
E-prints/Working papers : First made available on ORBi
Business & economic sciences : Production, distribution & supply chain management
Business & economic sciences : Quantitative methods in economics & management
The complexity of scheduling short tasks with few starting times
Crama, Yves mailto [Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Spieksma, Frits C.R. []
University of Limburg
The Netherlands
[en] scheduling ; complexity ; discrete starting times
[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.

File(s) associated to this reference

Fulltext file(s):

Open access
ShortTasksFewStartTimes.pdfAuthor preprint4.82 MBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.