Optimal online algorithms for scheduling on two identical machines under a grade of service

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

An efficient and impartial online algorithm for kidney assignment network

An online algorithm balancing the efficiency and equity principles is proposed for the kidney resource assignment when only the current patient and resource information is known to the assignment network. In the algorithm, the assignment is made according to the priority, which is calculated according to the efficiency principle and the equity principle. The efficiency principle is concerned with the post-transplantation immunity spending caused by the possible post-operation immunity rejection and patient’s mental depression due to the HLA mismatch. The equity principle is concerned with three other factors, namely the treatment spending incurred starting from the day of registering with the kidney assignment network, the post-operation immunity spending and the negative effects of waiting for kidney resources on the clinical efficiency. The competitive analysis conducted through computer simulation indicates that the efficiency competitive ratio is between 6.29 and 10.43 and the equity competitive ratio is between 1.31 and 5.21, demonstrating that the online algorithm is of great significance in application.

Online algorithms for scheduling with machine activation cost on two uniform machines

In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.

Competitive analysis of price online inventory problem with cost function

In this paper,a new price is given to the online decision maker at the beginning of each day.The trader must decide how many items to purchase according to the current price.We present three variants and an online algorithm based on cost function.The competitive ratio of the online algorithm is given for each variant,which is a performance measure of an online algorithm.More importantly,we show that the online algorithm is optimal.

An Online Algorithm Based on Replication for Using Spot Instances in IaaS Clouds

Infrastructure-as-a-Service(IaaS)cloud platforms offer resources with diverse buying options.Users can run an instance on the on-demand market which is stable but expensive or on the spot market with a significant discount.However,users have to carefully weigh the low cost of spot instances against their poor availability.Spot instances will be revoked when the revocation event occurs.Thus,an important problem that an IaaS user faces now is how to use spot in-stances in a cost-effective and low-risk way.Based on the replication-based fault tolerance mechanism,we propose an on-line termination algorithm that optimizes the cost of using spot instances while ensuring operational stability.We prove that in most cases,the cost of our proposed online algorithm will not exceed twice the minimum cost of the optimal of-fline algorithm that knows the exact future a priori.Through a large number of experiments,we verify that our algorithm in most cases has a competitive ratio of no more than 2,and in other cases it can also reach the guaranteed competitive ratio.

Competitive analysis of online inventory problem with interrelated prices

This paper investigates the online inventory problem with interrelated prices in which a decision of when and how much to replenish must be made in an online fashion even without concrete knowledge of future prices. Four new online models with different price corre- lations are proposed in this paper, which are the linear-decrease model, the log-decrease model, the logarithmic model and the exponential model. For the first two models, the online algo- rithms are developed, and as the performance measure of online algorithm, the upper and lower bounds of competitive ratios of the algorithms are derived respectively. For the exponential and logarithmic models, the online algorithms are proposed by the solution of linear programming and the corresponding competitive ratios are analyzed, respectively. Additionally, the algorithm designed for the exponential model is optimal, and the algorithm for the logarithmic model is optimal only under some certain conditions. Moreover, some numerical examples illustrate that the algorithms based on the dprice-conservative strategy are more suitable when the purchase price fluctuates relatively flat.

Two Online Algorithms for the Ambulance Systems

An ambulance system consists of a collection S = {s1,...,sm ) sm} of emergency centers in a metric space M. Each emergency center si has a positive integral capacity ci to denote, for example, the number of ambulances at the center. There are n = =1, ci patients requiring ambulances at different times tj and every patient is associated with a number bj, the longest time during which the patient can wait for ambulance. An online algorithm A will decide which emergency center sends an ambulance to serve a request for ambulance from a patient at some time. If algorithm A sends an ambulance in si to serve a patient rj, then it must be observed that di,j/v < bj, where di,j is the distance between emergency center si and patient rj, and v is the velocity of ambulance. A fault of algorithm A is such that to a request for ambulance at some time tj with j ≤n, for every i with di,j/v < bj, there is no ambulance available in si. The cost of an algorithm A is the number of faults A makes. This paper gives two algorithms B and C, where B is the local greedy algorithm and C is a variant of balancing costs, and proves that both B and C have no bounded competitive ratios. Moreover, given any sequence a of requests for ambulances without optimal faults, the cost of C on σis less than or equal to [n/3] and that of B is less than or equal to [n/2].

