Heuristics for parallel machine scheduling with delivery times (Q1338896)

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 \geq 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.