caa a22 4500 445838744 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s10951-010-0193-x doi (NATIONALLICENCE)springer-10.1007/s10951-010-0193-x Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor [Elektronische Daten] [G. Simonin, B. Darties, R. Giroudeau, J.-C. König] 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 $\mathcal{NP}$-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 $(\frac{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$\frac {3}{2}$ and$\frac{5}{4}$. Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to$\frac{1+\sqrt{3}}{2}\approx 1.37$. Springer Science+Business Media, LLC, 2010 Coupled-tasks nationallicence Complexity nationallicence Compatibility graph nationallicence Polynomial-time approximation nationallicence Simonin G. LIRMM UMR 5506, rue Ada, 34392, Montpellier Cedex 5, France aut Darties B. LE2I UMR 5158, 9 Rue Alain Savary, 21000, Dijon, France aut Giroudeau R. LIRMM UMR 5506, rue Ada, 34392, Montpellier Cedex 5, France aut König J.-C LIRMM UMR 5506, rue Ada, 34392, Montpellier Cedex 5, France aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/5(2011-10-01), 501-509 1094-6136 14:5<501 2011 14 10951 https://doi.org/10.1007/s10951-010-0193-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0193-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Simonin G. LIRMM UMR 5506, rue Ada, 34392, Montpellier Cedex 5, France aut NATIONALLICENCE 700 1- Darties B. LE2I UMR 5158, 9 Rue Alain Savary, 21000, Dijon, France aut NATIONALLICENCE 700 1- Giroudeau R. LIRMM UMR 5506, rue Ada, 34392, Montpellier Cedex 5, France aut NATIONALLICENCE 700 1- König J.-C LIRMM UMR 5506, rue Ada, 34392, Montpellier Cedex 5, France aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/5(2011-10-01), 501-509 1094-6136 14:5<501 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer