A note on the single‐machine scheduling problem with minimum weighted completion time and maximum allowable tardiness

Suresh Chand and Hans Schneeberger

Naval Research Logistics Quarterly, 1986, vol. 33, issue 3, 551-557

Abstract: 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 tradiness for any job does not exceed a prespecified maximum allowable tardiness. We identify several cases of this problem for which the Smith‐heuristic 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.

Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1002/nav.3800330319

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:33:y:1986:i:3:p:551-557

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().