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/2019

02.02.2019

A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time

verfasst von: Tianyu Wang, Odile Bellenguez-Morineau

Erschienen in: Journal of Scheduling | Ausgabe 6/2019

Einloggen

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

search-config
loading …

Abstract

This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as \(P|p_{j}=1,\text {in-tree}|\sum C_{j}\) with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly \( \mathcal {NP} \)-hard.
Vorheriger Artikel Single-machine scheduling with job-dependent machine deterioration

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
Baptiste, P., & Timkovsky, V. G. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28(5), 205–212.CrossRef
Baptiste, P., Brucker, P., Knust, S., & Timkovsky, V. G. (2004). Ten notes on equal-processing-time scheduling. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2(2), 111–127.
Brucker, P., Hurink, J., & Knust, S. (2003). A polynomial algorithm for \({P}|p_j=1, r_j, outtree|\sum {C}_j\). Mathematical Methods of Operations Research, 56(3), 407–412.
Garey, M., Johnson, D., Tarjan, R., & Yannakakis, M. (1983). Scheduling opposing forests. SIAM Journal on Algebraic Discrete Methods, 4(1), 72–93.CrossRef
Garey, M. R., & Johnson, D. S. (2002). Computers and intractability (Vol. 29). New York: W. H. Freeman.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.CrossRef
Hu, T. C. (1961). Parallel sequencing and assembly line problems. Operations Research, 9(6), 841–848.CrossRef
Huo, Y., & Leung, J. Y.-T. (2006). Minimizing mean flow time for UET tasks. ACM Transactions on Algorithms (TALG), 2(2), 244–262.CrossRef
Prot, D., & Bellenguez-Morineau, O. (2018). A survey on how the structure of precedence constraints may change the complexity class of scheduling problems. Journal of Scheduling, 21(1), 3–16.CrossRef
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (4th ed., p. 22). Springer.
Metadaten
Titel
A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time
verfasst von
Tianyu Wang
Odile Bellenguez-Morineau
Publikationsdatum
02.02.2019
Verlag
Springer US
Erschienen in
Journal of Scheduling / Ausgabe 6/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-019-00602-0

Weitere Artikel der Ausgabe 6/2019

Journal of Scheduling 6/2019 Zur Ausgabe

OriginalPaper

Shop scheduling problems with pliable jobs

OriginalPaper

On the parameterized tractability of the just-in-time flow-shop scheduling problem

OriginalPaper

Single-machine scheduling with job-dependent machine deterioration

OriginalPaper

Sequencing assembly lines to facilitate synchronized just-in-time part supply

OriginalPaper

Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints

OriginalPaper

Single machine scheduling with stochastically dependent times

Premium Partner

    Bildnachweise