Journal of Scheduling · 1999 · 54 citations · 10 references
ManagementIndustrial EngineeringOperations ManagementProduction PlanningProduction SystemsSchedulingAssignment ProblemsCombinatorial OptimizationInteger ProgrammingMachine SchedulingProduction OptimizationTardiness MinimizationMaximum Tardiness MinimizationSingle Machine Makespan MinimizationSingle-machine Tardiness Scheduling
The paper deals with the solution of the single machine total tardiness model. It improves and generalizes an important rule to decompose the model into two subproblems. It also provides a O(n2) procedure to implement this rule and its generalization. Those two rules, along with some known results, are incorporated in a branch and bound algorithm that efficiently handles instances with up to 300 jobs and uses the original and maximally increased due dates to solve the original problem. Several properties that justify the modified due date version of our algorithm and produce an easy-to-implement new lower bound are established. The paper also provides an explanation why using the increased due dates may improve the efficiency of certain algorithms. Copyright © 1999 John Wiley & Sons, Ltd.
10
The Total Tardiness Problem: Review and Extensions
Christos Koulamas · Operations Research · 1994 · 230 citations