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 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 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.