最大化接收工件总权值的批处理机在线排序

• 作者: 李文杰 熊建栋 翟红村
• 来源期刊: 河南师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 在线排序 竞争比 批处理机 接收工件总权值
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 数学
• 页码范围: 8-14
• 页数: 7页
• 分类号: O224
• 语种: 中文
• DOI: 10.16366/j.cnki.1000-2367.2017.01.002

摘要

研究m台无界批处理机上的在线排序问题.每个工件Jj具有一个相同的加工时间p＞0,一个到达时间rj≥0,一个权值wj＞0,一个必须交货期dj＞0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m2-m)1/2/(2m2-m).