SPT optimality (mostly) via linear programming

DOI10.1016/J.ORL.2022.12.007MaRDI QIDQ6161291zbMATH OpenFDO

Authors Woo-Hyung Cho, David B. Shmoys, Shane G. Henderson

Publication date 27 June 2023

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ORL.2022.12.007

zbMATH Keywords

gantt chartslinear programmingscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Recommendations

• How good are SPT schedules for fair optimality criteria
• On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time Problem
• SPT is optimally competitive for uniprocessor flow
• A note on a proof of SPT optimality for single-machine sequencing problems via the transportation problem
• The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem

Cites work

• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 876684 (Why is no real title available?)
• On the facial structure of scheduling polyhedra
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling algorithms
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• Structure of a simple scheduling polyhedron
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler

Cited in

(3)

• Total completion time scheduling under scenarios
• Total completion time scheduling under scenarios
• Mathematical models and optimal algorithms for lot scheduling considering job splitting and due dates in green logistics

This page was built for publication: SPT optimality (mostly) via linear programming

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