Theoretical Expectation versus Practical Performance of Jackson’s Heuristic

Nodari Vakhania, Dante Pérez and Lester Carballo

Mathematical Problems in Engineering, 2015, vol. 2015, 1-10

Abstract:

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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2015/484671.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2015/484671.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:484671

DOI: 10.1155/2015/484671

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().