2008.

abstract bibtex

abstract bibtex

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 \textgreater b, 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 7/5.

@unpublished{simonin_theoretical_2008, title = {Theoretical study of the isomorphic coupled-task scheduling problem with compatibility constrainsts.(rejected on {STACS} 2009)}, 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 {\textgreater} b, 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 7/5.}, author = {Simonin, Gilles and Darties, Benoit and Giroudeau, R. and {Jean-Claude Koenig}}, year = {2008}, keywords = {approximation algorithms, complexity, coupled-tasks, graph, review, scheduling} }

Downloads: 0