nach oben

Journal of Combinatorial Optimization

Erschienen in:

18.02.2020

Randomized selection algorithm for online stochastic unrelated machines scheduling

verfasst von: Xiaoyan Zhang, Ran Ma, Jian Sun, Zan-Bo Zhang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider an online stochastic unrelated machines scheduling problem. Specifically, a set of jobs arriving online over time must be randomly scheduled on the unrelated machines, which implies that the information of each job, including the release date and the weight, is not known until it is released. Furthermore, the actual processing time of each job is disclosed upon completion of this job. In addition, we focus on unrelated machines, which means that each job has a processing speed on every machine. Our goal is to minimize the expected total weighted completion time of all jobs. In this paper, we present a randomized selection algorithm for this problem and prove that the competitive ratio is a constant. Moreover, we show that it is asymptotic optimal for the online stochastic uniform machines scheduling problem when some parameters are bounded. Moreover, our proof does not require any probabilistic assumption on the job parameters.

Vorheriger Artikel Approximation algorithms for constructing required subgraphs using stock pieces of fixed length

Nächster Artikel An approximation algorithm for the uniform capacitated k-means problem

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

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

Chekuri C, Motwani R, Natarajan B, Stein C (2001) Approximation techniques for average completion time scheduling. SIAM J Comput 31:146–166MathSciNetCrossRef

Chou M, Liu H, Queyranne M, Simchi-levi D (2006) On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions. Oper Res 54:464–474MathSciNetCrossRef

Chou M, Queyranne M, Simchi-Levi D (2006) The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. Math Program 106:137–157MathSciNetCrossRef

Correa JR, Wagner MR (2009) LP-based online scheduling: from single to parallel machines. Math Program 119:109–136MathSciNetCrossRef

Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. In: Proceedings of the international conference on cumbinatorics (Calgary Canada), pp 69–87

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

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–326MathSciNetCrossRef

Gu MZ, Lu XW (2011) Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines. Ann Oper Res 191:97–113MathSciNetCrossRef

Gupta V, Moseley B, Uetz M, Xie Q (2017) Stochastic online scheduling on unrelated machines. In: International conference on integer programming and combinatorial optimization, IPCO 2017 book series: lecture notes in computer science, vol 10328, pp 228–240

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

Hoogeveen JA, Vestjens APA (1996) Optimal on-line algorithms for single-machine scheduling. Lect Notes Comput Sci 1084:404–414MathSciNetCrossRef

Lenstra JK, Rinoooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:343–362MathSciNetCrossRef

Liu PH, Lu XW (2009) Online scheduling of parallel machines to minimize total completion time. Comput Oper Res 36:2647–2652MathSciNetCrossRef

Liu PH, Lu XW (2009) Online scheduling of two uniform machines to minimize total completion times. J Ind Manag Optim 5:95–102MathSciNetCrossRef

Lübbecke E, Maurer O, Megow N, Wiese A (2016) A new approach to online scheduling: approximating the optimal competitive ratio. ACM Trans Algorithms 13:1–34MathSciNetCrossRef

Ma R, Tao JP (2018) An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. J Ind Manag Optim 14:497–510MathSciNetCrossRef

Megow N, Schulz AS (2004) Online scheduling to minimize average completion time revisited. Oper Res Lett 32:485–490MathSciNetCrossRef

Megow N, Uetz M, Vredeveld T (2006) Models and algorithms for stochastic online scheduling. Math Oper Res 31:513–525MathSciNetCrossRef

Mohring RH, Schulz A, Uetz M (1999) Approximation in stochastic schedule: the power of LP-based priority policies. J ACM 46:924–942MathSciNetCrossRef

Moulin H (2007) On scheduling fees to prevent merging, splitting, and transferring of jobs. Math Oper Res 32:266–283MathSciNetCrossRef

Sitters R (2010) Efficient algorithms for average completion time scheduling. Lect Notes Comput Sci 6080:411–423MathSciNetCrossRef

Skutella M, Sviridenko M, Uetz M (2016) Stochastic scheduling on unrelated machines. Math Oper Res 41:851–864MathSciNetCrossRef

Smith W (1956) Various optimizers for single stage production. Naval 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–224MathSciNetCrossRef

Tao JP, Huang RH, Liu TD (2015) A 2.28-competitive algorithm for online scheduling on identical machines. J Ind Manag Optim 11:185–198MathSciNetCrossRef

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

Titel: Randomized selection algorithm for online stochastic unrelated machines scheduling
verfasst von: Xiaoyan Zhang
Ran Ma
Jian Sun
Zan-Bo Zhang
Publikationsdatum: 18.02.2020
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00542-y

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 3/2022

Exact algorithms for finding constrained minimum spanning trees

Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

Fast computation of global solutions to the single-period unit commitment problem

Approximation algorithms for constructing required subgraphs using stock pieces of fixed length

An approximation algorithm for a general class of multi-parametric optimization problems

Online traveling salesman problem with time cost and non-zealous server

Premium Partner