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

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 $\mathrm{𝒩𝒫}$ ‐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$ .