𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on “Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”

✍ Scribed by F. Della Croce; E. Desmier; T. Garaix

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
171 KB
Volume
60
Category
Article
ISSN
0360-8352

No coin nor oath required. For personal study only.

✦ Synopsis

In a recent paper by Valente ''Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time" ', Computers & Industrial Engineering, 55, 663-675, 2008, several beam search approaches are compared on a large set of instances of the total weighted earlinesstardiness problem on single machine with jobs independent weights and no machine idle time. That problem is denoted 1jnmitj P j hE j þ P j wT j . This note points out that the standard iterated dynasearch procedure applied to that problem outperforms all the literature heuristics. Based on these results and others obtained on similar problems, we conclude that dynasearch for its efficiency and simplicity, should be used as a benchmark for future heuristics on those types of single machine no idle time problems.

📜 SIMILAR VOLUMES

A note on the single-machine scheduling
A note on the single-machine scheduling problem with minimum weighted completion time and maximum allowable tardiness
✍ Suresh Chand; Hans Schneeberger 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB

This paper analyzes the Smith-heuristic for the single-machine scheduling problem where the objective is to minimize the total weighted completion time subject to the constraint that the tardiness for any job does not exceed a prespecified maximum allowable tardiness. We identify several cases of th