Isomorphic Coupled Scheduling Problem for a Torpedo

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 its two sub-tasks. We prove NP-completeness of the minimization of the schedule length, and 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+\sqrt{3})/2.
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2011, 14 (5), pp.501-509
Liste complète des métadonnées
Contributeur : Rodolphe Giroudeau <>
Soumis le : vendredi 29 juin 2012 - 12:17:54
Dernière modification le : mardi 6 février 2018 - 15:56:16


  • HAL Id : lirmm-00713106, version 1



Rodolphe Giroudeau, Benoit Darties, Gilles Simonin, Jean-Claude König. Isomorphic Coupled Scheduling Problem for a Torpedo. Journal of Scheduling, Springer Verlag, 2011, 14 (5), pp.501-509. 〈lirmm-00713106〉



Consultations de la notice