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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Semi-online Machine Covering on Two Hierarchical Machines with Discrete Processing Times Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

A New Approximation Algorithm for Flow Shop with Transporter Coordinate

verfasst von : Xin Han, Yinling Wang

Erschienen in: Theoretical Computer Science

Verlag: Springer Singapore

Einloggen

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

search-config
loading …

Abstract

In this paper, we study a problem of the two-machine flow shop scheduling problem with intermediate transportation. This problem has been studied in [2, 4, 17]. The best approximation algorithm was presented in [17] with a two approximation ratio to our best knowledge. We propose a \((\frac{5}{3}+\varepsilon )\)-approximation algorithm for this problem, where \(\varepsilon >0\). Moreover, our algorithm can reach the lower bound \(\frac{5}{3}\) asymptotically given by [2] when \(\varepsilon \) is close to 0.

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 Study of Multilevel Parallel Algorithm of KPCA for Hyperspectral Images
Nächstes Kapitel A Kernel Method with Manifold Regularization for Interactive Segmentation
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Cheng, T.C.E., Gordon, V.S.: Batch delivery scheduling on a single machine. J. Oper. Res. Soc. 45(10), 1211–1216 (1994)CrossRef
2.
Dong, J., Wang, X., Hu, J., Lin, G.: An improved two-machine flowshop scheduling with intermediate transportation. J. Comb. Optim. 31(3), 1316–1334 (2016)MathSciNetCrossRef
3.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH
4.
Gong, H., Tang, L.: Two-machine flowshop scheduling with intermediate transportation under job physical space consideration. Comput. Oper. Res. 38(9), 1267–1274 (2011)MathSciNetCrossRef
5.
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(1), 287–326 (1979)MathSciNetCrossRef
6.
7.
Hall, L.A., Shmoys, D.B.: Approximation schemes for constrained scheduling problems. In: 1989 30th Annual Symposium on Foundations of Computer Science, pp. 134–139. IEEE (1989)
8.
Hurink, J., Knust, S.: Makespan minimization for flow-shop problems with transportation times and a single robot. Discret. Appl. Math. 112(1), 199–216 (2001)MathSciNetCrossRef
9.
Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)MathSciNetCrossRef
10.
Lan, Y., Han, X., Wu, Z., Guo, H., Chen, X.: Complexity of problem \({TF2}|v=1, c=2|{C}_{max}\). Inf. Process. Lett. 116(1), 65–69 (2016)CrossRef
11.
12.
Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Nav. Res. Logist. Q. 1(1), 61–68 (1954)CrossRef
13.
Maggu, P.L., Das, G.: On \(2\times n\) sequencing problem with transportation times of jobs. Am. J. Ind. Med. 12(6), 574–83 (1980)MATH
14.
15.
Vaidya, P.M.: Speeding-up linear programming using fast matrix multiplication. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 332–337 (1989)
16.
Chang, Y.-C., Lee, C.Y.: Machine scheduling with job delivery coordination. Eur. J. Oper. Res. 158(2), 470–487 (2004)MathSciNetCrossRef
17.
Zhong, W., Chen, Z.L.: Flowshop scheduling with interstage job transportation. J. Sched. 18(4), 411–422 (2015)MathSciNetCrossRef
Metadaten
Titel
A New Approximation Algorithm for Flow Shop with Transporter Coordinate
verfasst von
Xin Han
Yinling Wang
Copyright-Jahr
2018
Verlag
Springer Singapore
Buch
Theoretical Computer Science

Print ISBN: 978-981-13-2711-7

Electronic ISBN: 978-981-13-2712-4

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-981-13-2712-4_9