The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

In the prize-collecting travelling salesman problem, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow \mathbb {R}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow \mathbb {R}_+\) and the goal is to find a closed tour \(T\) such that \(r\in V(T)\) and such that the cost \(\ell (T)+\pi (V\setminus V(T))\), which is the sum of the edges in the tour and the cost of the vertices not spanned by \(T\), is minimized. We consider an online variant of the prize-collecting travelling salesman problem related to graph exploration. In the Canadian Tour Operator Problem the task is to find a closed route for a tourist bus in a given network \(G=(V,E)\) in which some edges are blocked by avalanches. An online algorithm learns from a blocked edge only when reaching one of its endpoints. The bus operator has the option to avoid visiting each node \(v\in V\) by paying a refund of \(\pi (v)\) to the tourists. The goal consists of minimizing the sum of the travel costs and the refunds. We study the problem on a simple (weighted) path and prove tight bounds on the competitiveness of deterministic algorithms. Specifically, we give an algorithm with competitive ratio equal to the golden ratio \(\phi =(1+\sqrt{5})/2\). We also study the effect of resource augmentation, where the online algorithm either pays a discounted cost for traversing edges or for the penalties.     

基于随机运输路径选择的物流中心选址模型

旨在以物流系统总费用最小化为目标进行物流中心选址规划.政府做出物流中心选址规划后,客户会选择合适的供应商进行交易,并根据已有物流中心与交通流分布进行货物运输路线决策,使其总费用最少.论文提出了物流中心选址双层规划模型,考虑投资费用的约束,保证用户平衡的同时使整个物流系统总费用最低.其中上层规划目标是使物流系统总费用最小化,下层规划建立了一个Logit随机用户均衡模型,并构造了一个等价的凸规划问题.最后针对模型提出了一个算法,并通过算例说明其可行性.     

Randomized Online Scheduling with Delivery Times

We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.     

Commercial territory design planning with realignment and disjoint assignment requirements

A territory design problem motivated by a bottled beverage distribution company is addressed. The problem consists of finding a partition of the entire set of city blocks into a given number of territories subject to several planning criteria. Each unit has three measurable activities associated to it, namely, number of customers, product demand, and workload. The plan must satisfy planning criteria such as territory compactness, territory balancing with respect to each of the block activity measures, and territory connectivity, meaning that there must exist a path between any pair of units in a territory totally contained in it. In addition, there are some disjoint assignment requirements establishing that some specified units must be assigned to different territories, and a similarity with existing plan requirement. An optimal design is one that minimizes a measure of territory dispersion and similarity with existing design. A mixed-integer linear programming model is presented. This model is unique in the commercial territory design literature as it incorporates the disjoint assignment requirements and similarity with existing plan. Previous methods developed for related commercial districting problems are not applicable. A solution procedure based on an iterative cut generation strategy within a branch-and-bound framework is proposed. The procedure aims at solving large-scale instances by incorporating several algorithmic strategies that helped reduce the problem size. These strategies are evaluated and tested on some real-world instances of 5000 and 10,000 basic units. The empirical results show the effectiveness of the proposed method and strategies in finding near optimal solutions to these very large instances at a reasonably small computational effort.     

On single machine scheduling with resource constraint

The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case.     

Minimum power assignment in wireless ad hoc networks with spanner property

Power assignment for wireless ad hoc networks is to assign a power for each wireless node such that the induced communication graph has some required properties. Recently research efforts have focused on finding the minimum power assignment to guarantee the connectivity or fault-tolerance of the network. In this paper, we study a new problem of finding the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Here, a spanner means that the length of the shortest path in the induced communication graph is at most a constant times of the length of the shortest path in the original communication graph. Polynomial time algorithm is given to minimize the maximum assigned power with spanner property. The algorithm also works for any other property that can be tested in polynomial time and is monotone. We then give a polynomial time approximation method to minimize the total transmission radius of all nodes. Finally, we propose two heuristics and conduct extensive simulations to study their performance when we aim to minimize the total assigned power of all nodes. The author is partially supported by NSF CCR-0311174.     

价格下界随时间递增的占线采购问题

本文研究的是价格不确定且其下界随时间递增的原材料采购问题。在实际的原材料采购问题中,原材料的价格随时间的变动往往是不可预测的。之前的学者在研究价格不确定的占线采购问题时,假设价格在一个统一的常数上下界内,这没有考虑到经过时间的变化,价格的上下界可能也是变化的。本文提出并研究价格下界随时间递增的原材料占线采购问题。构建了相应数学模型,给出了相应的竞争采购策略并证明了竞争比,同时通过证明问题的匹配竞争比下界,说明给出的竞争采购策略是最优的,最后利用数值分析进一步说明竞争策略具有较好的竞争性能。     

