The Algorithms And Conplexity Of Vehicle Scheduling Probkems

It has been over fifty years since Dantzig and Ramser firstly introduced the Vehicle scheduling problem (VSP, for short). Now VSP is one of the most important scheduling problems, and its applications involve transportation management, intelligent disaster management system, network job scheduling system, modern logistics system, etc.Given a graph G=(V,E), for each (i, j)∈E, there is a weight wi,j, indicating the time needed for the vehicle to travel from vertex i to j. At each vertex i, there is a task, also written as i, which has for parameters:the release time ri, the deadline di, the handling time hi, and the value vi. Now we have a vehicle to deal with the tasks. All the tasks are nonpreemptable. We want to work out a scheduling of the tasks and a routing for the vehicle to maximize the total value of the completed tasks. We denote this problem as VSP(Val), and get the following results:For VSP(Val) on a line, when the handling time is nonzero, we prove that the prob-lem is NP-hard, and when the release times are not the same, the problem is strongly NP-hard. We design a pseudo polynomial time algorithm and an FPTAs for the instances which all the tasks share a same deadline. When the number of the deadlines is2, we also give a pseudo polynomial time algorithm.For VSP(Val) on a tree, when the release times and the handling times of all the tasks are zero, the deadlines of all the tasks are all the same, and the vehicle has to return to the root after completing the tasks, we show that this problem is NP-hard, and give a pseudo polynomial time algorithm for this problem. We investigate VSP(Val) on Stars under deferent conditions with deferent complexity.For VSP(Val) on a general graph, it is strongly NP-hard, even if w(e)=1, d(i)=D, v(i)=1, where D is a given constant. When choosing the number of the completed tasks as the parameter, we give the corresponding parameterized problem an fpt-algorithm based on the technique of color coding, which was proposed in1994by Noga Alon, et al., with the running time O((4e)2kn3) where k is the parameter.We study a variate of VSP(Val)-program download problem(PDP, for short), and show that it is NP-complete even if there are two channels, each program being broad-casted at most twice on each channel, and having unit length. We also show that when each program is broadcasted at most once on each channel, and has unit length, PDP is NP-complete. If programs on every channel has the same beginning and ending, we device a polynomial algorithm. We prove that unless P=NP, there is no1+x/(2n+1)-approximation for an optimization version of PDP-MinPDP, where X is an arbitrary integer, and2n is the number of the channels. For parameterized problem p-MaxPDP, we give an fpt-algorithm with expected time O(2°(l)(nm)3).