Citation
Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland, pages 378-388, 2009.
Paper
Abstract
The problem presented in this paper is a generalization of the usual coupled tasks scheduling problem in presence of compatibility constraints. The reason behind this study is the data acquisition problem for a submarine torpedo. We investigate a particular configuration for coupled-tasks (any task is divided into two sub-tasks separated by an idle time), in which the idle time of a coupled-task is equal to the sum of durations of its two sub-tasks.We prove NP-completeness of the minimization of the schedule length, and we show that finding a solution to our problem amounts to solving a graph problem, which in itself is close to the minimum-disjoint path cover (min-DCP) problem. We design a ( (3a+2b) / (2a+2b) ) approximation, where a and b (the processing time of the two sub-tasks) are two input data such as a > b > 0, and that leads to a ratio between 3/2 and 5/4 . Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to (1+sqrt(3))/2 ? 1.37.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2009-378-388-P, author = {G. Simonin and B. Darties and R. Giroudeau and J-C. Konig},
title = {Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor},
booktitle = {Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland},
year = {2009},
editor = {J. Blazewicz and M. Drozdowski and G. Kendall and B. McCollum},
pages = {378--388},
note = {Paper},
abstract = {The problem presented in this paper is a generalization of the usual coupled tasks scheduling problem in presence of compatibility constraints. The reason behind this study is the data acquisition problem for a submarine torpedo. We investigate a particular configuration for coupled-tasks (any task is divided into two sub-tasks separated by an idle time), in which the idle time of a coupled-task is equal to the sum of durations of its two sub-tasks.We prove NP-completeness of the minimization of the schedule length, and we show that finding a solution to our problem amounts to solving a graph problem, which in itself is close to the minimum-disjoint path cover (min-DCP) problem. We design a ( (3a+2b) / (2a+2b) ) approximation, where a and b (the processing time of the two sub-tasks) are two input data such as a > b > 0, and that leads to a ratio between 3/2 and 5/4 . Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to (1+sqrt(3))/2 ? 1.37.},
owner = {gxk},
timestamp = {2010.10.11},
webpdf = {2009-378-388-P.pdf} }