Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Algorithmic Issues in Energy-Efficient Computation Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Approximating Coupled-Task Scheduling Problems with Equal Exact Delays

verfasst von : Alexander Ageev, Mikhail Ivanov

Erschienen in: Discrete Optimization and Operations Research

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We consider a coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. We design a 3-approximation algorithm for the general case of this problem. We also prove that the existence of a \((1.25-\varepsilon )\)-approximation algorithm implies P = NP. The inapproximability result remains valid for the case when the processing times of the two operations of each job are equal. We prove that this case is approximable within a factor of 1.5.

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 "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!

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
Vorheriges Kapitel A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem
Nächstes Kapitel Routing Open Shop with Unrelated Travel Times
Literatur
1.
Ageev, A.A., Baburin, A.E.: Approximation algorithms for UET scheduling problems with Exact Delays. Oper. Res. Lett. 35, 533–540 (2007)MathSciNetCrossRefMATH
2.
Ageev, A.A., Kononov, A.V.: Approximation algorithms for scheduling problems with exact delays. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, pp. 1–14. Springer, Heidelberg (2007)CrossRef
3.
4.
Bekesi, J., Galambos, G., Jung, M.N., Oswald, M., Reinelt, G.: A branch-and-bound algorithm for the coupled task problem. Math. Methods Oper. Res. 80, 47–81 (2014)MathSciNetCrossRefMATH
5.
Blazewicz, J., Pawlak, G., Tanas, M., Wojciechowicz, W.: New algorithms for coupled tasks scheduling – a survey. RAIRO - Oper. Res. - Recherche Operationnelle 46, 335–353 (2012)MathSciNetCrossRefMATH
6.
Condotta, A., Shakhlevich, N.V.: Scheduling coupled-operation jobs with exact time-lags. Discrete Appl. Math. 160, 2370–2388 (2012)MathSciNetCrossRefMATH
7.
Farina, A., Neri, P.: Multitarget interleaved tracking for phased array radar. IEEE Proc. Part F: Comm. Radar Signal Process. 127, 312–318 (1980)
8.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)MATH
9.
Elshafei, M., Sherali, H.D., Smith, J.C.: Radar pulse interleaving for multi-target tracking. Naval Res. Logist. 51, 79–94 (2004)MathSciNetCrossRefMATH
10.
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)
11.
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. Discret. Math. 5, 287–326 (1979)MathSciNetCrossRefMATH
12.
Hwang, F.J., Lin, B.M.T.: Coupled-task scheduling on a single machine subject to a fixed-job-sequence. J. Comput. Indust. Eng. 60, 690–698 (2011)CrossRef
13.
14.
Metadaten
Titel
Approximating Coupled-Task Scheduling Problems with Equal Exact Delays
verfasst von
Alexander Ageev
Mikhail Ivanov
Copyright-Jahr
2016
Buch
Discrete Optimization and Operations Research

Print ISBN: 978-3-319-44913-5

Electronic ISBN: 978-3-319-44914-2

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-44914-2_21

Premium Partner

    Bildnachweise