# New algorithms for coupled tasks scheduling – a survey

Jacek Blazewicz; Grzegorz Pawlak; Michal Tanas; Wojciech Wojciechowicz

RAIRO - Operations Research - Recherche Opérationnelle (2012)

- Volume: 46, Issue: 4, page 335-353
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBlazewicz, Jacek, et al. "New algorithms for coupled tasks scheduling – a survey." RAIRO - Operations Research - Recherche Opérationnelle 46.4 (2012): 335-353. <http://eudml.org/doc/275084>.

@article{Blazewicz2012,

abstract = {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 ∈ ℕ.},

author = {Blazewicz, Jacek, Pawlak, Grzegorz, Tanas, Michal, Wojciechowicz, Wojciech},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {coupled tasks; scheduling; complexity theory; heuristic algorithms},

language = {eng},

number = {4},

pages = {335-353},

publisher = {EDP-Sciences},

title = {New algorithms for coupled tasks scheduling – a survey},

url = {http://eudml.org/doc/275084},

volume = {46},

year = {2012},

}

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

PB - EDP-Sciences

VL - 46

IS - 4

SP - 335

EP - 353

AB - 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 ∈ ℕ.

LA - eng

KW - coupled tasks; scheduling; complexity theory; heuristic algorithms

UR - http://eudml.org/doc/275084

ER -

## References

top- [1] A.A. Ageev and A.E. Baburin, Approximation algorithms for uet scheduling problems with exact delays. Oper. Res. Lett.35 (2007) 533–540. Zbl1149.90337MR2333326
- [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. Zbl1138.90390MR2063078
- [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. Zbl1196.90046MR2592464
- [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. Zbl1159.90398MR2502034
- [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. Zbl0776.68023MR1161987
- [7] J. Blazewicz, M. Drabowski and J. Weglarz, Scheduling independent 2-processors tasks to minimize schedule length. Inf. Process. Lett.18 (1984) 267–273. Zbl0544.68032MR759993
- [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. Zbl1208.68090MR2685070
- [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). Zbl1165.90009
- [11] J. Blazewicz, G. Pawlak and B. Walter, Scheduling production tasks in a two stage FMS. Int. J. Prod. Res.40 (2002) 4341–4352. Zbl1064.90542
- [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. Zbl1157.90406MR2579919
- [13] P. Brucker, Scheduling Algorithms. Springer Verlag, Berlin, 3rd edition (2001). Zbl0839.90059MR1880405
- [14] P. Brucker and S. Knust, Complexity results for single-machine problems with positive finish-start time-lags. Osnabrück Schriften zur Mathematik202 (1998) 299–316. Zbl0946.90026MR1738712
- [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. Zbl1204.68105MR2376306
- [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. Zbl1204.68105
- [17] M. Elshafei, H.D. Sherali and J.C. Smith, Radar pulse interleaving for multi-target tracking. Naval Res. Logist.51 (2004) 79–94. Zbl1055.90096MR2028732
- [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. Zbl0411.90044MR558574
- [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. Zbl0866.90072MR1421829
- [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 Networks7 (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). Zbl1333.90047
- [25] J. Leung, editor. Handbook of Scheduling. Chapman and Hall (2004). MR2067247
- [26] R. McNaughton, Scheduling with deadlines and loss functions. Manage. Sci.6 (1959) 1–12. Zbl1047.90504MR110585
- [27] A.J. Orman and C.N. Potts, On the complexity of coupled tasks scheduling. Disc. Appl. Math.72 (1997) 141–154. Zbl0873.90053MR1424530
- [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. Zbl0916.90153
- [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. Zbl0904.90110
- [30] C.N. Potts and J.D. Whitehead, Heuristics for a coupled-operation scheduling problem. J. Oper. Res. Soc.58 (2007) 1375–1388. Zbl1177.90179
- [31] R.D. Shapiro, Scheduling coupled tasks. Nav. Res. Logist. Quart.27 (1980) 477–481. Zbl0446.90040MR585621
- [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). Zbl1123.90316
- [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). Zbl0863.90096MR1393202
- [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. Zbl1154.90506MR2101693