A heuristic for maximizing the number of on‐time jobs on two uniform parallel machines

Christos Koulamas and George J. Kyparisis

Naval Research Logistics (NRL), 2006, vol. 53, issue 6, 568-575

Abstract: We consider the problem of maximizing the number of on‐time jobs on two uniform parallel machines. We show that a straightforward extension of an algorithm developed for the simpler two identical parallel machines problem yields a heuristic with a worst‐case ratio bound of at least $5\over 3$. We then show that the infusion of a “look ahead” feature into the aforementioned algorithm results in a heuristic with the tight worst‐case ratio bound of $3\over 2$, which, to our knowledge, is the tightest worst‐case ratio bound available for the problem. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006

Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.20161

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:wly:navres:v:53:y:2006:i:6:p:568-575

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().