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

14.01.2016 | Research paper

Improved algorithms for single machine scheduling with release dates and rejections

verfasst von: Cheng He, Joseph Y.-T. Leung, Kangbok Lee, Michael L. Pinedo

Erschienen in: 4OR | Ausgabe 1/2016

Einloggen

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

search-config
loading …

Abstract

We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.
Vorheriger Artikel Light on the infinite group relaxation I: foundations and taxonomy
Nächster Artikel Assortment optimization under a multinomial logit model with position bias and social influence

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
Anhänge
Nur mit Berechtigung zugänglich
Literatur
Carnes T, Shmoys D (2008) Primal-dual schema for capacitated covering problems. In: Lodi A, Panconesi A, Rinaldi G (eds) Proceedings of the thirteenth international conference on integer programming and combinatorial optimization (IPCO ‘08). Springer, Berlin, pp 288–302
Csirik J, Frenk JBG, Labbe M, Zhang S (1991) Heuristics for the 0–1 min-knapsack problem. Acta Cybern 10(1–2):15–20
Gens GV, Levner EV (1981) Fast approximation algorithm for job sequencing with deadlines. Discrete Appl Math 3(4):313–318CrossRef
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
Guntzer M, Jungnickel D (2000) Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem. Oper Res Lett 26(2):55–66CrossRef
Lu LF, Ng CT, Zhang LQ (2011) Optimal algorithms for single-machine scheduling with rejection to minimize the makespan. Int J Prod Econ 130(2):153–158CrossRef
Pinedo M (2012) Scheduling—theory, algorithms, and systems, 4th edn. Springer, Berlin
Sahni S (1976) Algorithms for scheduling independent tasks. J ACM 23(1):116–127CrossRef
Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3–28CrossRef
Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212:1–11CrossRef
Tamir A (1998) Fully polynomial approximation schemes for locating a tree-shaped facility: a generalization of the knapsack problem. Discrete Appl Math 87(1):229–243CrossRef
Zhang LQ, Lu LF, Yuan JJ (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198:975–978CrossRef
Zhang LQ, Lu LF, Yuan JJ (2010) Single-machine scheduling under the job rejection constraint. Theor Comput Sci 411(16):1877–1882CrossRef
Metadaten
Titel
Improved algorithms for single machine scheduling with release dates and rejections
verfasst von
Cheng He
Joseph Y.-T. Leung
Kangbok Lee
Michael L. Pinedo
Publikationsdatum
14.01.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
4OR / Ausgabe 1/2016
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-016-0303-5

Weitere Artikel der Ausgabe 1/2016

4OR 1/2016 Zur Ausgabe

Invited Survey

Light on the infinite group relaxation I: foundations and taxonomy

PhD Thesis

Secure vehicle routing: models and algorithms to increase security and reduce costs in the cash-in-transit sector

Research paper

Assortment optimization under a multinomial logit model with position bias and social influence

Research paper

Mean-value at risk portfolio efficiency: approaches based on data envelopment analysis models with negative data and their empirical behaviour

PhD Thesis

Mathematical programming approaches to pricing problems

PhD Thesis

Robust linear programming; optimal sizing of an hybrid energy stand-alone system

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