Theoretical Expectation versus Practical Performance of Jackson’s Heuristic

Abstract EN

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 m a x 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 m a x 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.