0000000000928811
AUTHOR
Rodolphe Giroudeau
showing 3 related works from this author
Scheduling coupled-tasks with incompatibility constraint: a bin-packing related problem
2014
International audience; We tackle the makespan minimization problem of coupled- tasks in presence of compatibility constraint. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We show the relationship with bin packing problems for some configurations, and study several problems in framework of complexity and approximation for which the topology of the compatibility graph is specific (star, chain, bipartite, . . .).
Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs
2014
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…
Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph
2012
International audience; This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro \cite{Shapiro}, where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between $\mathcal{P}$ and $\mathcal{NP}$-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of …