Top

Journal of Scheduling

Published in:

01-12-2015

Identical coupled task scheduling: polynomial complexity of the cyclic case

Authors: Vassilissa Lehoux-Lebacque, Nadia Brauner, Gerd Finke

Published in: Journal of Scheduling | Issue 6/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Coupled tasks are two-operation tasks, where the two operations are separated by a time interval of fixed duration. Coupled task scheduling problems refer then to the scheduling of a set of coupled tasks on a single machine. Applications of these problems, reported in the literature, arise in connection with radar systems, robotic cells, and in manufacturing. Most of the complexity issues for scheduling coupled tasks have been settled. However, the complexity status has been unknown for the identical coupled task problem, where multiple copies of a single coupled task are to be processed. The purpose of the article is to solve this open problem in the cyclic case, for which we prove the polynomial complexity.

previous article An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

next article Approximation algorithms for inventory constrained scheduling on a single machine

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Ageev, A. A., & Baburin, A. E. (2007). Approximation algorithms for UET scheduling problems with exact delays. Operations Research Letters, 35(4), 533–540.CrossRef

Ahr, D., Békési, J., Galambos, G., Oswald, M., & Reinelt, G. (2004). An exact algorithm for scheduling identical coupled tasks. Mathematical Methods of Operations Research (ZOR), 59, 193–203.CrossRef

Baptiste, Ph. (2010). A note on scheduling identical coupled tasks in logarithmic time. Discrete Applied Mathematics, 158(5), 583–587.CrossRef

Békési, J., Galambos, G., Oswalda, M., & Reinelt, G. (2009). Improved analysis of an algorithm for the coupled task problem with UET jobs. Operations Research Letters, 37(2), 93–96.CrossRef

Blazewicz, J., Ecker, K., Kis, T., Potts, C. N., Tanas̀, M., & Whitehead, J. (2010). Scheduling of coupled tasks with unit processing times. Journal of Scheduling, 13(5), 453–461.CrossRef

Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2005). A framework for the complexity of high-multiplicity scheduling problems. Journal of Combinatorial Optimization, 9, 313–323.CrossRef

Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2007). Multiplicity and complexity issues in contemporary production scheduling. Statistica Neerlandica, 61(1), 75–91.CrossRef

Brauner, N., Finke, G., Lehoux-Lebacque, V., Potts, C. N., & Whitehead, J. (2009). Scheduling of coupled tasks and one-machine no-wait robotic cells. Computers and Operations Research, 36(2), 301–307.CrossRef

Duron, C. (2002). Ordonnancement en temps-réel des activités des radars. PhD thesis, Université de Metz.

Elshafei, M., Sherali, H. D., & Smith, J. C. (2003). Radar pulse interleaving for multi-target tracking. Naval Research Logistics, 51, 72–94.CrossRef

Farina, A., & Neri, P. (1980). Multitarget interleaved tracking for the phased radar array. IEE Proceedings F, 27, 312–318.

Gupta, J. N. D. (1996). Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags. Journal of Global Optimization, 9, 239–250.CrossRef

Karp, M. (1978). A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23(3), 309–311.CrossRef

Lebacque, V. (2007). Théories et applications en ordonnancement: contraintes de ressources et tâches agrégées en catégories. PhD thesis, Université Joseph Fourier.

Levner, E., Kats, V., de Pablo, D. A. L., & Cheng, T. C. E. (2010). Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & Industrial Engineering, 59, 352–361.

Milojevic, D. J., & Popovic, B. M. (1992). Improved algorithm for the interleaving of radar pulses. IEE Proceedings F, 139, 98–104.

Orman, A. J., & Potts, C. N. (1997). On the complexity of coupled-task scheduling. Discrete Applied Mathematics, 72, 141–154.CrossRef

Orman, A. J., Shahani, A. K., & Moore, A. R. (1998). Modelling for the control of radar system. Computers and OR, 25, 239–249.CrossRef

Shahani, A. K., Orman, A. J., Potts, C. N., & Moore, A. R. (1996). Scheduling for a multifunction phased array radar system. European Journal of Operational Research, 90, 13–25.CrossRef

Shapiro, R. D. (1980). Scheduling coupled tasks. Naval Research Logistics Quarterly, 27(2), 489–497.CrossRef

Simonin, G., Darties, B., Giroudeau, R., & König, J.-C. (2011). Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. Journal of Scheduling, 14(5), 501–509.CrossRef

Title: Identical coupled task scheduling: polynomial complexity of the cyclic case
Authors: Vassilissa Lehoux-Lebacque
Nadia Brauner
Gerd Finke
Publication date: 01-12-2015
Publisher: Springer US
Published in: Journal of Scheduling / Issue 6/2015
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0438-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2015

Real-time scheduling to minimize machine busy times

Scheduling with returnable containers

An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

Algorithms and Complexity Analysis for Robust Single-Machine Scheduling Problems

Approximation algorithms for inventory constrained scheduling on a single machine

Approximation algorithms for the joint replenishment problem with deadlines

Premium Partner