Analysis of a linear programming heuristic for scheduling unrelated parallel machines (Q1061599)

Each of n jobs is to be processed without interruption on one of m unrelated parallel machines. The objective 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\geq 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+\sqrt{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 3/2 while still requiring linear time.