๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A note on the equivalence of two heuristics to minimize total tardiness

โœ Scribed by Bahram Alidaee; Suresh Gopalan

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
272 KB
Volume
96
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

โœฆ Synopsis

Over the last thirty years, many researchers have studied single machine static and deterministic scheduling with the objective of minimizing total tardiness. It has been established that the tardiness problem is NP-hard. So it is unlikely that a polynomial time algorithm can be found for developing optimal solutions to this problem. The Modified Due Date rule (MDD) is generally considered to be an efficient heuristic that deals with the tardiness problem. Recently, Panwalkar et al. have proposed the PSK rule as effective in dealing with tardiness. The purpose of this paper is to show that the PSK rule is an implementation of the MDD rule. Furthermore, the relationship between the MDD rule and the WI (Wilkeson and Irwin) rule is clarified.

๐Ÿ“œ SIMILAR VOLUMES

A hybrid algorithm for the one machine s
A hybrid algorithm for the one machine sequencing problem to minimize total tardiness
โœ V. Srinivasan ๐Ÿ“‚ Article ๐Ÿ“… 1971 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 568 KB

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing n jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relatio

A note on the complexity of family sched
A note on the complexity of family scheduling to minimize the number of late jobs
โœ T. C. Edwin Cheng; Zhaohui Liu; Yakov M. Shafransky ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Springer US ๐ŸŒ English โš– 65 KB ๐Ÿ‘ 2 views

The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and pro