An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

DOI10.1016/j.cor.2012.07.004zbMath1349.90402OpenAlexW1978778741MaRDI QIDQ339586

Mituhiko Araki, Shunji Tanaka

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/160225

zbMATH Keywords

Lagrangian relaxationdynamic programmingsequence-dependent setup timesexact algorithmsingle-machine total weighted tardiness problem

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Mixed integer formulations using natural variables for single machine scheduling around a common due date, The third comprehensive survey on scheduling problems with setup times/costs, Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times, Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times, Scatter search for minimizing weighted tardiness in a single machine scheduling with setups, On the mass COVID-19 vaccination scheduling problem, Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness, Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date, An iterated greedy algorithm for the planning of yarn‐dyeing boilers, Solving the single crane scheduling problem at rail transshipment yards, Exact and heuristic methods for a workload allocation problem with chain precedence constraints, Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network, 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, ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness, Dominance inequalities for scheduling around an unrestrictive common due date, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties, Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints, 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, Steelmaking-continuous casting scheduling problem with multi-position refining furnaces under time-of-use tariffs

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• A GRASP based on DE to solve single machine scheduling problem with SDST
• Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
• A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
• An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups
• A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness
• A branch and bound method for the job-shop problem with sequence-dependent setup times
• The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
• A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times
• A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
• A dynamic programming method for single machine scheduling
• Scheduling in a sequence dependent setup environment with genetic search
• Generalized pairwise interchanges and machine scheduling
• Constraint-based scheduling: Applying constraint programming to scheduling problems.
• An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
• A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
• Earliness-tardiness scheduling with setup considerations
• A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time
• A branch \(\&\) bound method for the general-shop problem with sequence dependent setup-times
• An exact algorithm for single-machine scheduling without machine idle time
• Algorithms for single machine total tardiness scheduling with sequence dependent setups
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
• Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints
• A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times
• Enhancing stochastic search performance by value-biased randomization of heuristics
• Fast neighborhood search for the single machine total weighted tardiness problem
• 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
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times
• Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems
• A memetic algorithm for the total tardiness single machine scheduling problem