6533b7dcfe1ef96bd1273410
RESEARCH PRODUCT
Approximation algorithm for constrained coupled-tasks scheduling problem
Jean-claude KönigRodolphe GiroudeauBenoit DartiesGilles Simoninsubject
Rate-monotonic schedulingEarliest deadline first schedulingOptimizationBipartite graphMathematical optimizationOpen-shop schedulingSchedulesDistributed computingComplexity theoryProcessor schedulingDynamic priority schedulingApproximation methodscoupled-tasksFair-share schedulingApproximation algorithmsFixed-priority pre-emptive schedulingNurse scheduling problemTwo-level schedulingMathematics[ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]description
International audience; We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
year | journal | country | edition | language |
---|---|---|---|---|
2014-11-03 |