New algorithms for coupled tasks scheduling - a survey
RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 4, pp. 335-353.

The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of coupled tasks problems. Then, it complements previous results by providing experimental results of two new polynomial algorithms for coupled tasks scheduling, which are: an exact algorithm for 1|(1,4,1),strictchains|Cmax problem, and a fast heuristic algorithm for more general 1|(1,2k, 1), strictchains|Cmax problem, where k ∈ ℕ.

DOI : 10.1051/ro/2012020
Classification : 9002, 9008, 90B30, 90B35, 90C27, 90C59, 90C60
Mots-clés : coupled tasks, scheduling, complexity theory, heuristic algorithms 
@article{RO_2012__46_4_335_0,
     author = {Blazewicz, Jacek and Pawlak, Grzegorz and Tanas, Michal and Wojciechowicz, Wojciech},
     title = {New algorithms for coupled tasks scheduling - a survey},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {335--353},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {4},
     year = {2012},
     doi = {10.1051/ro/2012020},
     mrnumber = {3029894},
     zbl = {1262.90060},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2012020/}
}
TY  - JOUR
AU  - Blazewicz, Jacek
AU  - Pawlak, Grzegorz
AU  - Tanas, Michal
AU  - Wojciechowicz, Wojciech
TI  - New algorithms for coupled tasks scheduling - a survey
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2012
SP  - 335
EP  - 353
VL  - 46
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2012020/
DO  - 10.1051/ro/2012020
LA  - en
ID  - RO_2012__46_4_335_0
ER  - 
%0 Journal Article
%A Blazewicz, Jacek
%A Pawlak, Grzegorz
%A Tanas, Michal
%A Wojciechowicz, Wojciech
%T New algorithms for coupled tasks scheduling - a survey
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2012
%P 335-353
%V 46
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2012020/
%R 10.1051/ro/2012020
%G en
%F RO_2012__46_4_335_0
Blazewicz, Jacek; Pawlak, Grzegorz; Tanas, Michal; Wojciechowicz, Wojciech. New algorithms for coupled tasks scheduling - a survey. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 4, pp. 335-353. doi : 10.1051/ro/2012020. http://www.numdam.org/articles/10.1051/ro/2012020/

[1] A.A. Ageev and A.E. Baburin, Approximation algorithms for uet scheduling problems with exact delays. Oper. Res. Lett. 35 (2007) 533-540. | MR | Zbl

[2] D. Ahr, J. Bekesi, G. Galambos, M. Oswald and G. Reinelt, An exact algorithm for scheduling identical coupled tasks. Math. Methods Oper. Res. 59 (2004) 193-203. | MR | Zbl

[3] K. Baker, Introduction to Sequencing and Scheduling. J. Wiley, New York (1974).

[4] P. Baptiste, A note on scheduling identical coupled tasks in logarithmic time. Disc. Appl. Math. 158 (2010) 583-587. | MR | Zbl

[5] J. Bekesi, G. Galambos, M. Oswald and G. Reinelt, Improved analysis of an algorithm for the coupled task problem with uet jobs. Oper. Res. Lett. 37 (2009) 93-96. | MR | Zbl

[6] J. Blazewicz, P. Dell'Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors. Inform. Process. Lett. 41 (1992) 275-280. | MR | Zbl

[7] J. Blazewicz, M. Drabowski and J. Weglarz, Scheduling independent 2-processors tasks to minimize schedule length. Inf. Process. Lett. 18 (1984) 267-273. | MR | Zbl

[8] J. Blazewicz, K. Ecker, T. Kis, C.N. Potts, M. Tanas and J. Whitehead, Scheduling of coupled tasks with unit processing times. J. sched. 13 (2010) 453-461. | MR | Zbl

[9] J. Blazewicz, K. Ecker, T. Kis and M. Tanas, A note on the complexity of scheduling coupled tasks on a single processor. J. Brazil. Comput. Soc. 7 (2002) 23-27.

[10] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Handbook of Scheduling. From Theory to Applications. Springer Verlag (2007). | Zbl

