Algorithms And Complexity Of Some Routing Scheduling Problems

In this thesis we study the algorithms and complexity of some routing scheduling problems. In classical scheduling problems, it is assumed that all the tasks and re-sources(also called jobs and machines) are located at the same site and hence neither transportation time for jobs nor travel time for machines is considered. However, in many practical applications we are required to optimize the allocation of resources to tasks distributed at different sites of a real or virtual network. In routing scheduling problems, the locations of the jobs are fixed and the machines travel along the network to process the jobs. Routing scheduling problems consist of single-vehicle scheduling problems, parallel-vehicle scheduling problems and routing shop scheduling problems. In vehicle scheduling problems, if each job has zero processing time we have vehicle routing problems.In Chapter 2 we consider vehicle routing problems on a line. When no release time constraint is imposed, we give pseudo-polynomial and polynomial algorithms for single-vehicle problems with general minsum objective and general minmax objective respectively, and generalized them to parallel-vehicle problems. Particularly, we give a polynomial algorithm for the problem of minimizing number of late jobs. For the single-vehicle problems of minimizing weighted number of late jobs and total weighted tardiness, we prove that they are both NP-hard, but when all the jobs have a common due date these two problems are both polynomially solvable. When release time constraints are imposed, we give polynomial algorithms for two versions of the parallel-vehicle problem of minimizing makespan.In Chapter 3 we discuss the single-vehicle scheduling problem of minimizing makespan with release time constraints on a line. For the tour-version problem we propose 3/2-approximation algorithm and give tight examples. For the path-version problem, we present 5/3-approximation and also show tight examples.In Chapter 4 we deal with two vehicle routing problems on a graph, i.e., the path-version of TSP and Quota Traveling Salesman Problem(QTSP). We give a ((?)+ρ)- competitive polynomial algorithm for the path-version of online TSP and (1+ρ)-competitive polynomial algorithms for both online QTSP and its path-version counterpart, whereρdenotes the approximation ratio for the Shortest Hamiltonian Path Problem, QTSP and the path-version of QTSP respectively. Moreover, we also develop approximation algo-rithms for QTSP and its path version counterpart.In Chapter 5, we treat the routing shop scheduling problems of minimizing makespan in which all the machines have the same initial location. For open shop problems on a graph, we obtain a 5/3-approximation algorithm and a 7/4-approximation algorithm for the tour-version and path-version of two machine problem respectively, and the former is tight. These algorithms are generalized to m-machine problem. For two-machine flow shop problem on a tree, we prove both tour-version and path-version are NP-hard and give a 10/7-approximation algorithm for the tour-version.