Theoretical aspects of scheduling coupled-tasks in the presence of compatibility graph

Authors

  • G. Simonin Université Montpellier 2
  • R. Giroudeau Université Montpellier 2
  • B. Darties University of Burgundy
  • J.-C. König Université Montpellier 2

Keywords:

complexity, approximation algorithm, scheduling, coupled-tasks

Abstract

This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro [12], 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 <em>P</em> and <em>NP</em>-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 [11] 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.

Downloads

Additional Files

Published

2012-07-26

How to Cite

Simonin, G., Giroudeau, R., Darties, B., & König, J.-C. (2012). Theoretical aspects of scheduling coupled-tasks in the presence of compatibility graph. Algorithmic Operations Research, 7(1), Pages 1 – 12. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/18602

Issue

Section

Articles