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

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

项目编号： No.11201391

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 陶继平

作者单位： 厦门大学

项目金额： 22万元

中文摘要： 在线排序作为一种信息匮缺情况下的组合优化问题，广泛存在于生产制造、并行计算及公共服务等领域。本项目针对多个 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 informa

英文关键词： onliine scheduling；semi-online scheduling；competitive analysis；instances space contraction；performance ratio