Algorithms for the On-Line Quota Traveling Salesman Problem

The Quota Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem. The goal of the traveling salesman is, in this case, to reach a given quota of sales, minimizing the amount of time. In this paper we address the on-line version of the problem, where requests are given over time. We present algorithms for various metric spaces, and analyze their performance in the usual framework of competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the halfline metric space, we show that it is helpful not to move at full speed, and this approach is also used to derive the best on-line polynomial time algorithm known so far for the On-Line TSP (in the homing version).     

Are Stacker Crane Problems easy? A statistical study

Many full truckload pick-up and delivery problems in the intermodal freight container transport industry can be modeled as Asymmetric Traveling Salesman Problems (ATSPs). Several authors have noted that while ATSPs are NP-hard, some instances are readily solved to optimality in only a short amount of time. Furthermore, the literature contains several references to the Stacker Crane Problem (SCP) as an “easy” problem amidst the ATSPs. We put this hypothesis to test by using statistical methods to build a model relating measurable distance matrix structures to the amount of time required by two existing exact solvers in finding solutions to over 500 ATSP instances. From this analysis we conclude that SCPs are not necessarily easier than other ATSPs, but a special subset of SCPs, termed drayage problems, are more readily solved. We speculate that drayage problems are “easy” because of a comparatively high number of zeros in symmetric locations within the distance matrix. In real-world drayage problems (i.e. the movement of containers a short distance to/from a port or rail terminal), these zeros correspond to the prevalence of jobs originating at or destined to a fixed number of freight terminals.     

多媒体服务器混合磁盘调度策略

基于多媒体服务器的性能要求，提出了一种自适应的混合磁盘调度策略DRT-window．它既能满足实时请求对实时性的要求，根据实时请求的截止期动态选择窗口大小；又能在其松弛度内尽努力(best-effort)地服务非实时请求，从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案：第一层为不同类型的请求采用各自适合的调度策略；第二层为混合请求调度嚣，混合调度第一层中的不同类型的请求。通过性能比较和理论证明，表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时，尽量地减少非实时请求的响应时间。     

Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem

Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V ₁ , . . ., V _k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them. Received February 13, 1998; revised July 8, 1998.     

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of and a randomized approximation algorithm that achieves a ratio of . In particular, we obtain a 2+ε approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio ), asymmetric TSP (ATSP) with γ-triangle inequality (ratio ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2). A preliminary version of this work has been presented at the 4th Workshop on Approximation and Online Algorithms (WAOA 2006) (Lecture Notes in Computer Science, vol. 4368, pp. 302–315, 2007). B. Manthey is supported by the Postdoc-Program of the German Academic Exchange Service (DAAD). He is on leave from Saarland University and has done part of the work at the Institute for Theoretical Computer Science of the University of Lübeck supported by DFG research grant RE 672/3 and at the Department of Computer Science at Saarland University.     

General Perfectly Periodic Scheduling

In a perfectly periodic schedule, each job must be scheduled precisely every some fixed number of time units after its previous occurrence. Traditionally, motivated by centralized systems, the perfect periodicity requirement is relaxed, the main goal being to attain the requested average rate. Recently, motivated by mobile clients with limited power supply, perfect periodicity seems to be an attractive alternative that allows clients to save energy by reducing their "busy waiting" time. In this case, clients may be willing to compromise their requested service rate in order to get perfect periodicity. In this paper we study a general model of perfectly periodic schedules, where each job has a requested period and a length; we assume that m jobs can be served in parallel for some given m. Job lengths may not be truncated, but granted periods may be different than the requested periods. We present an algorithm which computes schedules such that the worst-case proportion between the requested period and the granted period is guaranteed to be close to the lower bound. This algorithm improves on previous algorithms for perfect schedules in providing a worst-case guarantee rather than an average-case guarantee, in generalizing unit length jobs to arbitrary length jobs, and in generalizing the single-server model to multiple servers.     

Algorithms for Minimizing Response Time in Broadcast Scheduling

In this paper we study the following problem. There are n pages which clients can request at any time. The arrival times of requests for pages are known in advance. Several requests for the same page may arrive at different times. There is a server that needs to compute a good broadcast schedule. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. This problem has recently been shown to be NP-hard. For any fixed , 0 < \le &frac;, we give a 1/-speed, polynomial time algorithm with an approximation ratio of 1/(1 – ). For example, setting = &frac; gives a 2-speed, 2-approximation algorithm. In addition, we give a 4-speed, 1-approximation algorithm improving the previous bound of 6-speed, 1-approximation algorithm.     

New Algorithms for Disk Scheduling

Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function that determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2 -approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the Asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-Δ ) in which all distances are either 0 or some constant α . We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly distributed requests arrive over time. We present an algorithm related to the above ATSP-Δ .     

基于磁盘性能模型的优化调度算法

总结分析了现阶段流行的一般磁盘调度算法和实时磁盘调度算法，并针对存储的实业业务的特性，提出了改进的调度算法，建立相对应的数学模型，最后通过模拟实验，验证了算法的有效性。     

Efficient algorithms for the double traveling salesman problem with multiple stacks

