@unpublished{simonin_theoretical_2008,
	title = {Theoretical study of the isomorphic coupled-task scheduling problem with compatibility constrainsts.(rejected on {STACS} 2009)},
	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 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 {\textgreater} b, 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 7/5.},
	author = {Simonin, Gilles and Darties, Benoit and Giroudeau, R. and {Jean-Claude Koenig}},
	year = {2008},
	keywords = {approximation algorithms, complexity, coupled-tasks, graph, review, scheduling}
}

{"_id":"FGhsbzb7CxhEKxCYc","bibbaseid":"simonin-darties-giroudeau-jeanclaudekoenig-theoreticalstudyoftheisomorphiccoupledtaskschedulingproblemwithcompatibilityconstrainstsrejectedonstacs2009-2008","downloads":0,"creationDate":"2016-12-19T20:50:58.865Z","title":"Theoretical study of the isomorphic coupled-task scheduling problem with compatibility constrainsts.(rejected on STACS 2009)","author_short":["Simonin, G.","Darties, B.","Giroudeau, R.","Jean-Claude Koenig"],"year":2008,"bibtype":"unpublished","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"unpublished","type":"unpublished","title":"Theoretical study of the isomorphic coupled-task scheduling problem with compatibility constrainsts.(rejected on STACS 2009)","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 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 \\textgreater b, 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 7/5.","author":[{"propositions":[],"lastnames":["Simonin"],"firstnames":["Gilles"],"suffixes":[]},{"propositions":[],"lastnames":["Darties"],"firstnames":["Benoit"],"suffixes":[]},{"propositions":[],"lastnames":["Giroudeau"],"firstnames":["R."],"suffixes":[]},{"firstnames":[],"propositions":[],"lastnames":["Jean-Claude Koenig"],"suffixes":[]}],"year":"2008","keywords":"approximation algorithms, complexity, coupled-tasks, graph, review, scheduling","bibtex":"@unpublished{simonin_theoretical_2008,\n\ttitle = {Theoretical study of the isomorphic coupled-task scheduling problem with compatibility constrainsts.(rejected on {STACS} 2009)},\n\tabstract = {The problem presented in this paper is a generalization of the usual coupled-\ntasks 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 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 {\\textgreater} b, 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 7/5.},\n\tauthor = {Simonin, Gilles and Darties, Benoit and Giroudeau, R. and {Jean-Claude Koenig}},\n\tyear = {2008},\n\tkeywords = {approximation algorithms, complexity, coupled-tasks, graph, review, scheduling}\n}\n\n","author_short":["Simonin, G.","Darties, B.","Giroudeau, R.","Jean-Claude Koenig"],"key":"simonin_theoretical_2008","id":"simonin_theoretical_2008","bibbaseid":"simonin-darties-giroudeau-jeanclaudekoenig-theoreticalstudyoftheisomorphiccoupledtaskschedulingproblemwithcompatibilityconstrainstsrejectedonstacs2009-2008","role":"author","urls":{},"keyword":["approximation algorithms","complexity","coupled-tasks","graph","review","scheduling"],"downloads":0,"html":""},"search_terms":["theoretical","study","isomorphic","coupled","task","scheduling","problem","compatibility","constrainsts","rejected","stacs","2009","simonin","darties","giroudeau","jean-claude koenig"],"keywords":["approximation algorithms","complexity","coupled-tasks","graph","review","scheduling"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}