Eprint first made available on ORBi (E-prints, working papers and research blog)
The complexity of scheduling short tasks with few starting times
Crama, Yves; Spieksma, Frits C.R.
1992
 

Files


Full Text
ShortTasksFewStartTimes.pdf
Author preprint (4.93 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
scheduling; complexity; discrete starting times
Abstract :
[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
Publication date :
1992
Available on ORBi :
since 15 January 2013

Statistics


Number of views
128 (2 by ULiège)
Number of downloads
69 (0 by ULiège)

Bibliography


Similar publications



Sorry the service is unavailable at the moment. Please try again later.
Contact ORBi