𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Solution of the single machine total tardiness problem

✍ Scribed by Wlodzimierz Szwarc; Federico Della Croce; Andrea Grosso

Publisher
Springer US
Year
1999
Tongue
English
Weight
129 KB
Volume
2
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

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(n) 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.

πŸ“œ SIMILAR VOLUMES

Decomposition and hybrid simulated annea
Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem
✍ Christos Koulamas πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 93 KB πŸ‘ 1 views

A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (P//T V ) by extending the decomposition principle embedded in the single-machine tardiness problem (1//T V ) to a parallel-machine setting. The subproblems generated by the decomposition are solved by an ef

Note: β€œSimultaneous optimization of effi
Note: β€œSimultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems”
✍ Michael X. Weng; Jose A. Ventura πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 280 KB πŸ‘ 1 views

n independent jobs are to be scheduled nonpreemptively on a single machine so as to minimize some performance measure. Federgruen and Mosheiov [ 21 show that a large class of such scheduling problems can be optimized by solving either a single instance or a finite sequence of instances of the so-cal

A parallel multisplitting solution of th
A parallel multisplitting solution of the least squares problem
✍ R. A. Renaut πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 143 KB πŸ‘ 2 views

The linear least squares problem, min x Ax-b 2 , is solved by applying a multisplitting(MS) strategy in which the system matrix is decomposed by columns into p blocks. The b and x vectors are partitioned consistently with the matrix decomposition. The global least squares problem is then replaced by

Converged solutions of the Newtonian ext
Converged solutions of the Newtonian extrudate-swell problem
✍ Georgios C. Georgiou; Andreas G. Boudouvis πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 85 KB πŸ‘ 1 views

Both the axisymmetric and the planar Newtonian extrudate-swell problems are solved using the standard and the singular finite element methods. In the latter method, special elements that incorporate the radial form of the stress singularity are used around the exit of the die. The convergence of eac