Competitive Analysis of Two Special Online Device Replacement Problems

When a new investment opportunity of purchasing a new device occurs, the investors must decide whether or not and when to buy this device in an online fashion. That is, the online player must make an investment decision while neither future demand for orders nor future investment opportunities are known. This problem which generalizes the basic leasing problem has been introduced by Azar et al., and then two special cases have been studied by Damaschke. In the so-called equal prices model a 2-competitive algorithm is devised and a 1.618 lower bound is given. Here we make use of an averaging technique and obtain a better tight lower bound of 2, in other words, this lower bound cannot be improved. Furthermore, another special case which only considers two-stage device replacement is studied in this paper. Accounting for the interest rate is an essential feature of any reasonable financial model. Therefore, we explore the two-stage model with and without the interest rate respectively. In addition, we introduce the risk-reward model to analyze this problem and improve the competitive ratio performance.

A Better Semi-online Algorithm for Q3/s_1=s_2≤s_3/C_(min) with the Known Largest Size

This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.

Competitive analysis for discrete multiple online rental problems

Many actual rental activities present online rental problems with multiple units of assets or equipment whose use can be continuous,separable,or discrete.Using online algorithms and competitive analysis,continuous multiple online rental problems have obtained the optimal risk control strategy and the optimal competitive ratio.For multiple online rental problems with discrete assets,first,we present an approximation algorithm for a risk control strategy and the upper bound of the optimal competitive ratio.Moreover,in practical applications,the approximation algorithm of the discrete online problem provides the approximate rental quantities in each period and the solution principle for the approximate competitive ratio.Second,we present the approximate optimal rental quantities and the correction algorithm to obtain a better competitive ratio based on the approximation algorithm.Finally,we compare the approximation algorithm with the correction algorithm by real data.Our findings show that when the approximate solution is used to replace the corrected solution,the resulting approximation error is usually less than the magnitude of 1/ms where m is the total units of certain assets or equipment and s is the price to buy one unit in each period.

Online scheduling of two type parallel jobs on identical machines

In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using ＂temporary schedule＂.

单源点疏散问题的Online探索算法研究

课题所研究的问题是受困人员如何从未知情形的受灾区域中尽快地完成撤离.单源点疏散问题是指受灾人员位于危险区域P中的某个位置,需要找到一条能够快速地到达安全位置(P的边界)的疏散路线.由于受灾人员不知道P边界的任何信息,所以采用online探索算法,针对单组单源点疏散问题,提出了三角形疏散策略探索凸多边形区域,计算出所提算法的竞争比为19.48,低于已有算法的竞争比,即优于现有求解该问题的其它算法.同时提出了分组数为2的半圆疏散策略用于探索P为任意多边形区域的情形,得到了一个较小的竞争比,结果表明,单源点半圆疏散策略可以较好地解决疏散区域为非凸多边形的疏散问题.

带有配额的在线旅行维修工问题

为了将应急物资公平且迅速地送往受灾点,本文提出救援车辆装载能力有限且不必返回出发点的在线旅行维修工问题。使用在线算法分析求解,证明了该问题在正半轴网络和一般网络上的下界。分别对正半轴网络上的情形设计了Blindly Turn Left(BTL)算法,对一般网络上的情形设计了逆杠杆算法,给出上述在线算法的竞争比并分析了其竞争性能,与前人研究的在线旅行维修工问题对比发现,逆杠杆算法的竞争性能更优。最后通过数值仿真对受灾网络规模、受灾点数量和配送车辆容量进行敏感性分析,研究得到逆杠杆算法更适用于网络规模、车辆容量和受灾点密度较大的情形。

占线决策问题及竞争分析方法

