Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs

We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, {\it i.e.}coupled-tasks having the same sub-tasks execution time and idle time duration. We study severals problems in frame works of classic complexity and approximation for which the compatibility graph $G_c$ is bipartite (star, chain, $\ldots$) In such context, we design some efficient polynomial-time approximation algorithms according to difference parameters of the scheduling problem. When $G_c$ is a $k$-stage bipartite graph, we propose, among other, a $\frac{7}{6}$-approximation algorithm when $k=1$, and a $\frac{13}{9}$-approximation algorithm when $k=2$.\

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00947519
Author Darties, Benoit, Giroudeau, Rodolphe, König, Jean-Claude, Simonin, Gilles
Maintainer CCSD
Last Updated May 6, 2026, 09:03 (UTC)
Created May 6, 2026, 09:03 (UTC)
Identifier hal-00947519
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Electronique, Informatique et Image [UMR6306] (Le2i) ; Université de Bourgogne (UB)-École Nationale Supérieure d'Arts et Métiers (ENSAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique (CNRS)
creator Darties, Benoit
date 2014-02-14T00:00:00
harvest_object_id 487ec187-d981-4d64-8e12-29c2c45db5f2
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-08-12T00:00:00
set_spec type:REPORT