Average and worst-case analysis of heuristics for the maximum tardiness problem

DOI10.1016/0377-2217(86)90190-6MaRDI QIDQ1080771zbMATH OpenOpenAlexFDO

Authors Nicholas G. Hall, Wansoo T. Rhee

Publication date 1986

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(86)90190-6

zbMATH Keywords

average errorheuristic approachesknown ready times, processing times and due datesmaximum tardiness problemNonparametric statistical testssingle processorworst-case performance bounds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)

Review text

We study the problem of scheduling n jobs with known ready times, processing times and due dates, on a single processor, so as to minimize the tardiness of the job which is latest relative to its due date. We develop a number of heuristic approaches for this problem and study their average error (heuristic value compared to the optimal solution value), over a large number of randomly generated problems. We use linear programming to estimate worst-case performance bounds for all the heuristics. Nonparametric statistical tests show a very strong relationship between worst-case and average-case error, and also between worst-case error and the frequency with which the heuristics identify optimal solutions.

Recommendations

• scientific article; zbMATH DE number 4121743
• A greedy heuristic for the mean tardiness sequencing problem
• The worst-case performance ratio with time-dependent single-scheduling problems
• A heuristic for the single machine tardiness problem
• Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

Cites work

• A decision-theoretic framework for comparing heuristics
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• scientific article; zbMATH DE number 3471786 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• Sequencing with due-dates and early start times to minimize maximum tardiness
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Worst-Case Analysis of Heuristic Algorithms

Cited in

(4)

• A note on the equivalence of two heuristics to minimize total tardiness
• Theoretical expectation versus practical performance of Jackson's heuristic
• Heuristic methods and applications: A categorized survey
• scientific article; zbMATH DE number 4121743 (Why is no real title available?)

This page was built for publication: Average and worst-case analysis of heuristics for the maximum tardiness problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1080771)