Time-Indexed Formulations and the Total Weighted Tardiness Problem
INFORMS journal on computingPublished 12 December 2007
Louis-Philippe Bigras, Michel Gamache, Gilles Savard
Citations49
SJR quartileQ1
SJR score1.44
SNIP1.64
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An acceleration strategy based on a decomposition of the time horizon into subperiods, where each subperiod is associated with a subproblem of the column-generation approach, is used to solve the linear relaxation of the total weighted tardiness problem.
Abstract
Asolution approach based on the column-generation technique is presented for solving a time-indexed formulation of the total weighted tardiness problem. An acceleration strategy based on a decomposition of the time horizon into subperiods, where each subperiod is associated with a subproblem of the column-generation approach, is used to solve the linear relaxation. Branching strategies and dominance rules are also applied to find the optimal integer solution. Using this new approach, it is possible to solve to optimality 117 out of 125 open problems of the OR-Library.
Keywords
EngineeringBusiness, Management and Accounting
Journal of the Operational Research SocietyInteger and Combinatorial Optimization
5,548 Citations1990H. P. Williams, George L. Nemhauser +1 more
Operations ResearchDecomposition Principle for Linear Programs
2,271 Citations1960George B. Dantzig, Philip Wolfe
A technique is presented for the decomposition of a linear program that permits the problem to be solved by alternate solutions of linear sub-programs representing its several parts and a coordinating program that is obtained from the parts by linear transformations.
IEEE Transactions on Systems Man and CyberneticsOptimization Theory of Large Systems
1,237 Citations1971Leon S. Lasdon, Daniel Tabak
Mathematical programming studiesLagrangean relaxation for integer programming
1,089 Citations1974Arthur M. Geoffrion
Lagrangian Relaxation for Integer Programming
978 Citations2009Arthur M. Geoffrion
It is a pleasure to write this commentary because it offers an opportunity to express my gratitude to several people who helped me in ways that turned out to be essential to the birth of [8].
Annals of discrete mathematicsA “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness
609 Citations1977Eugene L. Lawler
Mathematics of Operations ResearchScheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
491 Citations1997L. A. Hall, Andreas S. Schulz +2 more
This paper introduces two general techniques for the design and analysis of approximation algorithms for NP-hard scheduling problems in which the objective is to minimize the weighted sum of the job completion times.
Operations ResearchOne-Machine Sequencing to Minimize Certain Functions of Job Tardiness
346 Citations1969Hamilton Emmons
It proves theorems that establish the relative order in which pairs of jobs are processed in an optimal schedule; frequently they permit the jobs to be completely ordered, thus solving the problem without any searching.
INFORMS journal on computingAn Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
302 Citations2002Richard K. Congram, Chris N. Potts +1 more
Computational results show that an iterated dynasearch algorithm in which descents are performed a few random moves away from previous local minima is superior to other known local search procedures for the total weighted tardiness scheduling problem.
Operations ResearchA Branch and Bound Algorithm for the Total Weighted Tardiness Problem
276 Citations1985Chris N. Potts, Luk N. Van Wassenhove
This paper presents a new branch and bound algorithm for the single machine total weighted tardiness problem that obtains lower bounds using a Lagrangian relaxation approach with subproblems that are total weighted completion time problems.
Operations ResearchDynamic Programming Solution of Sequencing Problems with Precedence Constraints
241 Citations1978Linus Schrage, Kenneth R. Baker
These two results permit a very compact computer implementation of a dynamic programming algorithm for solving one-machine sequencing problems with precedence constraints and this algorithm appears to be much more efficient than previous ones for certain one- machine sequencing problems.
Discrete Applied MathematicsFormulating the single machine sequencing problem with release dates as a mixed integer program
240 Citations1990Martin Dyer, Laurence A. Wolsey
A hierarchy of relaxations obtained by combining enumeration of initial sequences with Smith's rule can be formulated as a linear programming problem in an enlarged space of variables and new valid inequalities for the problem are obtained.
Operations Research LettersAn exact algorithm for IP column generation
235 Citations1996François Vanderbeck, Laurence A. Wolsey
A combined branching and subproblem modification scheme is developed that generalizes existing approaches, and the use of lower bounds to reduce tailing-off effects is described.
Mathematical ProgrammingA time indexed formulation of non-preemptive single machine scheduling problems
235 Citations1992Jorge Pinho de Sousa, Laurence A. Wolsey
This work considers the formulation of non-preemptive single machine scheduling problems using time-indexed variables and derives a variety of valid inequalities, and shows the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities.
INFORMS journal on computingThe Shortest-Path Problem with Resource Constraints and <i>k</i>-Cycle Elimination for <i>k</i> ≥ 3
215 Citations2006Stefan Irnich, Daniel L. Villeneuve
It is shown that k-cycle elimination with k ≥ 3 can substantially improve the lower bounds of vehicle-routing problems with side constraints and a new definition of the dominance rule among labels for dealing with arbitrary values of k ≥ 2 is proposed.
Operations ResearchMinimizing Total Costs in One-Machine Scheduling
206 Citations1975A. H. G. Rinnooy Kan, B.J. Lageweg +1 more
A new algorithm is presented for a general cost function for a continuously available machine that can handle only one job at a time to find a schedule that minimizes total costs.
Discrete Applied MathematicsA survey of algorithms for the single machine total weighted tardiness scheduling problem
203 Citations1990Tariq S. Abdul-Razaq, Chris N. Potts +1 more
Four branch and bound algorithms use lower bounds obtained from the Lagrangean relaxation of machine capacity constraints and from dynamic programming state-space relaxation to minimize total weighted tardiness of jobs on a single machine.
INFORMS journal on computingTime-Indexed Formulations for Machine Scheduling Problems: Column Generation
197 Citations2000Marjan van den Akker, C.A.J. Hurkens +1 more
This paper discusses how Dantzig-Wolfe decomposition techniques can be applied to alleviate, at least partly, the difficulties associated with the size of time-indexed formulations, and shows that the application of these techniques still allows the use of cut generation techniques.
Mathematical ProgrammingMinimizing average completion time in the presence of release dates
170 Citations1998Cynthia A. Phillips, Clifford Stein +1 more
This paper gives the first constant-factor approximation algorithms for several variants of the single and parallel machine models and generalizes to the minimization of averageweighted completion time as well.
INFORMS journal on computingLocal Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem
170 Citations1998Herman Crauwels, Chris N. Potts +1 more
This paper introduces a new binary encoding scheme to represent solutions, together with a heuristic to decode the binary representations into actual sequences, and compares it to the usual "natural" permutation representation for descent, simulated annealing, threshold accepting, tabu search and genetic algorithms on a large set of test problems.
DSpace@MIT (Massachusetts Institute of Technology)On the n-job, one-machine, sequence-independent scheduling problem with tardiness penalties: a branch-bound solution
76 Citations2011Joel Shwimer
Mathematical ProgrammingA polyhedral approach to single-machine scheduling problems
67 Citations1999Marjan van den Akker, C.P.M. van Hoesel +1 more
This work gives complete characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex hull of the set of feasible partial schedules, i.e., schedules in which all jobs have to be started.
Management ScienceOn the <i>N</i>-Job One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: A Branch-Bound Solution
53 Citations1972Joel Shwimer
An efficient branch-bound algorithm is presented for solving the n-job, sequence-independent, single machine scheduling problem where the goal is to minimize the total penalty costs resulting from tardiness of jobs.
Mathematical ProgrammingOn the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
41 Citations2006Yunpeng Pan, Leyuan Shi
It is found that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program and the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation is shown.
Proximal ACCPM, a Cutting Plane Method for Column Generation and Lagrangian Relaxation: Application to the P-Median Problem
24 Citations2002O. du Merle, Jean-Philippe Vial
Proximal ACCPM is a variant of the analytic center cutting plane method, in which a proximal term is added to the barrier function that defines the center, that is used to solve the Lagrangian relaxation of the p-median problem on two sets of problem instances.
Mathematical ProgrammingThe relation of time indexed formulations of single machine scheduling problems to the node packing problem
19 Citations2002Hamish Waterer, ERIK JOHNSON +2 more
The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is established and then used to provide simple and intuitive alternate proofs of validity and maximality for previously known results on the facial structure of the scheduling problem.
Annals of Operations ResearchA Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor
13 Citations2004P. Prasad Babu, Laurent Péridy +1 more
A lower bound based on a Lagrangian decomposition is presented and it seems to prove that a trade-off between a tight lower bound and time consuming in the enumeration process can be a good strategy.