基于实例空间压缩的minsum目标的平行机在线排序研究-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

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

项目名称：基于实例空间压缩的minsum目标的平行机在线排序研究
项目类别：青年科学基金项目
批准号：11201391
申请代码：A011202
项目来源：国家自然科学基金
研究期限：2013-01-01-2015-12-31

项目负责人：陶继平
依托单位：厦门大学
批准年度：2012

中文摘要：

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

中文主题词：在线调度；半在线调度；竞争分析；实例空间压缩；性能比

结论摘要：

英文主题词onliine scheduling；semi-online scheduling；competitive analysis；instances space contraction；performance ratio

成果综合统计