带有资源冲突的Seru在线并行调度算法

随着大规模定制的市场需求日趋显著,赛如生产系统(Seru production system,SPS)应运而生,逐渐成为研究和应用领域的热点.本文针对带有资源冲突的Seru在线并行调度问题进行研究,即需要在有限的空间位置上安排随动态需求而构建的若干Seru,以总加权完工时间最小为目标,决策Seru的构建顺序及时间.先基于平均延迟最短加权处理时间(Average delayed shortest weighted processing time,AD-SWPT)算法,针对其竞争比不为常数的局限性,引入调节参数,得到竞争比为常数的无资源冲突的Seru在线并行调度算法.接下来,引入冲突处理机制,得到有资源冲突的Seru在线并行调度算法,αAD-I(α-average delayed shortest weighted processing time-improved)算法,特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同.最后,通过实验,验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性.     

一种基于协同进化的流水线向Seru系统转化方法

Seru生产系统是一种被广泛应用于电子制造产业的新型生产模式,但由于流水线向Seru系统转化问题（Line-seru conversion）包含有Seru构建与Seru调度两个相互耦合的子问题,现有算法难以在同时兼顾解的质量与计算效率的情况下对问题进行求解.因此,本文针对流水线向Seru系统转化问题的特点,提出了一种协同进化算法,即在进化算法中加入了协同机制,将Seru构建与Seru调度子问题作为两个子种群利用该机制进行协同进化,从而弥补了现有算法的不足.并且,本文还针对问题特点设计了个体基因编码方式,从而使规划获得的Seru生产系统具有更优的生产性能及均衡性能.实验表明,采用加入了协同机制的进化算法比传统解决流水线向Seru系统转化问题的方法具有更好的性能,本文所提的方法在最小化产品流通时间和劳动时间有较好的性能表现,并且具有较高的计算效率.     

NoC中基于路径树的无冲突测试调度方法

在复用片上网络(No C)架构作为测试访问机制对No C内嵌核进行测试时,如果有多个I/O接口并行测试就容易发生资源的冲突.为了解决多区域并行测试的资源冲突问题,提出一种无链路冲突的测试调度方法.首先使用分区算法将网络划分多个区域,然后使用链路分配算法对节点建立路径树来查找可连通路径,最后全局考虑各个区域的连通路径来分配链路使所有区域都连通,从而避免资源冲突、减少测试时间、保证测试可靠性.实验结果表明,相对于基准对象,该方法可减少测试时间14.13%~52.62%,比已有算法的测试时间最多减少了16.42%,是一种较优的无冲突测试调度方法.     

单步预测的单机调度算法及其仿真分析

调度问题中在线算法只能够利用已经到达的工件信息进行调度,但在实际生产中,往往有可能预知即将到达的未来工件信息,并且利用信息进行决策.针对经典单机加权完工时间调度问题,根据预测控制的思想,提出了一种单步预测调度的算法,并且分别在理论证明和仿真两方面进行了分析.对单步预测调度算法进行了性能分析,在理论上证明了预测调度算法的竞争比下界为2,对于一般的情况进行了大鼍的仿真比较,由于在调度中增加了未来信息,单步预测调度算法的调度结果优于在线调度算法.     

多核处理平台上任务图模型的并行调度策略研究

凭借着高性能,低功耗的特性,多核处理器已经占据了目前的主要市场.提出一种多核处理平台上基于任务图模型的调度策略.建立了多核平台上任务图的空间与时间并行调度模型;针对任务图的空间并行与时间并行调度模型提出了并行节点合并、分配的优化算法与流水线并行的优化算法.最后,提出将优化的空间与时间并行调度技术相结合的并行调度策略.通过实验验证,本文提出的算法比其他多核并行调度算法降低了处理器核心间的通信与同步开销,提高了系统的计算效率与吞吐量.     

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

针对众核处理器系统的核资源优化使用问题,提出了一种支持核资源动态分组的自适应调度算法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算法大幅度地提升了系统吞吐量.     

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

工作环境为两台处理速度相同的平行机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.     

磁带库系统的随机I/O调度算法

由于磁带库随机存取的性能很差,需要研究有效的随机I/O调度策略和算法以改善其在线存取的效率.对已有调度算法进行了分类、提炼和总结,利用仿真实验对静态调度、动态调度和基于复制的调度算法进行了深入研究,讨论了影响各种算法有效性的因素.针对已有算法在较重的负载条件下使系统性能急剧恶化的问题,还提出并研究了一种基于效益-代价均衡的调度算法.该算法引入效益-代价加权的概念,通过调节不同负载下的效益-代价加权比,极大地改善了已有算法在重负载下的有效性.该项研究为设计海量存储系统中的自适应调度算法提供了重要依据.     

