A note on the single-machine scheduling problem with minimum weighted completion time and maximum allowable tardiness
✍ Scribed by Suresh Chand; Hans Schneeberger
- Publisher
- John Wiley and Sons
- Year
- 1986
- Tongue
- English
- Weight
- 328 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
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 this problem for which the Smithheuristic is guaranteed to lead to optimal solutions. We also provide a worst-case analysis of the Smith-heuristic; the analysis shows that the fractional increase in the objective function value for the Smith-heuristic from the optimal solution is unbounded in the worst case.