An exact algorithm for the precedence-constrained single-machine scheduling problem
From MaRDI portal
Publication:2355863
DOI10.1016/j.ejor.2013.02.048zbMath1317.90132OpenAlexW2170479205MaRDI QIDQ2355863
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
Lagrangian relaxationschedulingdynamic programmingprecedence constraintssingle-machineexact algorithm
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
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
