Analysis of a linear programming heuristic for scheduling unrelated parallel machines

A heuristic method which uses linear programming to form a partial schedule leaving at most m−1 jobs unscheduled and which has a (best possible) worst-case performance ratio of 2 and a computational requirement which is polynomial in n although it is exponential in m.

Abstract

Each of n jobs is to be processed without interruption on one of m unrelated parallel machines. The objectives is to minimize the maximum completion time. A heuristic method is presented, the first stage of which uses linear programming to form a partial schedule leaving at most m−1 jobs unscheduled: the second stage schedules these m−1 jobs using an enumerative method. For m≥3, it is shown that the heuristic has a (best possible) worst-case performance ratio of 2 and has a computational requirement which is polynomial in n although it is exponential in m. For m = 2, it is shown that the heuristic has a (best possible) worst-case performance ratio of 1 +5)2 and requires linear time. A modified version of the heuristic is presented for m = 2 which is shown to have a (best possible) worst-case performance ratio of 32 while still requiring linear time.