具有前瞻区间的两个工件组单机在线排序问题

• 作者: 李文华 杨素芳
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 在线排序 平行分批 不相容工件组 最大完工时间 竞争比
• 年，卷（期）: 2012,（2）
• 页码范围: 115-120
• 分类号: O223
• 字数: 3208字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2012.02.011

摘要

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在无界平行分批排序中,一台容量无限制机器可将多个工件形成一批同时加工,每一批的加工时间等于该批中最长工件的加工时间.具有前瞻区间是指在时刻t,在线算法能预见到时间区间(t,t+β)内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为1+α的最好可能的在线算法,其中α是方程2α2+(β+1)α+β-2=0的一个正根,这里0≤β＜1.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李文华	郑州大学数学系	17	50	4.0	5.0
2	杨素芳	郑州大学数学系	4	9	2.0	3.0