A Branch and Bound Algorithm for the Total Weighted Tardiness Problem

DOI10.1287/OPRE.33.2.363zbMath0566.90046OpenAlexW2113856408MaRDI QIDQ3682221

Chris N. Potts, Luk N. Van Wassenhove

Publication date: 1985

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.33.2.363

zbMATH Keywords

Lagrangian relaxationsingle machinelower boundsbranch and bound algorithmtotal weighted tardinessdominance rulesComputational experiments

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (65)

Scheduling jobs and maintenance activities on parallel machines ⋮ Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times ⋮ A dynamic programming method for single machine scheduling ⋮ Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions ⋮ A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem ⋮ Improving the performance of enumerative search methods. I: Exploiting structure and intelligence ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs ⋮ A tabu search algorithm for the single machine total weighted tardiness problem ⋮ Scheduling on parallel identical machines to minimize total tardiness ⋮ A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times ⋮ Weighted tardiness for the single machine scheduling problem:an examination of precedence theorem productivity ⋮ A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date ⋮ Scheduling parallel machines to minimize total weighted and unweighted tardiness ⋮ Two due date assignment problems in scheduling a single machine ⋮ Real-time scheduling of an automated manufacturing center ⋮ Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling ⋮ Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems ⋮ New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ A new lower bounding scheme for the total weighted tardiness problem. ⋮ A Benders decomposition approach for order acceptance and scheduling problem: a robust optimization approach ⋮ New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem ⋮ A GRASP based on DE to solve single machine scheduling problem with SDST ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ A controlled search simulated annealing method for the single machine weighted tardiness problem ⋮ Column generation for extended formulations ⋮ Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ FMS scheduling based on timed Petri net model and reactive graph search ⋮ Minimizing total tardiness on a single machine with unequal release dates ⋮ Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups ⋮ An exact approach for the personnel task rescheduling problem with task retiming ⋮ 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 ⋮ Single machine scheduling with flow time and earliness penalties ⋮ Minimizing the weighted sum of squared tardiness on a single machine ⋮ Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem ⋮ A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine ⋮ A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem ⋮ Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment ⋮ Single machine scheduling to minimize total weighted tardiness ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ Metaheuristics for a scheduling problem with rejection and tardiness penalties ⋮ On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems ⋮ A two-stage assembly-type flowshop scheduling problem for minimizing total tardiness ⋮ Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty ⋮ A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times ⋮ A population-based variable neighborhood search for the single machine total weighted tardiness problem ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ A survey of algorithms for the single machine total weighted tardiness scheduling problem ⋮ The use of dynamic programming in genetic algorithms for permutation problems ⋮ Scheduling jobs on parallel machines with sequence-dependent setup times ⋮ Single machine earliness and tardiness scheduling ⋮ A branch and bound algorithm for the two-stage assembly scheduling problem ⋮ Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization ⋮ The one machine scheduling problem: insertion of a job under the real-time constraint ⋮ Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem ⋮ Machine scheduling models in environmentally focused chemical manufacturing ⋮ Cellular control of manufacturing systems ⋮ Fast neighborhood search for the single machine total weighted tardiness problem ⋮ Scheduling identical parallel machines to minimize total weighted completion time ⋮ One-Machine Sequencing to Minimize Total Tardiness: A Fourth Theorem for Emmons ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem ⋮ The two-machine flowshop scheduling problem with sequence-independent setup times: new lower bounding strategies

This page was built for publication: A Branch and Bound Algorithm for the Total Weighted Tardiness Problem