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

12.01.2016 | Research paper

Parallel-machine scheduling with release dates and rejection

verfasst von: Liqi Zhang, Lingfa Lu

Erschienen in: 4OR | Ausgabe 2/2016

Einloggen

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

search-config
loading …

Abstract

In this paper, we consider the parallel-machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is a fixed constant, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem. When m is arbitrary, we present a 2-approximation algorithm for the problem.
Vorheriger Artikel Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness
Nächster Artikel Pooling heterogeneous products for manufacturing environments

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
Bartal Y, Leonardi S, Spaccamela AM, Sgall J, Stougie L (2000) Multi-processor scheduling with rejection. SIAM J Discret Math 13:64–78CrossRef
Cheng YS, Sun SJ (2009) Scheduling linear deteriorating jobs with rejection on a single machine. Eur J Oper Res 194:18–27CrossRef
Dosa G, He Y (2006) Scheduling with machine cost and rejection. J Comb Optim 12:337–350CrossRef
Engels DW, Karger DR, Kolliopoulos SG, Sengupta S, Uma RN, Wein J (2003) Techniques for scheduling with rejection. J Algorithms 49:175–191CrossRef
Epstein L, Noga J, Woeginger GJ (2002) On-line scheduling of unit time jobs with rejection: minimizing the total completion time. Oper Res Lett 30:415–420CrossRef
Hoogeveen H, Skutella M, Woeginger GJ (2003) Preemptive scheduling with rejection. Math Program 94:361–374CrossRef
Lawler EL (1973) Optimal sequencing a single machine subject to precedence constraints. Manag Sci 19:544–546CrossRef
Lu LF, Ng CT, Zhang LQ (2011) Optimal algorithms for single-machine scheduling with rejection to minimize the makespan. Int J Prod Econ 130:153–158CrossRef
Ma R, Yuan JJ (2013) On-line scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost. Inf Process Lett 113:593–598CrossRef
Seiden S (2001) Preemptive multiprocessor scheduling with rejection. Theor Comput Sci 262:437–458CrossRef
Shabtay D, Gaspar N, Kaspi M (2013) A survey on off-line scheduling with rejection. J Sched 16:3–28CrossRef
Steiner G, Zhang R (2011) Revised delivery-time quotation in scheduling with tardiness penalties. Oper Res 59:1504–1511CrossRef
Zhang LQ, Lu LF, Yuan JJ (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198:975–978CrossRef
Metadaten
Titel
Parallel-machine scheduling with release dates and rejection
verfasst von
Liqi Zhang
Lingfa Lu
Publikationsdatum
12.01.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
4OR / Ausgabe 2/2016
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-016-0304-4

Weitere Artikel der Ausgabe 2/2016

4OR 2/2016 Zur Ausgabe

Research paper

Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem

PhD Thesis

Heuristic and metaheuristic algorithms for the generation of optimal experimental designs

Research paper

A line search trust-region algorithm with nonmonotone adaptive radius for a system of nonlinear equations

Research Paper

Pooling heterogeneous products for manufacturing environments

Research Paper

Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness

Invited Survey

Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms

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