Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor

Abstract : The problem presented in this paper is a generalization of the usual coupled-tasks scheduling problem in presence of compatibility constraints. The reason behind this study is the data acquisition problem for a submarine torpedo. We investigate a particular configuration for coupled tasks (any task is divided into two sub-tasks separated by an idle time), in which the idle time of a coupled task is equal to the sum of durations of its two sub-tasks. We prove -completeness of the minimization of the schedule length, we show that finding a solution to our problem amounts to solving a graph problem, which in itself is close to the minimum-disjoint-path cover (min-DCP) problem. We design a (3a+2b)/(2a+2b)-approximation, where a and b (the processing time of the two sub-tasks) are two input data such as a>b>0, and that leads to a ratio between 3/2 and 5/4. Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to 1.37 .
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2011, 14 (5), pp.501-509. 〈10.1007/s10951-010-0193-x〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00612822
Contributeur : Benoît Darties <>
Soumis le : mercredi 7 juin 2017 - 10:21:36
Dernière modification le : mardi 10 octobre 2017 - 13:48:52
Document(s) archivé(s) le : vendredi 8 septembre 2017 - 12:13:42

Fichiers

JOS-2011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gilles Simonin, Benoit Darties, Rodolphe Giroudeau, Jean-Claude König. Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. Journal of Scheduling, Springer Verlag, 2011, 14 (5), pp.501-509. 〈10.1007/s10951-010-0193-x〉. 〈hal-00612822v2〉

Partager

Métriques

Consultations de
la notice

121

Téléchargements du document

20