两台等级平行机上部分处理时间已知的半在线调度

工作环境为两台处理速度相同的平行机M1,M2,工件具有两种不同的等级gj=1或2,等级gj=1的工件只能在第1台机器上处理,等级gj=2的工件两台机都能处理.已知等级gj=1的工件的处理时间之和,目标是最小化最大完工时间.主要思路为第一台机器预留出等级gj=1的工件的总处理时间,分析过程中只对等级gj=2的工件进行讨论.文章的三种半在线等级调度问题分别为已知最优处理时间,即已知C opt的情况,可得竞争比大于等于4/3,并有竞争比为4/3的半在线算法;已知工件的最大处理时间,可得竞争比大于等于4/3,同样有算法得出竞争比为4/3;对已知最优处理时间和工件最大处理时间的半在线问题,得到竞争比大于等于6/5,并且找到了相应的算法竞争比小于等于6/5.     

三台等级机器上带重排的半在线问题

研究了3台机上带2种等级的重排问题,当所有工件都被分配之后,在等级约束下,可以重排一台机器上的最后一个工件,目标是最小化最大完工时间。3台机上带2种等级分为2种情形：第1种是有1台机器的等级为1,另2台机器的等级为2;第2种是2台机器的等级为1,另1台机器的等级为2。针对第1种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为5/3的在线算法;针对第2种情形给出了一个竞争比下界为3/2,并提出了一个竞争比至多为12/7的在线算法。     

带等级约束的多重工件在线(半在线)排序问题

论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件。目标是寻找一个调度方案,使得机器的最大完工时间最小。当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法。当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法。这些结论对经典带等级约束的两台平行机排序问题进行了推广。     

P_4|fix|C_(max)问题的最优规则调度算法

多处理机任务调度问题P4|fix|Cmax(m≥=)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.     

半在线调度中约束求解算法研究

很多实际调度问题是半在线的. 尝试运用人工智能方法来求解半在线调度问题, 首先简要介绍了半在线调度问题并对其约束模型进行了分类, 通过引入单调性约束扩展的相关概念, 从约束建模角度形式化描述 了一类动态约束扩展, 并在此基础上设计了一个完备动态约束求解算法, 最后给出该算法在半在线离散资源约束调度求解的应用算例. 测试结果表明, 该算法是可行有效的.     

带有多折扣选项的滑雪租赁问题的在线和离线算法

研究了带有多折扣选项的滑雪租赁问题（ski-rental problem with multiple discount options,简称多折扣租赁问题）的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.     

三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

无线网络中的在线信道分配问题

研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k 2)*/(k 1);还给出了一个竞争比为2的1-look-ahead算法.     

众核处理器系统核资源动态分组的自适应调度算法

针对众核处理器系统的核资源优化使用问题,提出了一种支持核资源动态分组的自适应调度算法CASM(core-partitioned adaptive scheduling for many-core systems).该算法通过对任务簇的拆分与合并,动态构建可弹性分区的核逻辑组,实现核资源的隔离优化访问.为了平衡核资源利用率及任务调度效率,CASM算法针对任务簇间和簇内的不同特点,分别采用公平性较好的均衡调度算法和资源利用率较高的自适应调度算法.在线竞争理论分析表明,CASM算法的任务执行时间在线竞争比为常数2,其性能可扩展性较好.实验结果表明,与WS(work-stealing),AGDEQ(adaptive greedy dynamicequi-partitioning)和EQUI°EQUI算法相比,CASM算法使任务集运行时间分别减少了近46％,32％和15％.在相同能耗情况下,CASM算法大幅度地提升了系统吞吐量.     

线性网络上分布式任务调度算法

针对一种已有的分布式计算理论模型(单位长度的任务由处理器独立产生，没有全局控制，彼此通信需要花费时间)，研究了在线性网络上的任务有效调度问题．通过考虑算法中任务处理时间和通信时间之间的平衡，给出了一个近似比为5．88的分布式算法，该算法无需全局信息，且处理策略简单．对该问题的近似比下界也做了研究，证明了该问题不存在近似比小于1．16的算法．     

Preemptive online algorithms for scheduling with machine cost

