基于实例空间压缩的在线及半在线调度算法的竞争分析

发布时间：2018-05-25 03:23

  本文选题：在线调度 + 半在线调度　； 参考：《上海交通大学》2014年博士论文

【摘要】：在线或半在线调度作为一种信息匮缺情况下的优化决策问题,广泛存在于生产制造、通信网络、电力系统、交通运输及公共服务系统等领域。由于缺乏完整信息,一般不能建立基于问题完整描述的优化算法,此外,在线调度在很多情况下还有实时性要求,这使得大部分在线调度都采用一些计算要求简单的分派规则,由于这些规则多为启发式的,即使应用到相同问题的不同实例也可能出现性能差异甚远的情况。因此,为了对规则的选择和应用提供理论支持,还需分析研究相应调度算法的竞争性能。 在竞争分析的历史研究中,采用的很多方法都具有很强的问题依赖性,证明分析都依赖于一些辅助调度的巧妙构造,过程通常也显得相当繁琐,精妙有余而规律性不强。本文首先尝试进行竞争比分析方法的研究,提出了一种基于实例空间压缩的较为一般的分析方法,然后将其应用到多个在线及加工时间有界的半在线调度问题的算法设计与竞争分析上,归纳起来,本论文的研究内容主要包括以下四个方面： ·提出了一种新颖的基于实例空间压缩的竞争比分析方法,阐述了该方法的基本思想及常用的空间压缩方法,并将该方法应用于最小化总完工时间及总加权完工时间的单机调度,针对现有的两个最优在线算法,分别给出了替代的竞争比证明。 ·研究了最小化总加权完工时间的同速并行机在线调度通过扩展相应单机及非加权情况下的在线算法,提出了基于组合延时的CD-SWPT算法,并采用基于实例空间压缩的分析方法,证明了该算法的竞争比位于[2,2.5-1/2m]之间。 ·研究了加工时间有界的最小化总完工时间及总加权完工时间的单机半在线调度问题,针对提出了αD-SPT算法,并应用基于实例空间压缩的方法证明其竞争比为针对γ|∑ωjCj,提出了αD-SWPT算法,并应用基于实例空间压缩的方法证明了其竞争比为同时证明了该竞争比也是针对该问题的任何半在线算法所能取得的最好结果。 ·针对加工时间有界的最小化总加权流通时间的单机半在线调度及同速并行机半在线调度采用基于实例空间压缩的方法分别分析了SWPT规则的竞争性能,证明了SWPT针对单机情形为最优的半在线算法,相应的竞争比为γ+1,针对并行机情形其竞争比位于[γ+1,γ+1.5-1/2m]之间。
[Abstract]:As an optimal decision making problem in the absence of information, online or semi-online scheduling is widely used in manufacturing, communication networks, power systems, transportation and public service systems. Because of the lack of complete information, the optimization algorithm based on the complete description of the problem can not be established generally. In addition, there are real-time requirements in many cases for online scheduling, which makes most online scheduling adopt some simple dispatch rules that require simple computation. As most of these rules are heuristic, even if they are applied to different instances of the same problem, the performance may vary greatly. Therefore, in order to provide theoretical support for the selection and application of rules, it is necessary to analyze and study the competitive performance of the corresponding scheduling algorithms. In the historical study of competition analysis, many of the methods used have strong problem dependence. It is proved that the analysis depends on the ingenious construction of some auxiliary scheduling, and the process is usually very complicated, subtle and irregular. In this paper, we first try to study the competitive ratio analysis method, and propose a more general analysis method based on case space compression. Then it is applied to the algorithm design and competition analysis of multiple online and semi-online scheduling problems with bounded processing time. In summary, the research contents of this paper mainly include the following four aspects: A novel competitive ratio analysis method based on case space compression is proposed. The method is applied to single machine scheduling which minimizes the total completion time and the total weighted completion time. For the existing two optimal online algorithms, the alternative competitive ratio proof is given respectively. In this paper, the on-line scheduling of parallel machines at the same speed, which minimizes the total weighted completion time, is studied. By extending the corresponding on-line algorithms in the case of single machine and non-weighted case, the CD-SWPT algorithm based on combinatorial delay is proposed, and the analysis method based on case space compression is adopted. It is proved that the competitive ratio of the algorithm is between [2] 2. 5-1 / 2 m. In this paper, the semi-on-line scheduling problem of single machine with bounded processing time to minimize the total completion time and the total weighted completion time is studied, and a 伪 D-SPT algorithm is proposed to solve the problem. The case based space compression method is used to prove that the competition ratio is 纬 鈭，

本文编号：1931866