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.90073MaRDI 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
Lagrangian relaxation; single-machine scheduling; dynamic programming; exact algorithm; machine idle time
Related Items
An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems, 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, An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times, Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems, A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem, Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times, An exact algorithm for the bi-objective timing problem, \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees, 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, Structured learning based heuristics to solve the single machine scheduling problem with release times and sum of completion times, Minimizing makespan on a single machine with release dates and inventory constraints, On the exact solution of a large class of parallel machine scheduling problems, A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, An exact algorithm for the precedence-constrained single-machine scheduling 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, Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date, A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems, An Exact Algorithm for the Single-Machine Earliness–Tardiness 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
