Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling

DOI10.4230/LIPICS.STACS.2018.43MaRDI QIDQ3304142zbMATH OpenFDO

Authors Sven Jäger, Martin Skutella

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1801.01105

zbMATH Keywords

approximation algorithmparallel machinesstochastic schedulingList schedulingweighted shortest (expected) processing time rule

Mathematics Subject Classification ID

Approximation algorithms (68W25) Stochastic scheduling theory in operations research (90B36)

Recommendations

• Lower bounds for Smith's rule in stochastic machine scheduling
• Approximation results in parallel machines stochastic scheduling
• Analysis of Smith's rule in stochastic machine scheduling
• scientific article; zbMATH DE number 1418273
• Approximation in stochastic scheduling

Cites work

• scientific article; zbMATH DE number 6677416 (Why is no real title available?)
• scientific article; zbMATH DE number 871909 (Why is no real title available?)
• scientific article; zbMATH DE number 6472636 (Why is no real title available?)
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• A PTAS for minimizing the total weighted completion time on identical parallel machines.
• An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule
• Analysis of Smith's rule in stochastic machine scheduling
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm
• Approximation in stochastic scheduling
• Approximation results in parallel machines stochastic scheduling
• Approximation techniques for average completion time scheduling
• Models and Algorithms for Stochastic Online Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime
• Scheduling with Random Service Times
• Single machine scheduling with release dates
• Stochastic Online Scheduling Revisited
• Stochastic online scheduling on unrelated machines
• Stochastic scheduling problems I — General strategies
• Turnpike Optimality of Smith's Rule in Parallel Machines Stochastic Scheduling
• Unrelated machine scheduling of jobs with uniform Smith ratios
• Unrelated machine scheduling with stochastic processing times
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

Cited in

(8)

• The expected competitive ratio for weighted completion time scheduling
• Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines
• Greed works -- online algorithms for unrelated machine stochastic scheduling
• Approximation results in parallel machines stochastic scheduling
• Analysis of Smith's rule in stochastic machine scheduling
• Lower bounds for Smith's rule in stochastic machine scheduling
• On index policies for stochastic minsum scheduling
• STACS 2004

This page was built for publication: Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304142)