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

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.