✦ LIBER ✦

Algorithmic paradoxes of the single-machine total tardiness problem

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

Publisher: Springer US
Year: 2001
Tongue: English
Weight: 108 KB
Volume: 4
Category: Article
ISSN: 1094-6136
DOI: 10.1002/jos.69

No coin nor oath required. For personal study only.

✦ Synopsis

The paper deals with the single-machine total tardiness problem. It investigates the authors' most recent branch and bound algorithm and discovers the following paradoxes. Deleting a lower bound drastically improves the performance of the algorithm, while adding a stronger component, like a better decomposition rule, negatively a ects its performance. Guided by those paradoxes it develops a very fast branch algorithm that handles instances with up to 500 jobs. It also shows that the powerful recent result of Chang et al. (Operations Research Letters 1995; 17:221-229) can be further improved. Copyright ? 2001 John Wiley & Sons, Ltd.

📜 SIMILAR VOLUMES

A decomposition algorithm for the single

A decomposition algorithm for the single machine total tardiness problem

✍ C.N Potts; L.N Van Wassenhove 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 533 KB

Solution of the single machine total tar

Solution of the single machine total tardiness problem

✍ Wlodzimierz Szwarc; Federico Della Croce; Andrea Grosso 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 129 KB 👁 2 views

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, a

An efficient algorithm for the single ma

An efficient algorithm for the single machine tardiness problem

✍ Suna Kondakci; Ömer Kirca; Meral Azizoǧlu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 553 KB

Fast neighborhood search for the single

Fast neighborhood search for the single machine total weighted tardiness problem

✍ Özlem Ergun; James B. Orlin 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 154 KB

A heuristic for the single machine tardi

A heuristic for the single machine tardiness problem

✍ S.S. Panwalkar; M.L. Smith; C.P. Koulamas 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 518 KB

An experimental comparison of solution a

An experimental comparison of solution algorithms for the single-machine tardiness problem

✍ Kenneth R. Baker; James B. Martin 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 778 KB

## Abstract A basic problem in scheduling involves the sequencing of a set of independent tasks at a single facility with the objective of minimizing mean tardiness. Although the problem is relatively simple, the determination of an optimal sequence remains a challenging combinatorial problem. A nu