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
4OR
Erschienen in: 4OR 1/2019

16.06.2018 | Research paper

A note on posterior tight worst-case bounds for longest processing time schedules

verfasst von: Johnny C. Ho, Ivar Massabò, Giuseppe Paletta, Alex J. Ruiz-Torres

Erschienen in: 4OR | Ausgabe 1/2019

Einloggen

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

search-config
loading …

Abstract

This note proposes and analyzes a posterior tight worst-case bound for the longest processing time (LPT) heuristic for scheduling independent jobs on identical parallel machines with the objective of minimizing the makespan. It makes natural remarks on the well-known posterior worst-case bounds, and shows that the proposed bound can complement the well-known posterior bounds to synergistically achieve a better posterior worst-case bound for the LPT heuristic. Moreover, it gives some insight on LPT asymptotical optimality.
Vorheriger Artikel A Branch & Price algorithm for the minimum cost clique cover problem in max-point tolerance graphs
Nächster Artikel Integrating order picking and vehicle routing decisions

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
Literatur
Blocher JD, Chand S (1991) Scheduling of parallel processors: a posterior bound on LPT sequencing and a two-step algorithm. Naval Res Logist 38:273–287CrossRef
Blocher JD, Sevastyanov S (2015) A note on the Coffman–Sethi bound for LPT scheduling. J Sched 18:325–327CrossRef
Chen B, Potts CN, Woeginger GJ (1998) A review of machine scheduling: complexity, algorithms and approximability. In: Du DZ, Pardalos P (eds) Handbook of combinatorial optimization, vol 3. Kluwer Academic, Dordrecht, pp 21–169
Cheng TCE, Sin CCS (1990) A state-of-the-art review of parallel-machine scheduling research. Eur J Oper Res 47:271–292CrossRef
Coffman EG Jr, Garey MR, Johnson DS (1978) An application of bin-paking to multiprocessor scheduling. SIAM J Comput 7:1–17CrossRef
Coffman EG Jr, Lueker GS, Rinnooy Kan AHG (1988) Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics. Manag. Sci. 34:266–290CrossRef
Coffman EG Jr, Sethi R (1976) A generalized bound on LPT sequencing. RAIRO Inf 10:17–25
Dell’Amico M, Martello S (1995) Optimal scheduling of tasks on identical parallel processors. ORSA J Comput 7:191–200CrossRef
Frenk JBG, Rinnooy Kan AHG (1986) The rate of convergence to optimality of the LPT rule. Discrete Appl Math 14:187–197CrossRef
Frenk JBG, Rinnooy Kan AHG (1987) The asymptotic optimality of the LPT rule. Math Oper Res 12:241–254CrossRef
Garey MR, Johnson DS (1979) Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco
Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45:1563–1581CrossRef
Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:416–429CrossRef
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326CrossRef
Gupta JND, Ruiz-Torres AJ (2001) LISTFIT heuristic for minimizing makespan on identical parallel machines. Prod Plan Control 12:28–36CrossRef
Ibarra OH, Kim CE (1977) Heuristic algorithms for scheduling independent tasks on nonidentical processors. J Assoc Comput Mach 24:280–289CrossRef
Karmarkar N, Karp RM (1982) The differencing method of set partitioning. Technical report UCB/CSD 82/113. University of California, Berkeley
Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: algorithms and complexity. In: Graves SC, Rinnooy Kan AHG, Zipkin PH (eds) Handbooks in operations research and management science, vol 4. Elsevier Science Publishers B.V., Amsterdam
Lee CY, Massey JD (1988) Multiprocessor scheduling: combining LPT and MULTIFIT. Discrete Appl Math 20:233–242CrossRef
Massabò I, Paletta G, Ruiz-Torres AJ (2016) A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem. J Sched 19(2):207–211CrossRef
Mokotoff E (2001) Parallel machine scheduling problem: a survey. Asia Pac J Oper Res 18:193–242
Paletta G, Pietramala P (2007) A new approximation algorithm for the nonpreemptive scheduling of independent jobs on identical parallel processors. SIAM J Discrete Math 21:313–328CrossRef
Paletta G, Vocaturo F (2010) A short note on an advance in estimating the worst-case performance ratio of the MPS algorithm. SIAM J Discrete Math 23:2198–2203CrossRef
Metadaten
Titel
A note on posterior tight worst-case bounds for longest processing time schedules
verfasst von
Johnny C. Ho
Ivar Massabò
Giuseppe Paletta
Alex J. Ruiz-Torres
Publikationsdatum
16.06.2018
Verlag
Springer Berlin Heidelberg
Erschienen in
4OR / Ausgabe 1/2019
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-018-0381-7

Weitere Artikel der Ausgabe 1/2019

4OR 1/2019 Zur Ausgabe

Research Paper

A Branch & Price algorithm for the minimum cost clique cover problem in max-point tolerance graphs

Acknowledgements

Acknowledgement to referees

Research Paper

Advertising and forecasting investments of a newsvendor

PhD Thesis

A methodological framework for evaluating metaheuristics: an application to vehicle routing

PhD Thesis

Integrating order picking and vehicle routing decisions

Invited Survey

A selective survey of game-theoretic models of closed-loop supply chains

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Zur Marktübersicht
    Bildnachweise