Theoretical expectation versus practical performance of Jackson's heuristic (Q1665791)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Theoretical expectation versus practical performance of Jackson's heuristic |
scientific article |
Statements
Theoretical expectation versus practical performance of Jackson's heuristic (English)
0 references
27 August 2018
0 references
Summary: 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.
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references