TCPN的变迁弱规则特有的调度可达决策区域及算法

针对时间限制Petri网(TCPN)采用的变迁弱激活规则和基于TCPN的动态标记, 引入变迁的调度延时决策变量和决策空间概念刻画TCPN的状态可达可调度规律.这些概 念及其算法揭示了TCPN网的并发分布式动态调度特征.特别是变迁弱规则固有的容许含 有失败变迁的并行分布式调度问题,描述了涉及具有有效期的可释放资源类实时系统的特殊 调度问题及其规律.     

桥吊迁移的港口连续泊位分配问题在线算法

集装箱码头资源的高效利用已被研究多年,而多数是在预知所有船舶作业的相关信息(到港时间、船舶尺寸等)的离线情况下建模与计算.现实中,却因一些突发因素(如恶劣天气、设备故障等)使预知信息不可靠,以至原调度方案不可行,从而降低港口作业效率及资源浪费.故在桥吊可迁移的连续泊位分配模式下,首次结合在线算法思想,提出泊位与桥吊调度的模型,并设计相应的在线调度算法.利用平滑分析方法给出算法的平滑竞争比,实验证实算法可行性.     

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

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

Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time

We consider online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. We show that no online algorithm can have a competitive ratio less than 1+αm, where αm is the positive root of α²+(m+1)α−1=0, and this lower bound is still valid even when all jobs have the same processing times. Then we provide an online algorithm of competitive ratio 1+1/m. When the jobs have the same processing times, we present a best possible online algorithm of competitive ratio 1+αm.     

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

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

A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time

The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5–1/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.     

On robust online scheduling algorithms

While standard parallel machine scheduling is concerned with good assignments of jobs to machines, we aim to understand how the quality of an assignment is affected if the jobs’ processing times are perturbed and therefore turn out to be longer (or shorter) than declared. We focus on online scheduling with perturbations occurring at any time, such as in railway systems when trains are late. For a variety of conditions on the severity of perturbations, we present bounds on the worst case ratio of two makespans. For the first makespan, we let the online algorithm assign jobs to machines, based on the non-perturbed processing times. We compute the makespan by replacing each job’s processing time with its perturbed version while still sticking to the computed assignment. The second is an optimal offline solution for the perturbed processing times. The deviation of this ratio from the competitive ratio of the online algorithm tells us about the “price of perturbations”. We analyze this setting for Graham’s algorithm, and among other bounds show a competitive ratio of 2 for perturbations decreasing the processing time of a job arbitrarily, and a competitive ratio of less than 2.5 for perturbations doubling the processing time of a job. We complement these results by providing lower bounds for any online algorithm in this setting. Finally, we propose a risk-aware online algorithm tailored for the possible bounded increase of the processing time of one job, and we show that this algorithm can be worse than Graham’s algorithm in some cases.     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).     

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 And Offline Scheduling Schemes to Maximize the Weighted Delivered Video Packets Towards Maritime Cpss

In this paper, the online and offline scheduling schemes towards maritime Cyber Physical Systems (CPSs), to transmit video packets generating from the interior of vessel. During the sailing from the origin port to destination port, the video packets could be delivered via the infostations shoreside. The video packets have their respective release times, deadlines, weights and processing time. The video packets only could be successfully transmitted before their deadlines. A mathematic job-machine problem is mapped. Facing distinguished challenges with unique characteristics imposed in maritime scenario, we focus on the heterogeneous networking and resource optimal scheduling technology to provide valuable insights on the data transmission scheduling via this system. We aim to maximize the weight of delivered packets totally, three algorithms, an offline algorithm, an online ADMISSION Algorithm with no bounded processing times, as well as Exponential-Capacity Algorithm with bounded processing times are developed. Moreover, we induct the approximation ratio and competitive ratios of the proposed algorithms respectively. Finally, we verify the performance of the potential solutions for resource scheduling through comparison simulation.     

Parallel machine scheduling with precedence constraints and setup times

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. These problems are strongly NP-hard and it is even conjectured that no list scheduling algorithm can be defined without explicitly considering jointly scheduling and resource allocation. We propose dominance conditions based on the analysis of the problem structure and an extension to setup times of the energetic reasoning constraint propagation algorithm. An exact branch-and-bound procedure and a climbing discrepancy search (CDS) heuristic based on these components are defined. We show how the proposed dominance rules can still be valid in the CDS scheme. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.