HEURISTICS FOR PARALLEL MACHINE SCHEDULING WITH DELIVERY TIMES

A parallel machine scheduling problem is considered in which each job has a processing time and a delivery time. The objective is to find a schedule which minimizes the time by which all jobs are delivered. For a single machine this problem is easily solved in polynomial time, for m greater than or equal to 2 machines it becomes NP-hard. Several heuristics using list scheduling as a subroutine are proposed and a tight worst-case analysis is given. The best one of our heuristics has a worst-case performance guarantee of 2 - 2/(m + 1). For the on-line case we give a heuristic with the (best possible) worst-case performance of two.