Search results for "coupled-tasks"
showing 3 items of 3 documents
Approximation algorithm for constrained coupled-tasks scheduling problem
2014
International audience; We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
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 …