An exact algorithm for the precedence-constrained single-machine scheduling problem
From MaRDI portal
dynamic programmingexact algorithmLagrangian relaxationprecedence constraintsschedulingsingle-machine
Lua error in Module:PublicationMSCList at line 28: attempt to call field 'getDbData' (a nil value).
Lua error in Module:PublicationShowAbstract at line 21: attempt to call field 'getDbData' (a nil value).
Recommendations
- An exact algorithm for single-machine scheduling without machine idle time
- Exact algorithms for single-machine scheduling with time windows and precedence constraints
- An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
- A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
- An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
Cites work
- A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
- A dynamic programming method for single machine scheduling
- A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
- A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
- 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
- An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
- An exact algorithm for single-machine scheduling without machine idle time
- An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem
- Approximating Precedence-Constrained Single Machine Scheduling by Coloring
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Dual decomposition of a single-machine scheduling problem
- Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
- Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
- Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability
- Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
- Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks
- scientific article; zbMATH DE number 3550186 (Why is no real title available?)
- Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling
- Near-optimal solutions and large integrality gaps for almost all instances of single-machine precedence-constrained scheduling
- New exact algorithms for one-machine earliness-tardiness scheduling
- On the approximability of average completion time scheduling under precedence constraints.
- On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
- One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- Scheduling with Precedence Constraints of Low Fractional Dimension
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Single machine precedence constrained scheduling is a Vertex cover problem
- Single-Machine Scheduling with Precedence Constraints
- Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems
Cited in
(15)- Single machine precedence constrained scheduling is a Vertex cover problem
- A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile
- An improved precedence rule for single machine sequencing problems with quadratic penalty
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- 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
- 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 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
- Exact algorithms for single-machine scheduling with time windows and precedence constraints
- A Precedence Graph Algorithm for the Shop Scheduling Problem
This page was built for publication: An exact algorithm for the precedence-constrained single-machine scheduling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355863)
