On the machine scheduling problem with job delivery coordination

This paper examines two scheduling problems with job delivery coordination, in which each job demands different amount of storage space during transportation. For the first problem, in which jobs are processed on a single machine and delivered by one vehicle to a customer, we present a best possible approximation algorithm with a worst-case ratio arbitrarily close to 3/2. For the second problem, which differs from the first problem in that jobs are processed by two parallel machines, we give an improved algorithm with a worst-case ratio 5/3.