Precedence theorems and dynamic programming for the single-machine weighted tardiness problem

DOI10.1016/j.ejor.2018.06.004zbMath1403.90362OpenAlexW2756714062MaRDI QIDQ1991104

Stefan Creemers, Roel Leus, Salim Rostami

Publication date: 30 October 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.12210/19410

zbMATH Keywords

schedulingdynamic programmingsingle machineprecedence constraintsweighted tardiness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers

Uses Software

• RanGen

Cites Work

• Unnamed Item
• Exact algorithms for single-machine scheduling with time windows and precedence constraints
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• A dynamic programming method for single machine scheduling
• Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems
• Dual decomposition of a single-machine scheduling problem
• An exact algorithm for single-machine scheduling without machine idle time
• An exact algorithm for the precedence-constrained single-machine scheduling problem
• Rangen: A random network generator for activity-on-the-node networks
• Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
• Technical Note—A Note on the Weighted Tardiness Problem
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Minimizing Total Costs in One-Machine Scheduling
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Single-Machine Scheduling with Precedence Constraints
• New Precedence Theorems for One-Machine Weighted Tardiness
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness