Single Machine Scheduling With A Maintenance Interval And Job Delivery Coordination

This paper investigates a single machine scheduling problem with a main-tenance interval and job delivery coordination,our problem can also be viewed as an integrated production and outbound distribution scheduling model.Each job needs to be processed without preemption on the single machine with a maintenance,which demands different amount of storage space during transporta-tion.After processing in the manufacturing center,they need to be delivered by vehicles with a limited load capacity in batches in the distribution center.When the vehicle deliveries a shipment to a customer it has to return back to manufac-turing center to delivery the next shipment,and it takes different constant time for the round trips between the machine and the different customers.The goal is min-imize the makespan.We present a 5/2-approximation algorithm for the case which jobs are processed and delivered to multiple customers by a single vehicle;for a particular case of a customer,the bound of the algorithm is 2 and the perfor-mance ratio is tight.We also present a2-approximation algorithm for the case which jobs are processed and delivered to single customer by two homogeneous vehicles,also,we show that the performance ratio is tight.