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

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/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/2, which, to our knowledge, is the tightest worst-case ratio bound available for the problem.