最大化接收工件个数的在线分批排序问题研究

• 作者: 李文杰 马冉
• 来源期刊: 郑州大学学报（理学版）
• 学科: 数学
• 关键词: 在线排序 在线算法 批处理机 竞争比
• 年，卷（期）: 2016,（2）
• 页码范围: 24-28
• 页数: 5页
• 分类号: O223
• 字数: 5308字
• 语种: 中文
• DOI: 10.13705/j.issn.1671-6841.2015216

摘要

研究m台批处理机上的等长工件在线排序问题.在该问题中,工件是随着时间依次到达的,每个工件J具有一个共同的加工时间p＞0,一个释放时间rj≥0,一个必须交货期dj＞0.一台机器可以同时加工b个工件(b个工件构成一批),b=∞表示批容量无界.每一批的加工时间由该批中工件的最长加工时间来决定.同一批中的所有工件均具有相同的开工时间和完工时间,目标是确定一个工件可以被中断重启的在线排序最大化接收工件总个数.首先,当m=2、3时分别给出了问题的下界为2和6/5.其次,设计出了问题的一个在线算法H并证明其竞争比分别为3(当m=2时)、4(当m=3或m≥4为偶数时)和5(当m≥5为奇数时).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马冉	河南理工大学数学与信息科学学院	21	10	2.0	2.0
2	李文杰	洛阳师范学院数学科学学院	4	1	1.0	1.0