Scheduling to approximate minimization objectives on identical machines

DOI10.4230/LIPICS.ICALP.2019.86MaRDI QIDQ5091246zbMATH OpenFDO

Authors Benjamin Moseley

Publication date 21 July 2022

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

zbMATH Keywords

approximation algorithmsLP roundingscheduling

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• The geometry of scheduling
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• scientific article; zbMATH DE number 871909
• Approximation schemes for scheduling on parallel machines
• Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays

Cites work

• A fully polynomial approximation scheme for the total tardiness problem
• A primal-dual approximation algorithm for min-sum single-machine scheduling problems
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities
• Fair scheduling via iterative quasi-uniform sampling
• How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 7204483 (Why is no real title available?)
• On the performance of Smith's rule in single-machine scheduling with nonlinear cost
• Single machine scheduling to minimize total weighted tardiness
• The geometry of scheduling
• Valid inequalities for mixed 0-1 programs
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(7)

• Scheduling with a minimum number of machines
• Minimizing the number of machines for minimum length schedules
• Fair scheduling via iterative quasi-uniform sampling
• An Optimal Control Framework for Online Job Scheduling with General Cost Functions
• A water-filling primal-dual algorithm for approximating nonlinear covering problems
• Approximating Real-Time Scheduling on Identical Machines
• A water-filling primal-dual algorithm for approximating nonlinear covering problems

This page was built for publication: Scheduling to approximate minimization objectives on identical machines

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