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

DOI10.1016/J.COR.2012.07.004MaRDI QIDQ339586zbMATH OpenOpenAlexFDO

Authors Shunji Tanaka, Mituhiko Araki

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

dynamic programmingexact algorithmLagrangian relaxationsequence-dependent setup timessingle-machine total weighted tardiness problem

Mathematics Subject Classification ID

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

Recommendations

• An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
• A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
• An exact algorithm for single-machine scheduling without machine idle time
• A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
• An iterated greedy algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

Cites work

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

Cited in

(31)

• On the mass COVID-19 vaccination scheduling problem
• Mixed integer formulations using natural variables for single machine scheduling around a common due date
• A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties
• An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem
• Parallel branch-and-price algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times
• On the exact solution of a large class of parallel machine scheduling problems
• Scatter search for minimizing weighted tardiness in a single machine scheduling with setups
• Dominance inequalities for scheduling around an unrestrictive common due date
• Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
• Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times
• Order assignment and scheduling under processing and distribution time uncertainty
• Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
• An iterated greedy algorithm for the planning of yarn‐dyeing boilers
• The third comprehensive survey on scheduling problems with setup times/costs
• A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times
• An iterated greedy algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
• scientific article; zbMATH DE number 495273 (Why is no real title available?)
• Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
• A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
• An exact exponential branch-and-merge algorithm for the single machine total tardiness 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
• Steelmaking-continuous casting scheduling problem with multi-position refining furnaces under time-of-use tariffs
• An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems
• A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
• Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network
• Exact and heuristic methods for a workload allocation problem with chain precedence constraints
• An exact algorithm for the precedence-constrained single-machine scheduling problem
• ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness
• Solving the single crane scheduling problem at rail transshipment yards

Describes a project that uses

Uses Software

• VRP

This page was built for publication: An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q339586)