| 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  . 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  , which, to our knowledge, is the tightest worst‐case ratio bound available for the problem. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006 |
