An exact algorithm for the precedence-constrained single-machine scheduling problem

DOI10.1016/J.EJOR.2013.02.048zbMath1317.90132OpenAlexW2170479205MaRDI QIDQ2355863

Shunji Tanaka, Shun Sato

Publication date: 28 July 2015

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

Full work available at URL: http://hdl.handle.net/2433/174100

zbMATH Keywords

Lagrangian relaxationschedulingdynamic programmingprecedence constraintssingle-machineexact algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (8)

Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ An exact dynamic programming algorithm for the precedence-constrained class sequencing problem ⋮ On the mass COVID-19 vaccination scheduling problem ⋮ Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date ⋮ Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ Order assignment and scheduling under processing and distribution time uncertainty ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems

Uses Software

• VRP

Cites Work

• Unnamed Item
• Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
• Single machine precedence constrained scheduling is a Vertex cover problem
• A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• A dynamic programming method for single machine scheduling
• On the approximability of average completion time scheduling under precedence constraints.
• An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
• Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems
• Dual decomposition of a single-machine scheduling problem
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• An exact algorithm for single-machine scheduling without machine idle time
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• Enhancing Lagrangian Dual Optimization for Linear Programs by Obviating Nondifferentiability
• New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling
• Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring
• 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
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks
• Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
• Single-Machine Scheduling with Precedence Constraints
• Scheduling with Precedence Constraints of Low Fractional Dimension
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness

This page was built for publication: An exact algorithm for the precedence-constrained single-machine scheduling problem