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
Journal of Scheduling
Erschienen in: Journal of Scheduling 6/2023

02.11.2022

An improved approximation algorithm for a scheduling problem with transporter coordination

verfasst von: Yinling Wang, Xin Han, Yong Zhang, Jacek Blazewicz

Erschienen in: Journal of Scheduling | Ausgabe 6/2023

Einloggen

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

search-config
loading …

Abstract

We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single transporter. The goal is to minimize the time that all the jobs are delivered to their destination, such that the transporter returns. We propose a \(11/6+\varepsilon \)-approximation algorithm which improves upon the best-known approximation ratio of 2.
Vorheriger Artikel A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
Nächster Artikel Scheduling on a graph with release times

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
Literatur
Blazewicz, J., Eiselt, H. A., Finke, G., Laporte, G., & Weglarz, J. (1991). Scheduling tasks and vehicles in a flexible manufacturing system. International Journal of Flexible Manufacturing Systems, 4(1), 5–16.CrossRef
Blazewicz, J., Burkard, R. E., Finke, G., & Wöginger, G. J. (1994). Vehicle scheduling in two-cycle flexible manufacturing systems. Mathematical and Computer Modelling, 20(2), 19–31.CrossRef
Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., & Weglarz, J. (2019). Handbook on scheduling. Springer.
Chang, Y., & Lee, C. (2004). Machine scheduling with job delivery coordination. European Journal of Operational Research, 158(2), 470–487.CrossRef
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(1), 287–326.CrossRef
Hurink, J., & Knust, S. (2001). Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Applied Mathematics, 112(1–3), 199–216.CrossRef
Johnson, D. S. (2008). Bin Packing (pp. 1–99). Springer.
Johnson, D. S., Demers, A. J., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4), 299–325.CrossRef
Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61–68.CrossRef
Kise, H. (1991). On an automated two-machine flowshop scheduling problem with infinite buffer. Journal of the Operations Research Society of Japan, 34(3), 354–361.CrossRef
Lan, Y., Han, X., Wu, Z., Guo, H., & Chen, X. (2016). Complexity of problem \(tf2| v= 1, c= 2| c_{max}\). Information Processing Letters, 116(1), 65–69.CrossRef
Lee, C. Y., & Chen, Z. L. (2001). Machine scheduling with transportation considerations. Journal of Scheduling, 4(1), 3–24.CrossRef
Potts, C. N. (1980). Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research, 28(6), 1436–1441.CrossRef
Potts, C. N., & Van Wassenhove, L. N. (1992). Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society, 43(5), 395–406.CrossRef
Sethi, S. P., Sriskandarajah, C., Sorger, G., Blazewicz, J., & Kubiak, W. (1992). Sequencing of parts and robot moves in a robotic cell. International Journal of Flexible Manufacturing Systems, 4(3–4), 331–358.CrossRef
Su, C. S., Pan, C. H., & Hsu, T. S. (2009). A new heuristic algorithm for the machine scheduling problem with job delivery coordination. Theoretical Computer Science, 410(27), 2581–2591.
Wang, L., & Liu, Z. (2013). An improved algorithm for scheduling two identical machines with batch delivery consideration. Operations Research Transactions, 17(1), 38–43.
Wang, Y., Lan, Y., Chen, X., Han, X., & Piao, Y. (2020). A tight approximation algorithm for problem \( p2 \rightarrow d | v=1,c=1 | c_{\max }\). Journal of Combinatorial Optimization, pp. 1–12.
Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43(4), 692–703.CrossRef
Woeginger, G. J. (1994). Heuristics for parallel machine scheduling with delivery times. Acta Informatica, 31(6), 503–512.
Zhang, Y., Zheng, Q., Ren, J., & Zhang, L. (2015). An improved algorithm for the machine scheduling problem with job delivery coordination. In 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015), pp. 167–172
Zhong, W., Dósa, G., & Tan, Z. (2007). On the machine scheduling problem with job delivery coordination. European Journal of Operational Research, 182(3), 1057–1072.CrossRef
Metadaten
Titel
An improved approximation algorithm for a scheduling problem with transporter coordination
verfasst von
Yinling Wang
Xin Han
Yong Zhang
Jacek Blazewicz
Publikationsdatum
02.11.2022
Verlag
Springer US
Erschienen in
Journal of Scheduling / Ausgabe 6/2023
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-022-00762-6

Weitere Artikel der Ausgabe 6/2023

Journal of Scheduling 6/2023 Zur Ausgabe

OriginalPaper

Scheduling on a graph with release times

OriginalPaper

Competitive algorithms for demand response management in a smart grid

OriginalPaper

Approximation algorithms for batch scheduling with processing set restrictions

EditorialNotes

Mathematical challenges in scheduling theory

OriginalPaper

A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints

Premium Partner

    Bildnachweise