网络上的排序问题的近似算法研究

Both Traveling Salesman Problem(TSP) and Scheduling Problem are classical combinatorial optimization problems, which have a wide range of applications. However, the fundamental models are simplified, more or less. In TSP, it is assumed that the visiting times of all the cities are zero and each city can be visited at any time. Actually, it is more reasonable to suppose that the visit of each city takes a time duration and can only be conducted within a particular time period. In classical scheduling problems, all the resources and tasks(also known as machines and jobs) are assumed to be situated at the same location and therefore neither travel time for machines nor transportation time for jobs is taken into account. But in a lot of practical applications we need to efficiently allocate resources to tasks distributed at different sites of a real or virtual network. As an organic combination of TSP and Scheduling Problem, Routing Scheduling Problem models such applications perfectly, in which the jobs are located at vertices of some network and the machines travel along the network to process the jobs. Clearly, Routing Scheduling Problem tremendously extends the applications of TSP and Scheduling Problem. Meanwhile, the difficulty of Routing Scheduling Problem is enhanced enormously, because TSP in itself is an NP-hard problem and the scheduling of job processing makes the problem more complicated. This project devotes to the design of approximation algorithms for some fundamental routing scheduling problems as well as their inapproximability.

TSP和排序问题都是经典的组合优化问题，应用领域极其广泛。然而，TSP和排序问题的基本模型都有些简化。TSP假设旅行商访问城市所用的时间为零，而且可以在任何时间访问。事实上，假定城市的访问需要一定的时间，而且访问时间有一定限制更为合理。在经典的排序模型中，假定所有的任务和资源（称为工件和机器）都位于同一地点，所以无需考虑工件运输或机器移动。而在很多实际应用中，需要对分散在网络中的任务或资源进行有效、合理的调度。网络上的排序问题为这些应用提供了合理的模型，它是TSP和排序问题的有机结合，其中工件分散在网络中且位置固定，机器需要在工件之间移动或旅行来进行加工。网络上的排序问题极大地扩展了TSP和排序问题的应用范围，研究难度也相应提高，因为TSP本身已经是NP困难问题，工件加工的安排又使得问题更加复杂化。本课题主要研究若干基本的网络上的排序问题的近似算法，同时也对部分问题的不可近似性进行探讨。

在本课题中，我研究了网络上的排序问题及其相关问题。这些问题有机地结合了两个经典的组合优化问题，即旅行商问题和排序问题，应用领域极其广泛。.我们研究的第一个问题是在线配额旅行商问题。对于返回型和不返回型的在线配额旅行商问题，我们都给出了最优在线算法。我们还将上述结果推广到一般的准度量空间，并对一般空间、直线以及半直线的情形均给出了最优在线算法。.第二个问题是线形网络上的分群VSP问题。当每个工件加工时间为零时，证明了返回型和不返回型的问题均可在O(n^2)的时间内解决。如果每个工件加工时间任意，就返回型和不返回型的问题分别给出了16/9-和13/7-近似算法。.第三个问题是分群旅行商问题。对于旅行商进入每个群的顶点给定而离开每个群的顶点可以在其内剩余顶点中任意选择的情形，给出一个5/2-近似算法；就旅行商进入和离开每个群的顶点均可以在其内顶点中任意选择的情形，给出一个19/10-近似算法。.第四个问题是圈覆盖问题。对于无根和带根的最小-最大圈问题，分别给出了5-和6-近似算法。对于最小圈覆盖问题，得到了复杂性为O(n^2)的24/5-近似算法和复杂性为O(n^5)的14/3-近似算法。.第五个问题是有容量约束的带根最小-最大树（圈、路）覆盖问题。我们分别给出了相应的树、圈和路覆盖问题的7-，6-和7-近似算法。我们还将圈（路、树）覆盖问题的不可近似性下界推广到平面图的情形。.第六个问题是网络上的自由（流水）作业问题。对于一般网络上的自由（流水）作业问题，目前还没有常数界性能比的近似算法。我们对以下三种重要的情形给出了常数界近似比的算法：(i)工序的加工时间与工件无关；(ii)工序的加工时间与机器无关；(iii)所有工序的加工时间相等。.第七个问题是旅行商选址问题。对于线形网络上的多旅行商选址问题和树形网络上的2-旅行商选址问题，我们都首先给出了多项式时间算法。对于不返回型旅行商选址问题，我们首先给出了旅行商个数m≤3时树形网络上该问题的多项式时间算法。对于一般网络上的问题，我们给出了几个简单的近似算法，并分析了它们的性能比。.综合以上研究结果, 本项目已经完成了7篇论文,其中3篇已经正式发表（2篇为SCI期刊），1篇已经被接收，2篇已经投稿，2篇即将投稿。此外,项目负责人参加了两次国际会议并作了口头报告。项目负责人及其他成员参加了多次全国学术会议。