6533b7dcfe1ef96bd1273410

RESEARCH PRODUCT

Approximation algorithm for constrained coupled-tasks scheduling problem

Jean-claude KönigRodolphe GiroudeauBenoit DartiesGilles Simonin

subject

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.

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01101208