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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016034
Classification : 90B35, 68W25, 68Rxx, 68R10
Mots clés : Coupled-task scheduling model, complexity, polynomial-time approximation algorithm
Darties, Benoit 1 ; Giroudeau, Rodolphe 2 ; König, Jean-Claude 2 ; Simonin, Gilles 3

1 LE2I, UMR CNRS 6306, University of Burgundy, 8 Rue Alain Savary, 21000 Dijon, France.
2 LIRMM, UMR CNRS 5506, Université de Montpellier, 161 rue Ada, 34392 Montpellier cedex 5, France.
3 Insight Centre for Data Analytics, University College Cork, Cork, Ireland.
@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/

D. Ahr, J. Békési, G. Galambos, M. Oswald and G. Reinelt, 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

A. Caprara, H. Kellerer and U. Pferschy, The Multiple Subset Sum Problem. SIAM J. Optimiz. 11 (2000) 308–319. | DOI | MR | Zbl

A. Caprara, H. Kellerer and U. Pferschy, A 3/4-Approximation Algorithm for Multiple Subset Sum. J. Heuristics 9 (2003) 99–111. | DOI | Zbl

M. Dawande, J. Kalagnanam, P. Keskinocak, F.S. Salman and R. Ravi, Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions. J. Combin. Optim. 4 (2000) 171–186. | DOI | MR | Zbl

J. Edmonds, Maximum matching and a polyhedron with 0,1 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

R. Giroudeau, J.-C. König, F.K. Moulaï and J. Palaysi, Complexity and approximation for the precedence constrained scheduling problem with large communication delays. Theoret. Comput. Sci. 401 (2008) 107–119. | DOI | MR | Zbl

R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Ann. Discrete Math. 5 (1979) 287–326. | DOI | MR | Zbl

O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the Knapsack and Sum of Subset problems. J. ACM 22 (1975) 463–468. | DOI | MR | Zbl

H. Kellerer, R. Mansini, U. Pferschy and M.G. Speranza, An efficient fully polynomial approximation scheme for the subset-sum problem. J. Comput. Syst. Sci. 66 (2003) 349–370. | DOI | MR | Zbl

H.W. Kuhn, The hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 (1955) 83–97. | DOI | MR | Zbl

A.J. Orman and C.N. Potts, On the complexity of coupled-task scheduling. Discrete Appl. Math. 72 (1997) 141–154. | DOI | MR | Zbl

R.D. Shapiro, 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).

G. Simonin, B. Darties, R. Giroudeau and J.-C. König, Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. J. Sched. 14 (2011) 501–509. | DOI | MR | Zbl

G. Simonin, R. Giroudeau, J.-C. König and B. Darties, Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph. Algorithm. Oper. Res. 7 (2012) 1–12. | MR | Zbl

Cité par Sources :