Résumé
15th International Conference on Project Management and Scheduling, pp.94-97, 2016 This article is devoted to propose some lower and upper bounds for the coupled-tasks scheduling problem in presence of compatibility constraints according to classical complexity hypothesis ( $\mathcal{P} \neq \mathcal{NP}$ ,$\mathcal{ETH}$ ). Moreover, we develop an efficient polynomial-time approximation algorithm for the specific case for which the topology describing the compatibility constraints is a quasi split-graph.