Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling

DOI10.4230/LIPICS.STACS.2018.43zbMATH Open1487.90335arXiv1801.01105MaRDI QIDQ3304142FDOQ3304142

Authors: Sven Jäger, Martin Skutella 

Publication date: 5 August 2020

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

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

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)

Cites Work

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

Cited In (8)

• The expected competitive ratio for weighted completion time scheduling
• Analysis of Smith's rule in stochastic machine scheduling
• Greed works -- online algorithms for unrelated machine stochastic scheduling
• Lower bounds for Smith's rule in stochastic machine scheduling
• Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines
• Approximation results in parallel machines stochastic 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)