A dynamic programming method for single machine scheduling
From MaRDI portal
Publication:1331548
DOI10.1016/0377-2217(94)90007-8zbMath0806.90064OpenAlexW2032786752MaRDI QIDQ1331548
Yuichi Nakamura, Toshihide Ibaraki
Publication date: 21 August 1994
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(94)90007-8
single machine schedulingstate-space relaxationsuccessive sublimation dynamic programmingweighted sums of earliness and tardiness
Related Items (21)
Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation ⋮ Minmax scheduling with job-classes and earliness-tardiness costs ⋮ An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times ⋮ Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem ⋮ Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date ⋮ An application of dynamic programming to assign pressing tanks at wineries ⋮ 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 ⋮ Exact approaches for solving a covering problem with capacitated subtrees ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ An exact approach for scheduling jobs with regular step cost functions on a single machine ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ An iterative dynamic programming approach for the temporal knapsack problem ⋮ Solving integrated process planning, dynamic scheduling, and due date assignment using metaheuristic algorithms ⋮ The use of dynamic programming in genetic algorithms for permutation problems ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ Single machine scheduling with symmetric earliness and tardiness penalties ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem
Cites Work
- A decomposition algorithm for the single machine total tardiness problem
- A Dynamic Programming Approach to Sequencing Problems
- A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
- Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
- State-space relaxation procedures for the computation of bounds to routing problems
- Minimizing Total Costs in One-Machine Scheduling
- Minimization of unsmooth functionals
This page was built for publication: A dynamic programming method for single machine scheduling
