Worst‐case analysis of local search heuristics for the one‐machine total tardiness problem

Shiwei Chang, Hirofumi Matsuo and Guochun Tang

Naval Research Logistics (NRL), 1990, vol. 37, issue 1, 111-121

Abstract: In this article the worst‐case performance of four local search heuristics for the total tardiness problem is investigated. Since the denominator of the error ratio, which is the optimal objective value, may become zero, the derivation of the worst‐case relative error requires a careful mathematical treatment. After necessary definitions and notations are introduced, the worst‐case relative errors of two heuristics are shown to be infinite for a given number of jobs, while those of the other two are shown to be finite.

Date: 1990
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199002)37:13.0.CO;2-V

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:navres:v:37:y:1990:i:1:p:111-121

Access Statistics for this article

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