Bounds and approximation results for scheduling coupled-tasks with compatibility constraints

Abstract

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}\ne \mathcal{NP}$, $\mathcal{E}\mathcal{T}\mathcal{H}$). 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.

References in corpus (1)

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