A survey of algorithms for the single machine total weighted tardiness scheduling problem

DOI10.1016/0166-218X(90)90103-JzbMath0685.90059OpenAlexW2056466128WikidataQ127109988 ScholiaQ127109988MaRDI QIDQ1262207

T. S. Abdul-Razaq, Luk N. Van Wassenhove, Chris N. Potts

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90103-j

zbMATH Keywords

surveylexicographic orderLagrangean relaxationsingle machinebranch and bound algorithmstotal weighted tardinesscardinality order

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (43)

Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ A tabu search algorithm for the single machine total weighted tardiness problem ⋮ Single machine scheduling with interfering job sets ⋮ A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times ⋮ Metaheuristics for the single machine weighted quadratic tardiness scheduling problem ⋮ 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 ⋮ Effects of change of scale on optimality in a scheduling model with priorities and earliness/tardiness penalties ⋮ Scheduling parallel machines to minimize total weighted and unweighted tardiness ⋮ An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates ⋮ An improved particle swarm optimization for selective single machine scheduling with sequence dependent setup costs and downstream demands ⋮ Augmentations of consistent partial orders for the one-machine total tardiness problem ⋮ Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling ⋮ Scheduling a hybrid flowshop with batch production at the last stage ⋮ On heuristic search for the single machine total weighted tardiness problem - Some theoretical insights and their empirical verification ⋮ New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives ⋮ A new lower bounding scheme for the total weighted tardiness problem. ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Minimizing total tardiness on a single machine with unequal release dates ⋮ 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 learning effects and maintenance: a methodological note on some polynomial-time solvable cases ⋮ Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem ⋮ Predictive-reactive scheduling on a single resource with uncertain future jobs ⋮ Minimizing the weighted sum of squared tardiness on a single machine ⋮ A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine ⋮ Single machine scheduling to minimize total weighted tardiness ⋮ On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems ⋮ Scheduling a single machine to minimize a regular objective function under setup constraints ⋮ A HYBRID METAHEURISTIC FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS PROBLEM ⋮ The single-machine total tardiness problem with unequal release times and a linear deterioration ⋮ Minimizing total tardiness on a single machine with controllable processing times ⋮ 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 ⋮ Interval-indexed formulation based heuristics for single machine total weighted tardiness problem ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ A strategy for evolution of algorithms to increase the computational effectiveness of NP-hard scheduling problems ⋮ Scheduling jobs on parallel machines with sequence-dependent setup times ⋮ The single-machine total tardiness scheduling problem: review and extensions ⋮ A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines ⋮ Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem ⋮ One-Machine Sequencing to Minimize Total Tardiness: A Fourth Theorem for Emmons ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• Four solution techniques for a general one machine scheduling problem. A comparative study
• Technical Note—There are No Undiscovered Priority Index Sequencing Rules for Minimizing Total Delay Costs
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• State-space relaxation procedures for the computation of bounds to routing problems
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• On Dynamic Programming Methods for Assembly Line Balancing
• Coordinating Aggregate and Detailed Scheduling Decisions in the One-Machine Job Shop: Part I. Theory
• Coordinating Aggregate and Detailed Scheduling in the One-Machine Job Shop: II—Computation and Structure
• Minimizing Total Costs in One-Machine Scheduling
• A dual algorithm for the one-machine scheduling problem
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
• An experimental comparison of solution algorithms for the single-machine tardiness problem
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• A hybrid algorithm for the one machine sequencing problem to minimize total tardiness
• On the N-Job One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: A Branch-Bound Solution

This page was built for publication: A survey of algorithms for the single machine total weighted tardiness scheduling problem