Some Research On Single Machine Scheduling With Job Delivery Coordination

In this thesis we investigate a single m achine scheduling problem with job delivery coordination,in this problem,each job needs to be processed on a single machine without preemption,and then delivered by vehicles to one customer,where the job has different amount of storage space during delivery.The goal is to minimize the total time required in this process.Two scenarios of this problem are discussed.One is jobs are processed on a single machine and delivered by three homogeneous vehicles to one customer,we present a approximation algorithm with a worst-case ratio of 2,and the bound is tight,and the time complexity of the approximation algorithm is O(n log n).In the other case,we expand the number of transport vehicles into m vehicles,we also present a approximation algorithm with a worst-case perfor-mance ratio of 2,and the time complexity of the approximation algorithm is O(n log n).