[11] J. Blazewicz, G. Pawlak and B. Walter, Scheduling production tasks in a two stage FMS. Int. J. Prod. Res. 40 (2002) 4341-4352. | Zbl

[12] N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Potts and J. Whitehead, Scheduling of coupled tasks and one-machine no-wait robotic cells. Comput. Oper. Res. 36 (2009) 301-307. | MR | Zbl

[13] P. Brucker, Scheduling Algorithms. Springer Verlag, Berlin, 3rd edition (2001). | MR | Zbl

[14] P. Brucker and S. Knust, Complexity results for single-machine problems with positive finish-start time-lags. Osnabrück Schriften zur Mathematik 202 (1998) 299-316. | MR | Zbl

[15] K. Ecker and M. Tanas, Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap. Found. Comput. Decision Sci. 32 (2007) 199-212. | MR | Zbl

[16] K. Ecker and M. Tanas, Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap. J. Oper. Res. Soc. 63 (2012) 524-529. | Zbl

[17] M. Elshafei, H.D. Sherali and J.C. Smith, Radar pulse interleaving for multi-target tracking. Naval Res. Logist. 51 (2004) 79-94. | MR | Zbl

[18] A. Farina and P. Neri, Multitarget interleaved tracking for phased array radar. IEEE Proc. Part F : Comm. Radar Signal Process 127 (1980) 312-318.

[19] 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. | MR | Zbl

[20] J.N.D. Gupta, Single facility scheduling with two operations per job and time-lags. Technical Paper (1994).

[21] J.N.D. Gupta, Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags. J. Glob. Optim. 9 (1996) 239-50. | MR | Zbl

[22] P.L. Heinselman, D.L. Preignitz, K.L. Manross and T.M. Smith and R.W. Adams, Rapid sampling of severe storms by the national weather radar testbed phased array radar. Weather Forecast. 23 (2008) 808-824.

[23] A. Izquierdo-Fuente and J.R. Casar-Corredera. Optimal radar pulse scheduling using neural networks. In IEEE International Conference on Neural Networks 7 (1994) 4588-4591.

[24] V. Lehoux-Lebacque, N. Brauner and G. Finke, Identical coupled tasks scheduling : polynomial complexity of the cyclic case. Les Cahiers Leibnitz 179 (2009).

[25] J. Leung, editor. Handbook of Scheduling. Chapman and Hall (2004). | MR

[26] R. Mcnaughton, Scheduling with deadlines and loss functions. Manage. Sci. 6 (1959) 1-12. | MR | Zbl

[27] A.J. Orman and C.N. Potts, On the complexity of coupled tasks scheduling. Disc. Appl. Math. 72 (1997) 141-154. | MR | Zbl

[28] A.J. Orman, C.N. Potts, A.K. Shahani and A.R. Moore, Scheduling for the control of a multifunctional radar system. Eur. J. Oper. Res. 90 (1996) 13-25. | Zbl

[29] A.J. Orman, A.K. Shahani and A.R. Moore, Modelling for the control of a complex radar system. Comput. Oper. Res. 25 (1998) 239-249. | Zbl

[30] C.N. Potts and J.D. Whitehead, Heuristics for a coupled-operation scheduling problem. J. Oper. Res. Soc. 58 (2007) 1375-1388. | Zbl

[31] R.D. Shapiro, Scheduling coupled tasks. Nav. Res. Logist. Quart. 27 (1980) 477-481. | MR | Zbl

[32] M.I. Skolnik, Introduction to Radar Systems. McGraw Hill, London (1980).

[33] M. Tanas, Scheduling of Coupled Tasks. PhD thesis, Technische Universitat Clausthal (2004). | Zbl

[34] J.D. Whitehead, Scheduling and layout in flexible manufacturing systems. Ph.D. thesis, University of Southampton (2002).

[35] W. Yu, The Two-machine Flow Shop Problem with Delays and the One-machine Total Tardiness Problem Ph.D. Thesis. Technische Universiteit Eindhoven (1996). | MR | Zbl

[36] W. Yu, H. Hoogeveen and J.K. Lenstra, Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard. J. Sched. 7 (2004) 333-348. | MR | Zbl

Cité par Sources :