基于实例空间压缩的minsum目标的平行机在线排序研究

As a discrete optimization problem without the global information, online and semi-online scheduling problems exist in areas such as manufacturing, parallel computing, communication network, and public service system. Due to the lack of the global information, an optimization algorithm based on the complete formulation about the considered problem cannot be constructed. In addition, many online scheduling problems are time-critical, where dispatch rules with a reasonable computing time have to be used. However, these kind of heuristic rules often perform unstably even for instances from the same problem. It is necessary to analyze the competitive performance of online scheduling algorithms...The project considers several parallel machine scheduling problems with minsum criteria in the online setting where jobs arrive over time. First, the common dilemma which online algorithms have to face is investigated. Then the algorithm design and competitive analysis is developed based on the observation on the corresponding worst case instances. For the lower bound on the competitive ratio of any online algorithm for a problem, the so-called adversary method is used. For algorithm design, priority rules based waiting strategies are utilized in order to take account of all kinds of worst case instances. For competitive analysis, the instances space contracting based method is developed, which transforms the instance towards the possible structure of the worst-case instance with respect to the given online algorithm by increasing or reducing some parameters of some jobs, such that the modified instance shows a more special structure of which we can take advantage to analyze the performance ratio. The project aims to not only propose better online or semi-online algorithms for several parallel machine online scheduling problems with minsum criteria, but also to develop a relative general method based on the idea of instances space contracting to analyze the competitive performance.

在线排序作为一种信息匮缺情况下的组合优化问题，广泛存在于生产制造、并行计算及公共服务等领域。本项目针对多个 minsum 目标的平行机时间在线排序模型，分析这类问题对应的在线算法由于缺乏完整信息而所面临的困境，挖掘相应算法所对应最差实例的特点与共性，展开以最差实例为中心的算法设计与分析。在分析问题竞争比下界时，用对手策略构造一系列特殊实例以导出较紧的下界；在设计算法时，构造基于工件优先级的在线等待策略,以保证其能兼顾到各类最差实例；在竞争分析时，通过调整任意实例的某些参数使其向最差实例可能的结构靠近，逐步将最差实例的搜索空间从整个实例空间压缩到更小的子集，以导出期望的竞争比。本项目不仅旨在为最小化总加权完工时间的各类平行机在线排序,以及加工时间有界的相应半在线问题,提出具有更好竞争性能的在线或半在线算法，还意在发展一种更具一般性与系统性的基于实例空间压缩的竞争分析方法。

在线排序作为一种信息匮缺情况下的组合优化问题，广泛存在于生产制造、并行计算及公共服务等领域。本项目针对多个 minsum 目标的平行机时间在线排序模型，分析这类问题对应的在线算法由于缺乏完整信息而所面临的困境，挖掘相应算法所对应最差实例的特点与共性，展开以最差实例为中心的算法设计与分析。主要研究内容及相应成果包括：.1、提出并完善了一种新颖的基于实例空间压缩的竞争比分析方法，并将该方法应用于多个 minsum 目标的平行机时间在线排序模型，设计了更好的在线算法。.2、研究了最小化总加权完工时间的同速并行机在线调度，通过扩展相应单机及非加权情况下的在线算法，提出了基于平均剩余时间延时的AD-SWPT算法，并采用基于实例空间压缩的分析方法，证明了该算法的竞争比为2.5-1/2m.相应成果发表在计算机与运筹学方面的优秀国际期刊《Computers & Operations Research》。.3、针对上述的2.5-1/2m算法，进一步设计了一个以机器数m为参数的算法，该算法将竞争比提高到了2.28，相应结果发表在《Journal of Industrial Management Optimization》。.4、针对加工时间有界的最小化总加权流通时间的单机半在线调度及同速并行机半在线调度，采用基于实例空间压缩的方法分别分析了SWPT规则的竞争性能，证明了SWPT针对单机情形为最优的半在线算法，针对并行机情形其竞争比不超过P+1.5-1/2m，其中P为实例中最大加工时间与最小加工时间的比值。成果发表在《Mathematical Problems in Engineering》。.5、将基于实例空间压缩方法应用到一个加工时间具有恶化效益的单机调度，得到了一个最优的在线算法，成果发表在《Applied Mathematics and Computation》。.本项目不仅为最小化总加权完工时间的各类平行机在线排序提出了具有更好竞争性能的在线或半在线算法，还发展了一种更具一般性与系统性的基于实例空间压缩的竞争分析方法，该方法可以应用于其它具有类似结构的排序问题的在线算法分析。.经过三年的研究，受到该项目的资助，已发表12篇学术论文，其中5篇被SCI收录，在项目研究进行中，培养或协助培养了多名研究生。