In this paper we investigate theoretical properties of the Double Traveling Salesman Problem with Multiple Stacks. In particular, we provide polynomial time algorithms for different subproblems when the stack size limit is relaxed. Since these algorithms can represent building blocks for more complex methods, we also include them in a simple heuristic which we test experimentally. We finally analyze the impact of handling the stack size limit, and we propose repair procedures. The theoretical investigation highlights interesting structural properties of the problem, and our computational results show that the single components of the heuristic can be successfully incorporated in more complex algorithms or bounding techniques.     

一种新颖的带模糊截止时限的磁盘调度算法

设计了一种新的基于截止时限的磁盘调度算法,该算法支持带多优先级的请求。对于某些实时要求,其截止时限是不确定的或者不精确的,该算法采用模糊集来描述这类不确定性,模糊截止时限的隶属度函数表示对请求完成时间的满意程度。调度的目的是最优的指定优先级,使得截止时限的满意程度最大化。根据请求截止时限的不同,把满意程度划分为若干连续的区间。在每个不同的区间内,每个请求都对应有修正的截止时限,把请求按照其修正的截止时限非减的顺序分配优先级,才能实现请求优先级的最优配置。仿真结果表明该算法能有效的分配请求的优先级,降低请求的丢失率,保证了更多的请求得到满足。     

Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and edges represent data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has a processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (J. Algorithms 55, 42–57, 2005) gave an LP-rounding 3-approximation algorithm when edges have unit processing times. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee. When edges have arbitrary processing times we give a primal-dual 5.83-approximation algorithm. We also study a variant of the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the sum of completion times of edges. We present a simple algorithm that achieves an approximation ratio of , thus improving the 1.796-approximation given by Gandhi et al. (ACM Trans. Algorithms 2(1), 116–129, 2006). We show that the analysis of our algorithm is almost tight. A preliminary version of the paper appeared in the Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006. Research of R. Gandhi partially supported by Rutgers University Research Council Grant. Research of J. Mestre done at the University of Maryland; supported by NSF Awards CCR-0113192 and CCF-0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

一种新的求解TSP问题智能蚁群优化算法

提出了一种新的用于求解TSP问题的智能蚁群优化算法。新算法从TSP问题本身出发,提取出了该问题的一种本质特征,并赋予蚁群算法中的精英蚂蚁以识别该固有特征的能力,以提高精英蚂蚁的搜索质量,进而使得新算法整体的求解能力得以提高。文章中不仅阐述了新算法的原理,而且进行了仿真实验,实验结果表明新算法在求解时间和求解质量上都取得了很好的效果。     

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑ _j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C _max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.     

双头镜像磁盘的SSTF调度算法

首先简要介绍了双头镜像磁盘系统的研究现状,然后针对双头镜像磁盘系统中传统的先来先服务（ＦＣＦＳ）调度算法提出一种新的调度算法：短寻道时间优先算法（Ｓｈｏｒｔ Ｓｕｅｅｋ－Ｔｉｍｅ Ｆｉｒｓｔ－ＳＳＴＦ）。根据蒙特卡罗模拟实验方法,对双头镜像磁盘系统下的这两种调度算法进行模拟,从模拟实验的结果中定量分析出ＳＳＴＦ调 度算法大大提高了系统的性能。本文还讨论了在该调度算法下,系统的平均寻道时间与Ｉ／Ｏ请     

Approximation Algorithms for Minimum K -Cut

Let G=(V,E) be a complete undirected graph, with node set V={v ₁ , . . ., v _n } and edge set E . The edges (v _i ,v _j ) ∈ E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = { k _i } _i=1 ^p , the minimum K-cut problem is to compute disjoint subsets with sizes { k _i } _i=1 ^p , minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds on the ratio between the weights of maximum and minimum cuts. Received September 4, 1997; revised July 15, 1998.     

一种新的求解TSP的混合量子进化算法

在分析量子进化基本概念的基础上,提出了一种新的求解TSP的混合量子进化算法（MQEA）。该算法将三段优化局部搜索算法融入量子进化机制,采用一种基于边的编码方法,应用最近邻规则设置初始参数,并设计了排序交叉算子以扩展种群的搜索范围。通过选取国际通用旅行商问题（TSP）实例库(TSPLIB)中的多个实例进行测试,表明新算法具有高的精确度和鲁棒性,即使对于中大规模问题（城市数大于500）,也能以很小的种群和微小的相对误差求得满意解。     

基于QoS的磁盘调度策略

随着视频点播、视频会议、视频监控、数字图书馆等流媒体应用的普及，流媒体服务器存储资源管理成为制约服务质量的瓶颈之一。根据多媒体服务器的性能要求，提出了一种支持QoS的磁盘调度策略。它由三个主要部分组成：探测模块、负载监测模块和自适应管理模块。探测模块，负责判断当前的资源情况能否满足服务请求；自适应模块，根据负载监删模块检测到的负载变化情况，动态调整服务周期在实时请求和尽力服务请求之间的分配。实验表明此磁盘调度策略能在保证实时请求无抖动执行的同时，明显减少了非实时请求的响应时间。     

实时系统中的调度算法分类研究

本文叙述了实时系统中调度算法的分类、各类算法的研究成果和近期研究状况。     

网格任务调度算法研究

网格任务调度算法是影响网格成功与否的关键技术之一。本文总结了网格计算系统的体系结构和特征,分析了网格任务调度算法的基本原理和性能指标,并对各种调度策略和算法进行了分类和比较。本文为网格任务调度的研究提供了很好的参考。