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

Abstract

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

How to cite

top

Blazewicz, 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. [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. [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. [3] K. Baker, Introduction to Sequencing and Scheduling. J. Wiley, New York (1974). 
  4. [4] P. Baptiste, A note on scheduling identical coupled tasks in logarithmic time. Disc. Appl. Math.158 (2010) 583–587. Zbl1196.90046MR2592464
  5. [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. [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. [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. [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. [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. [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. [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. [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. [13] P. Brucker, Scheduling Algorithms. Springer Verlag, Berlin, 3rd edition (2001). Zbl0839.90059MR1880405
  14. [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. [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. [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. [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. [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. [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. [20] J.N.D. Gupta, Single facility scheduling with two operations per job and time-lags. Technical Paper (1994). 
  21. [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. [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. [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. [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. [25] J. Leung, editor. Handbook of Scheduling. Chapman and Hall (2004). MR2067247
  26. [26] R. McNaughton, Scheduling with deadlines and loss functions. Manage. Sci.6 (1959) 1–12. Zbl1047.90504MR110585
  27. [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. [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. [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. [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. [31] R.D. Shapiro, Scheduling coupled tasks. Nav. Res. Logist. Quart.27 (1980) 477–481. Zbl0446.90040MR585621
  32. [32] M.I. Skolnik, Introduction to Radar Systems. McGraw Hill, London (1980). 
  33. [33] M. Tanas, Scheduling of Coupled Tasks. PhD thesis, Technische Universitat Clausthal (2004). Zbl1123.90316
  34. [34] J.D. Whitehead, Scheduling and layout in flexible manufacturing systems. Ph.D. thesis, University of Southampton (2002). 
  35. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.