Theoretical Expectation versus Practical Performance of Jackson's Heuristic

摘要

A basic 2-approximation heuristic was suggested by Jackson in early 50s last century for scheduling jobs with release times and due dates to minimize the maximum job lateness. The theoretical worst-case bound of 2 helps a little in practice, when the solution quality is important. The quality of the solution delivered by Jackson's heuristic is closely related to the maximum job processing time p(max) that occurs in a given problem instance and with the resultant interference with other jobs that such a long job may cause. We use the relationship of p(max) with the optimal objective value to obtain more accurate approximation ratio, which may drastically outperform the earlier known worst-case ratio of 2. This is proved, in practice, by our computational experiments.