nach oben

Journal of Combinatorial Optimization

Erschienen in:

29.09.2016

Online scheduling to minimize the total weighted completion time plus the rejection cost

verfasst von: Ran Ma, Jinjiang Yuan

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider the online scheduling on a single machine, in which jobs are released over time and each job can be either accepted and scheduled on the machine or rejected under a certain rejection cost. The goal is to minimize the total weighted completion time of the accepted jobs plus the total rejection cost of the rejected jobs. For this problem, we provide an online algorithm with a best possible competitive ratio of 2.

Vorheriger Artikel Two efficient values of cooperative games with graph structure based on -values

Nächster Artikel On Motzkin–Straus type results for non-uniform hypergraphs

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

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

Nur mit Berechtigung zugänglich

Anderson EJ, Potts CN (2004) Online scheduling of a single machine to minimize total weighted completion time. Math Oper Res 29(3):686–697MathSciNetCrossRefMATH

Bartal Y, Leonardi S, Spaccamela AM, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discret Math 13(1):64–78MathSciNetCrossRefMATH

Engels DW, Karger DR, Kolliopoulos SG, Sengupta S, Uma RN, Wein J (2003) Techniques for scheduling with rejection. J Algorithm 49:175–191MathSciNetCrossRefMATH

Goemans MX, Queyranne M, Schulz AS, Skutella M, Wang Y (2002) Single machine scheduling with release dates. SIAM J Discret Math 15:165–192MathSciNetCrossRefMATH

Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287–326MathSciNetCrossRefMATH

Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math Oper Res 22(3):513–544MathSciNetCrossRefMATH

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) Online 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–598MathSciNetCrossRefMATH

Ma R, Yuan JJ (2014) Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time. Int J Prod Econ 158:114–119CrossRef

Ma R, Tao JP, Yuan JJ (2016) Online scheduling with linear deteriorating jobs to minimize the total weighted completion time. Appl Math Comput 273:570–583MathSciNet

Philips C, Stein C, Wein J (1998) Minimizing average completion time in the presence of release dates. Math Program 82:199–223MathSciNetMATH

Schulz AS, Skutella M (1997) Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. In: Burkard R, Woeginger G (eds) Algorithms, ESA-97, Proceedings of the 5th annual European symposium on algorithms, Lecture Notes in Computer Science, vol 1284, Springer, Berlin, pp 416–429

Schulz AS, Skutella M (2002) The power of \(\alpha \)-points in preemptive single scheduling. J Sched 5:121–133MathSciNetCrossRefMATH

Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3–28MathSciNetCrossRefMATH

Smith WE (1956) Various optimizers for single-stage production. Nav Res Logist Q 3:59–66MathSciNetCrossRef

Tao JP (2014) A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time. Comput Oper Res 43:215–224MathSciNetCrossRefMATH

Tao JP, Chao ZJ, Xi YG (2010a) A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. J Ind Manag Optim 6(2):269–282MathSciNetCrossRefMATH

Tao JP, Chao ZJ, Xi YG, Tao Y (2010b) An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time. Inf Process Lett 110(8–9):325–330MathSciNetCrossRefMATH

Tao JP, Jiang H, Liu TD (2012) A 2.5-competitive online algorithm for \(Pm| r_j| \sum w_jC_j\). In: The 24th Chinese control and decision conference (CCDC), Taiyuan, pp 3184-3188

Tao JP, Liu TD (2013) WSPT’s competitive performance for minimizing the total weighted flow time: from single to parallel machines. Math Probl Eng, Article ID 343287

Vestjens APA (1997) On-line machine scheduling. Ph.D. Thesis, Eindhoven University of Technology, Netherlands

Titel: Online scheduling to minimize the total weighted completion time plus the rejection cost
verfasst von: Ran Ma
Jinjiang Yuan
Publikationsdatum: 29.09.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0083-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2017

Two-agent scheduling of time-dependent jobs

Triple-solution approach for the strip packing problem with two-staged patterns

The adjacent vertex distinguishing total chromatic numbers of planar graphs with

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

On maximum Wiener index of trees and graphs with given radius

Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans