Skip to main content

2020 | OriginalPaper | Buchkapitel

An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays

verfasst von : Alexander Ageev, Mikhail Ivanov

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

We study the coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. It is known that the problem cannot be approximated with a factor better than 1.25 unless P \(=\) NP. In this paper, we present a 2.5-approximation algorithm for this problem, which improves the best previously known approximation bound of 3. The algorithm runs in time \(O(n\log n)\) where n is the number of jobs.

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!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

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!

Literatur
1.
Zurück zum Zitat Ageev, A.A., Baburin, A.E.: Approximation algorithms for UET scheduling problems with exact delays. Oper. Res. Lett. 35, 533–540 (2007)MathSciNetCrossRef Ageev, A.A., Baburin, A.E.: Approximation algorithms for UET scheduling problems with exact delays. Oper. Res. Lett. 35, 533–540 (2007)MathSciNetCrossRef
4.
Zurück zum Zitat Baptiste, P.: A note on scheduling identical coupled tasks in logarithmic time. Disc. Appl. Math. 158, 583–587 (2010)MathSciNetCrossRef Baptiste, P.: A note on scheduling identical coupled tasks in logarithmic time. Disc. Appl. Math. 158, 583–587 (2010)MathSciNetCrossRef
6.
Zurück zum Zitat Blazewicz, J., Pawlak, G., Tanas, M., Wojciechowicz, W.: New algorithms for coupled tasks scheduling – a survey. RAIRO - Operations Research - Recherche Operationnelle 46, 335–353 (2012)MathSciNetCrossRef Blazewicz, J., Pawlak, G., Tanas, M., Wojciechowicz, W.: New algorithms for coupled tasks scheduling – a survey. RAIRO - Operations Research - Recherche Operationnelle 46, 335–353 (2012)MathSciNetCrossRef
7.
Zurück zum Zitat Condotta, A., Shakhlevich, N.V.: Scheduling coupled-operation jobs with exact time-lags. Discrete Appl. Math. 160, 2370–2388 (2012)MathSciNetCrossRef Condotta, A., Shakhlevich, N.V.: Scheduling coupled-operation jobs with exact time-lags. Discrete Appl. Math. 160, 2370–2388 (2012)MathSciNetCrossRef
8.
Zurück zum Zitat Farina, A., Neri, P.: Multitarget interleaved tracking for phased array radar. IEEE Proc. Part F Comm. Radar Signal Process. 127, 312–318 (1980)CrossRef Farina, A., Neri, P.: Multitarget interleaved tracking for phased array radar. IEEE Proc. Part F Comm. Radar Signal Process. 127, 312–318 (1980)CrossRef
9.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)MATH Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)MATH
10.
Zurück zum Zitat Elshafei, M., Sherali, H.D., Smith, J.C.: Radar pulse interleaving for multi-target tracking. Naval Res. Logist. 51, 79–94 (2004)MathSciNetCrossRef Elshafei, M., Sherali, H.D., Smith, J.C.: Radar pulse interleaving for multi-target tracking. Naval Res. Logist. 51, 79–94 (2004)MathSciNetCrossRef
11.
Zurück zum Zitat Izquierdo-Fuente, A., Casar-Corredera, J.R.: Optimal radar pulse scheduling using neural networks. In: IEEE International Conference on Neural Networks, vol. 7, pp. 4588–4591 (1994) Izquierdo-Fuente, A., Casar-Corredera, J.R.: Optimal radar pulse scheduling using neural networks. In: IEEE International Conference on Neural Networks, vol. 7, pp. 4588–4591 (1994)
12.
Zurück zum Zitat Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979) Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)
13.
Zurück zum Zitat Hwang, F.J., Lin, B.M.T.: Coupled-task scheduling on a single machine subject to a fixed-job-sequence. J. Comput. Ind. Eng. 60, 690–698 (2011)CrossRef Hwang, F.J., Lin, B.M.T.: Coupled-task scheduling on a single machine subject to a fixed-job-sequence. J. Comput. Ind. Eng. 60, 690–698 (2011)CrossRef
14.
Zurück zum Zitat Lawler, E., Lenstra, J., Rinnooy Kan, A., Shmoys, D.: Sequencing and scheduling: algorithms and complexity, In: Handbooks in Operations Research and Management Science, Logistics of Production and Inventory, 4, North Holland, Amsterdam, pp. 445–522 (1993) Lawler, E., Lenstra, J., Rinnooy Kan, A., Shmoys, D.: Sequencing and scheduling: algorithms and complexity, In: Handbooks in Operations Research and Management Science, Logistics of Production and Inventory, 4, North Holland, Amsterdam, pp. 445–522 (1993)
15.
Zurück zum Zitat Orman, A.J., Potts, C.N.: On the complexity of coupled-task scheduling. Discrete Appl. Math. 72, 141–154 (1997)MathSciNetCrossRef Orman, A.J., Potts, C.N.: On the complexity of coupled-task scheduling. Discrete Appl. Math. 72, 141–154 (1997)MathSciNetCrossRef
16.
Zurück zum Zitat Sherali, H.D., Smith, J.C.: Interleaving two-phased jobs on a single machine. Discrete Optim. 2, 348–361 (2005)MathSciNetCrossRef Sherali, H.D., Smith, J.C.: Interleaving two-phased jobs on a single machine. Discrete Optim. 2, 348–361 (2005)MathSciNetCrossRef
Metadaten
Titel
An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays
verfasst von
Alexander Ageev
Mikhail Ivanov
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-49988-4_18