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

DOI10.1016/J.EJOR.2013.02.048MaRDI QIDQ2355863zbMATH OpenOpenAlexFDO

Authors 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

dynamic programmingexact algorithmschedulingsingle-machineprecedence constraintsLagrangian relaxation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

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

• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• 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
• A dynamic programming method for single machine scheduling
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle 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
• 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)

• On the mass COVID-19 vaccination scheduling problem
• A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
• A Precedence Graph Algorithm for the Shop Scheduling Problem
• A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Order assignment and scheduling under processing and distribution time uncertainty
• Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
• Exact algorithms for single-machine scheduling with time windows and precedence constraints
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date
• 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
• Single machine precedence constrained scheduling is a Vertex cover problem
• Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers
• An improved precedence rule for single machine sequencing problems with quadratic penalty

Describes a project that uses

Uses Software

• VRP

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)