A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
From MaRDI portal
Publication:2434288
DOI10.1007/s10951-011-0242-0zbMath1280.90073OpenAlexW2023149476MaRDI QIDQ2434288
Publication date: 5 February 2014
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/156178
Related Items (24)
Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ A hybrid heuristic approach for single machine scheduling with release times ⋮ Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times ⋮ An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times ⋮ An exact algorithm for the bi-objective timing problem ⋮ Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time ⋮ On the mass COVID-19 vaccination scheduling problem ⋮ Minimizing makespan on a single machine with release dates and inventory constraints ⋮ Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date ⋮ A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ On the exact solution of a large class of parallel machine scheduling problems ⋮ 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 ⋮ A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ Order assignment and scheduling under processing and distribution time uncertainty ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ Structured learning based heuristics to solve the single machine scheduling problem with release times and sum of completion times ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem
Cites Work
- A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
- Preemption in single machine earliness/tardiness scheduling
- A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- A practical use of Jackson's preemptive schedule for solving the job shop problem
- Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates
- A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
- An algorithm for single machine sequencing with release dates to minimize total weighted completion time
- Scheduling with release dates on a single machine to minimize total weighted completion time
- A time indexed formulation of non-preemptive single machine scheduling problems
- A dynamic programming method for single machine scheduling
- The job-shop problem and immediate selection
- Adjustment of heads and tails for the job-shop problem
- A dynamic programming algorithm for single machine scheduling with ready times
- Constraint-based scheduling: Applying constraint programming to scheduling problems.
- An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
- A polyhedral approach to single-machine scheduling problems.
- Optimal timing of a sequence of tasks with general completion costs
- Using short-term memory to minimize the weighted number of late jobs on a single machine.
- A branch and bound approach for single machine scheduling with earliness and tardiness penalties
- An exact algorithm for single-machine scheduling without machine idle time
- Algorithms for a class of single-machine weighted tardiness and earliness problems
- The one-machine problem with earliness and tardiness penalties
- Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints
- A branch and bound procedure to minimize mean absolute lateness on a single processor
- 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
- Scheduling of a single machine to minimize total weighted completion time subject to release dates
- A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
- Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
- An Algorithm for Solving the Job-Shop Problem
- State-space relaxation procedures for the computation of bounds to routing problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates
- A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
- Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
- Single-machine scheduling with early and tardy completion costs
This page was built for publication: A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time