Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Algorithmic Operations Research Year : 2012

Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph

Abstract

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 the complexity of scheduling problems with coupled-task given by Orman and Potts \cite{op1997} to our model, determine new complexity results, and thus propose a new visualization including incompatibility constraints. In the end, we give a new polynomial-time approximation algorithm result which completes previous works.
No file

Dates and versions

lirmm-00715828 , version 1 (09-07-2012)

Identifiers

  • HAL Id : lirmm-00715828 , version 1

Cite

Rodolphe Giroudeau, Benoit Darties, Jean-Claude König, Gilles Simonin. Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph. Algorithmic Operations Research, 2012, 7 (1), pp.1-12. ⟨lirmm-00715828⟩
219 View
0 Download

Share

More