Randomized selection algorithm for online stochastic unrelated machines scheduling

DOI10.1007/s10878-020-00542-yzbMath1502.90082OpenAlexW3007431699MaRDI QIDQ2082193

Yanyan Li

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00542-y

zbMATH Keywords

online schedulingunrelated machinesexpected total weighted completion timerandomized selection algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic scheduling theory in operations research (90B36) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
• On-line scheduling to minimize average completion time revisited.
• Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines
• On-line scheduling of parallel machines to minimize total completion times
• Online scheduling of two uniform machines to minimize total completion times
• LP-based online scheduling: From single to parallel machines
• An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
• Stochastic online scheduling on unrelated machines
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• A \(2.28\)-competitive algorithm for online scheduling on identical machines
• Approximation Techniques for Average Completion Time Scheduling
• Single Machine Scheduling with Release Dates
• Approximation in stochastic scheduling
• Unrelated Machine Scheduling with Stochastic Processing Times
• On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
• Efficient Algorithms for Average Completion Time Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Optimal on-line algorithms for single-machine scheduling
• A New Approach to Online Scheduling
• Models and Algorithms for Stochastic Online Scheduling
• On Scheduling Fees to Prevent Merging, Splitting, and Transferring of Jobs
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

This page was built for publication: Randomized selection algorithm for online stochastic unrelated machines scheduling