For most scheduling problems the set of machines is fixed initially and remains unchanged. Recently Imreh and Noga proposed adding the concept of machine cost to scheduling problems and considered the so-called List Model problem. For this problem, we are given a sequence of independent jobs with positive sizes, which must be processed non-preemptively on a machine. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. The objective is to minimize the sum of the makespan and cost of machines. In this paper, a modified model of List Model is presented where preemption is allowed. For this model, it is shown that better performance is possible. We present an online algorithm with a competitive ratio of while the lower bound is 4/3. For the semi-online problem with decreasing sizes, we design an optimal algorithm with a competitive ratio of 4/3, which improves the known upper bound of 3/2. The algorithm does not introduce any preemption, and hence is also an optimal semi-online algorithm for the non-preemptive semi-online problem. For the semi-online problem with known largest size, we present an optimal algorithm with a competitive ratio of 4/3.Received: 7 June 2004, Published online: 11 November 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110, 60021201).     

带两个服务等级的3台机半在线算法

This paper studies a semi-online hierarchical scheduling problem on three identical machines. In the problem, there is only one machine with hierarchy 1 and two machines with hierarchy 2, and the goal is to minimize the makespan. When the total size of low-hierarchy is known, an online algorithm with the competitive ratio of 5/3 and the lower bound of 3/2 is given. When the total size of high-hierarchy is known, an online algorithm with the competitive ratio of 9/5 and the lower bound of 3/2 is given. When the total size of each hierarchy is known, an online algorithm with the competitive ratio of 3/2 and the lower bound of 4/3 is given. When the total size of jobs is known, a best possible online algorithm with the competitive ratio of 3/2 is given.     

Semi-online scheduling with machine cost

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem.Recently Imreh and Nogaproposed to add the concept of machine cost to scheduling problems and considered the so-called List Model problem.An online algorthm with a competitive ratio 1.618 was given while the lower boud is 4/3.In this paper,two different semi-onlne versions of this problem are studied‘.In the first case,it is assumed that the processing time of the largest job is known a priori.A semi-online algorithm is presented with the competitive ratio at most 1.5309 while the lower bound is 4/3,In the second case,it is assumed that the total processing time of all jobs is known in advance.A semi-online algorithm is presented with the competitive ratio at most 1.414 while the lower bound is 1.161.It is shown that the additional partial available information about the jobs leads to the possibility of constructing a schedule with a smaller competitive ratio than that of online algorithms.     

Semi-Online Algorithms for Scheduling with Machine Cost

In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.     

Online algorithms for scheduling two parallel machines with a single server

We consider an online scheduling problem on two identical parallel machines with a single server. Jobs arrive one by one and each job has to be loaded by the server before being processed on one of the machines, and unloaded immediately by the server after its processing. Both loading and unloading times are equal to one time unit. The goal is to minimize the makespan. For the variant of the problem involving both loading and unloading operations, we present an online algorithm with competitive ratio of 5/3. For the variant with loading operation only, we show that the competitive ratio of list scheduling is at least 8/5 and provide an improved online algorithm with competitive ratio of 11/7. Finally, we discuss the lower bounds for these problems. We show that both variants have a lower bound of 3/2. Furthermore, we show that the lower bound of the first variant is at least 8/5 if the online algorithm satisfies a certain constraint.     

Online rectangle filling

We study an online geometric problem arising in channel-aware scheduling of wireless networks, which we call the online rectangle filling. We present an online algorithm (with one-lookahead) for this problem with a competitive ratio of 1.848, improving the previously best-known 8/3-competitive algorithm in Arora et al. (2006) [4]. We also prove a lower bound of 1.6358 on the competitive ratio of the problem, improving the previous 1.6 lower bound in [4]. In addition, we give an O(n²)-time optimal algorithm for the offline version of the problem, where n is the size of the input, which improves the O(n³)-time solution in Arora and Choi (2006) [3], Arora et al. (2006) [5]. Our techniques are based on interesting techniques and new observations of the combinatorial structures in the problem.     

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.     

Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times

This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2, 3, 4 machine cases. For m ≥ 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is 5/3. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, an algorithm with significantly improved competitive ratio is given.     

A tight lower bound for job scheduling with cancellation

The Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time.