We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain, ). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.
Accepté le :
DOI : 10.1051/ro/2016034
Mots clés : Coupled-task scheduling model, complexity, polynomial-time approximation algorithm
@article{RO_2016__50_4-5_781_0,
author = {Darties, Benoit and Giroudeau, Rodolphe and K\"onig, Jean-Claude and Simonin, Gilles},
title = {Some complexity and approximation results for coupled-tasks scheduling problem according to topology},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {781--795},
publisher = {EDP-Sciences},
volume = {50},
number = {4-5},
year = {2016},
doi = {10.1051/ro/2016034},
zbl = {1353.90058},
mrnumber = {3570530},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2016034/}
}
TY - JOUR AU - Darties, Benoit AU - Giroudeau, Rodolphe AU - König, Jean-Claude AU - Simonin, Gilles TI - Some complexity and approximation results for coupled-tasks scheduling problem according to topology JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 781 EP - 795 VL - 50 IS - 4-5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016034/ DO - 10.1051/ro/2016034 LA - en ID - RO_2016__50_4-5_781_0 ER -
%0 Journal Article %A Darties, Benoit %A Giroudeau, Rodolphe %A König, Jean-Claude %A Simonin, Gilles %T Some complexity and approximation results for coupled-tasks scheduling problem according to topology %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 781-795 %V 50 %N 4-5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016034/ %R 10.1051/ro/2016034 %G en %F RO_2016__50_4-5_781_0
Darties, Benoit; Giroudeau, Rodolphe; König, Jean-Claude; Simonin, Gilles. Some complexity and approximation results for coupled-tasks scheduling problem according to topology. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 781-795. doi : 10.1051/ro/2016034. http://www.numdam.org/articles/10.1051/ro/2016034/
, , , and , An exact algorithm for scheduling identical coupled-tasks. Math. Methods Oper. Res. 59 (2004) 193–203. | DOI | MR | Zbl
J. Blażewicz, K. Ecker, T. Kis, C.N. Potts, M. Tanas and J. Whitehead, Scheduling of coupled tasks with unit processing times. Technical report, Poznan University of Technology (2009). | MR | Zbl
A. Caprara, H. Kellerer and U. Pferschy, A PTAS for the Multiple Subset Sum Problem with different knapsack capacities. Inf. Process. Lett. (2000). | MR | Zbl
, and , The Multiple Subset Sum Problem. SIAM J. Optimiz. 11 (2000) 308–319. | DOI | MR | Zbl
, and , A 3/4-Approximation Algorithm for Multiple Subset Sum. J. Heuristics 9 (2003) 99–111. | DOI | Zbl
, , , and , Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions. J. Combin. Optim. 4 (2000) 171–186. | DOI | MR | Zbl
, Maximum matching and a polyhedron with vertices. J. Res. Nat. Bur. Stand. 69 (1965) 125–130. | DOI | MR | Zbl
M.R. Garey and D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA (1979). | MR | Zbl
, , and , Complexity and approximation for the precedence constrained scheduling problem with large communication delays. Theoret. Comput. Sci. 401 (2008) 107–119. | DOI | MR | Zbl
, , and , Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Ann. Discrete Math. 5 (1979) 287–326. | DOI | MR | Zbl
and , Fast approximation algorithms for the Knapsack and Sum of Subset problems. J. ACM 22 (1975) 463–468. | DOI | MR | Zbl
, , and , An efficient fully polynomial approximation scheme for the subset-sum problem. J. Comput. Syst. Sci. 66 (2003) 349–370. | DOI | MR | Zbl
, The hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 (1955) 83–97. | DOI | MR | Zbl
and , On the complexity of coupled-task scheduling. Discrete Appl. Math. 72 (1997) 141–154. | DOI | MR | Zbl
, Scheduling coupled tasks. Naval Res. Logist. Quarterly 27 (1980) 477–481. | DOI | MR | Zbl
G. Simonin, R. Giroudeau and J.-C. König, Complexity and approximation for scheduling problem for coupled-tasks in presence of compatibility tasks. In Project Management and Scheduling (2010).
, , and , Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. J. Sched. 14 (2011) 501–509. | DOI | MR | Zbl
, , and , Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph. Algorithm. Oper. Res. 7 (2012) 1–12. | MR | Zbl
Cité par Sources :