基于近年来理论计算机科学领域的热点研究方向——占线算法与竞争分析理论,将相关概念引入经济管理决策问题当中,比较分析处理占线经济管理决策问题的竞争分析方法与传统Bayesian优化方法的区别以及后者的缺陷,构建利用占线算法及其竞争分析方法研究占线经济管理决策问题的理论框架,指出在进行占线分析时应注意的要点及分析方法,最后以两个实例加以说明。

空间众包环境下的3类对象在线任务分配

随着移动互联网技术与O2O(offline-to-online)商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足:(1)现有工作通常假设基于静态场景,即,全部众包任务和众包工人的时空信息在任务分配前已完整获知,但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此,现存研究结果在实际应用中缺乏可行性;(2)现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,提出了一类新型动态任务分配问题,即,空间众包环境下的3类对象在线任务分配.该问题不但囊括了任务分配中的3类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.进而设计了随机阈值算法,给出了该算法在最差情况下的竞争比分析.采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终通过在真实数据集和具有不同分布人造数据集上进行的大量实验,验证了算法的效果与性能.

收益约束下在线租赁最小风险策略竞争分析

在线算法是研究信息不确定决策问题的一种新工具。应用在线算法研究金融租赁问题(在线租赁)是近年来国内外的一个研究热点。本文在前人研究基础上,讨论了给定收益约束下在线租赁最小风险策略,完善了在线租赁的风险收益竞争分析。同时我们也把基本的在线租赁扩展为可退货在线租赁问题,并进一步讨论了可退货在线租赁问题的风险最小策略。本文结果对在线租赁研究具有重要意义。

在线多租赁选择问题的最优竞争策略

在线算法与竞争分析是研究信息不确定决策问题的一种新工具,应用该方法研究在线租赁问题是近年来国内外的一个研究热点。传统的在线租赁问题以经典的"雪橇租赁模型"为基础,考虑在线决策者可以选择购买或按单位时间租赁的方式来使用设备。然而现实租赁市场(比如汽车租赁,房屋租赁)往往提供多种租赁方式供在线决策者选择,除了按单位时间进行租赁,通常可以以一个较优惠的价格租赁多个单位时间。在这种现实背景下,本文建立了多种租赁形式下的在线租赁模型,给出了这种租赁模型下的确定性竞争策略,并证明该策略具有最优竞争比。

租金费用和购买价格连续可变的在线租赁竞争策略分析

本文运用竞争分析方法研究了占线金融租赁决策问题,已往的研究都是基于租赁设备的租用费用和购买价格不变的情形给出最优投资策略,本文给出了当价格在有界范围内连续可变时的占线投资策略,并对有无利率两种情形分析进行了竞争策略分析,分别给出了其竞争比的上下界。

基于任务跟踪的在线租赁问题与竞争策略研究

现实经济活动中,有许多租赁融资决策既非纯在线租赁问题也非纯离线租赁问题,而是介于二者之间的具有部分已知信息的在线租赁问题。基于此研究了工作任务总量已知而工作任务进展序列未知的在线设备租赁问题,以租赁工作所需设备的费用最小为优化目标,建立了该问题的基本数学模型,提出了任务跟踪策略,给出并证明了基于这一策略的算法的竞争比。最后,把该在线租赁问题的竞争比与经典的在线租赁问题的竞争比做了比较分析,结果表明在线租赁问题的算法优于经典的在线算法,竞争性能得到了较大的提高。

考虑二手货市场的在线租赁决策与竞争

以往的在线租赁研究基于Karp提出的"雪橇租赁"模型,其假设当租赁方购买设备后不允许出售。研究了存在二手货市场的在线设备租赁问题,即购买的设备可在二手货市场上出售。讨论了设备在二手货市场出售价格为2种不同情形下问题的竞争策略。第1种情形,出售价格围绕购买设备的剩余价值(购买价格与价值损耗量之差)上下波动,分析了问题的离线最优解,并证明不存在具有常数竞争性能比的租赁策略。第2种情形为第1种情形的特例,其出售价格完全由购买设备的剩余价值决定,给出一个租赁策略,并证明了该策略为最优策略,其竞争比小于Karp"雪橇租赁"模型中最优策略的竞争比。