【作者】 余炜；

【导师】 刘朝晖；

【作者基本信息】 华东理工大学 ， 应用数学， 2010， 博士

【摘要】 本文从算法和复杂性的角度对一些网络排序问题进行了研究。经典的排序模型假设所有任务和资源(通常称为工件和机器)位于同一场所,从而不需要考虑工件的运输时间或机器的旅行时间。然而,在实际的应用中经常需要考虑如何对分散的任务合理地分配资源以实现资源的最优配置。在网络排序问题(Routing Scheduling Problem)中,工件分散在网络中且位置固定,机器移动或旅行到工件所在的位置进行加工。网络排序问题可分为单机VSP (Vehicle Scheduling Problem)问题、平行机VSP问题和网络作业排序问题。在VSP问题中,若所有工件的加工时间都等于零时,就得到了VRP问题(Vehicle Routing Problem)。第二章讨论线形网络上的VRP问题。对于无准备时间约束的情形,分别给出了极小化一般正则求和目标函数和一般正则瓶颈目标函数的单机问题的拟多项式和多项式算法,并将其推广到平行机问题。特别地,给出了极小化延误工件数的单机问题的多项式算法,并证明了极小化加权延误工件数和加权总延误的单机问题都是NP困难的,但是当所有工件的工期相同时这两个问题都是多项式可解的。对于有准备时间约束的情形,给出了极小化时间表长的返回型和不返回型平行机问题的多项式算法。第三章讨论线形网络上有准备时间约束的极小化时间表长的单机VSP问题。对于返回型问题给出了3／2-近似算法并证明了其紧性；对于不返回型问题给出了5／3-近似算法并证明了其紧性。第四章讨论一般网络上的两个VRP问题,即在线不返回型TSP和QTSP。对于在线不返回型TSP,给出了竞争比为2~1/2+ρ的多项式算法,对于在线QTSP和在线不返回型QTSP,都给出了竞争比为1+ρ的多项式算法,其中ρ分别为求解最短Hamilton路问题、QTSP和不返回型QTSP的近似算法的性能比。此外,还给出了QTSP和不返回型QTSP的近似算法。第五章讨论机器起点相同的极小化时间表长的网络作业排序问题。对于一般网络上的自由作业排序问题,分别对两台机器的返回型和不返回型问题给出了5／3-近似算法和7／4-近似算法,其中前一个算法是紧的；对m-台机器的问题也给出了近似算法。对于树形网络上的两台机器流水作业排序问题,证明了返回型和不返回型问题都是NP困难的,并且对返回型问题设计了10／7-近似算法。更多还原

【Abstract】 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.更多还原