Online lazy bureaucrat scheduling with a machine deadline

The lazy bureaucrat scheduling problem was first introduced by Arkin et al. (Inf Comput 184:129–146, 2003). Since then, a number of variants have been addressed. However, very little is known on the online version. In this note we focus on the scenario of online scheduling, in which the jobs arrive over time. The bureaucrat (machine) has a working time interval. Namely, he has a deadline by which all scheduled jobs must be completed. A decision is only based on released jobs without any information on the future. We consider two objective functions of [min-makespan] and [min-time-spent]. Both admit best possible online algorithms with competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\).     

Online scheduling on uniform machines with two hierarchies

In this paper we study online scheduling problem on m parallel uniform machines with two hierarchies. The objective is to minimize the maximum completion time (makespan). Machines are provided with different capability. The machines with speed s can schedule all jobs, while the other machines with speed 1 can only process partial jobs. Online algorithms for any 0<s<∞ are provided in the paper. For the case of k=1 and m=2, and the case of some values of s, k=1 and m=3, the algorithms are the best possible, where k is the number of machines with hierarchy 1, and m is the number of machines. Lower bounds for some special cases are also presented.     

Online scheduling with a buffer on related machines

Online scheduling with a buffer is a semi-online problem which is strongly related to the basic online scheduling problem. Jobs arrive one by one and are to be assigned to parallel machines. A buffer of a fixed capacity K is available for storing at most K input jobs. An arriving job must be either assigned to a machine immediately upon arrival, or it can be stored in the buffer for unlimited time. A stored job which is removed from the buffer (possibly, in order to allocate a space in the buffer for a new job) must be assigned immediately as well. We study the case of two uniformly related machines of speed ratio s≥1, with the goal of makespan minimization.     

Optimal tree structure with loyal users and batch updates

We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(n⋅K+K ⁴) time where K=min {4(log (1−p)⁻¹)⁻¹,n} and n is the number of normal users.     

考虑资源分配的 HTN 规划方法及其应用

针对应急决策中方案制定过程和资源分配过程紧密耦合的特点,设计了一种满足 HTN( Hierarchy Task Net) 规划动作推理机制的方法来求解带资源分配的规划问题．本方法在 HTN规划中扩展了资源时间轴来描述资源函数; 对于各类资源,在规划推理过程中通过不同的处理流程,将资源分配信息转化为 HTN 规划的当前全局资源状态; 并在 HTN 规划搜索行动序列的同时,采用资源约束规则和资源约束层次传播规则控制每一步行动所对应的系统状态满足资源约束和时间约束． 最后以某区域应急资源筹集为例,将本方法应用于 HTN 规划模型 SHOP2( Simple Hierarchical Ordered Planner 2) 证实了其有效性和实用性．     

活动重叠模式与资源约束下的项目调度优化

采取活动重叠模式通常是加速研发的有效手段,带有活动重叠的资源受限项目调度问题是经典资源受限项目调度问题的扩展.首先,深入分析了活动重叠对于项目调度的影响,对活动重叠及其不确定进行详细描述与建模,提出了活动重叠导致下游活动返工时间的二项分布概率模型;其次,构建了以最小化研发项目期望工期为目标的优化调度模型,设计了基于串行进度生成机制的遗传算法对大规模问题进行优化求解;最后,基于PSPLIB J60问题库中480个算例分析了该算法的计算结果,并考察了网络参数、资源参数和重叠参数变化时,采用活动重叠模式对缩短项目工期的影响.研究结果表明:活动对资源的需求强度越小或资源稀缺程度越低,可重叠活动对数量就会增加,项目工期缩短得越明显;网络复杂度的变化对缩短项目工期的影响不大;项目中重叠活动对越多,重叠导致的下游活动返工的概率越小,项目工期缩短的越明显.     

具有概率分布在线租赁问题策略研究

在经济系统中,决策越来越呈现出在线性特征,传统优化方法在解决这类在线问题时,通常假设未来输入是一随机变量从而寻求概率意义上的最优决策。近年来,在优化领域兴起了一种新的研究方法——在线算法与竞争分析,为解决这类在线问题提供了新的视角,但传统的竞争分析方法有意规避概率分布假设。对于在线租赁决策问题,由于其输入结构简单且具有良好的统计性质,似乎忽略这些有用的信息而只运用标准的竞争比方法分析显然具有不足之处。在本文中,我们将其输入结构的概率分布引入纯竞争分析方法中,从而建立了具有概率情形的最优在线租赁模型,并得到了最优竞争策略及其竞争比。     

Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.     

Online routing and searching on graphs with blocked edges

Journal of Combinatorial Optimization - We study routing and searching decisions of a search-and-detection (SDT) team on a road network under online uncertainty setting. Given an undirected...