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

项目名称： 网络上的排序问题的近似算法研究

项目编号： No.11301184

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 余炜

作者单位： 华东理工大学

项目金额： 23万元

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

中文关键词： 网络上的排序问题；旅行商问题；近似算法；NP 困难性；不可近似性

英文摘要： 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 N

英文关键词： Routing Scheduling Problems；Traveling Salesman Problem；Approximation Algorithms；NP-hardness；Inapproximability