Citation
Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. Journal of Scheduling, 14 (5): 501-509, 2011.
Selected
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, 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 32 and 54 . Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to 1+ ? 3 2 ? 1.37.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/s10951-010-0193-x You can link directly to the original paper, via the doi, from here
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
@ARTICLE{2011-501-509-SI, author = {G. Simonin and B. Darties and R. Giroudeau and J.-C. König},
title = {Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor},
journal = {Journal of Scheduling},
year = {2011},
volume = {14},
pages = {501--509},
number = {5},
note = {Selected},
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, 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 32 and 54 . Using a polynomial-time algorithm developed for some class of graph of min-DCP, we show that the ratio decreases to 1+ ? 3 2 ? 1.37.},
doi = {10.1007/s10951-010-0193-x},
owner = {user},
timestamp = {2012.05.25} }