nach oben

Journal of Scheduling

Erschienen in:

01.12.2015

Identical coupled task scheduling: polynomial complexity of the cyclic case

verfasst von: Vassilissa Lehoux-Lebacque, Nadia Brauner, Gerd Finke

Erschienen in: Journal of Scheduling | Ausgabe 6/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

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

Nächster Artikel Approximation algorithms for inventory constrained scheduling on a single machine

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

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

Titel: Identical coupled task scheduling: polynomial complexity of the cyclic case
verfasst von: Vassilissa Lehoux-Lebacque
Nadia Brauner
Gerd Finke
Publikationsdatum: 01.12.2015
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 6/2015
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0438-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2015

Approximation algorithms for the joint replenishment problem with deadlines

Algorithms and Complexity Analysis for Robust Single-Machine Scheduling Problems

Scheduling with returnable containers

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

Robust execution strategies for project scheduling with unreliable resources and stochastic durations

Approximation algorithms for inventory constrained scheduling on a single machine

Premium Partner