𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Kenneth R. Baker; James B. Martin

Publisher
John Wiley and Sons
Year
1974
Tongue
English
Weight
778 KB
Volume
21
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

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 number of algorithms have been developed for finding solutions, and this paper reports a comparative evaluation of these procedures. Computer programs for five separate algorithms were written and all were run on a data base designed to highlight computational differences. Optimizing algorithms developed by Emmons and by Srinivasan appeared to be particularly efficient in the comparative study.

πŸ“œ SIMILAR VOLUMES

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

Algorithmic paradoxes of the single-mach
Algorithmic paradoxes of the single-machine total tardiness problem
✍ Wlodzimierz Szwarc; Andrea Grosso; Federico Della Croce πŸ“‚ Article πŸ“… 2001 πŸ› Springer US 🌐 English βš– 108 KB

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 d