工件具有区间限制的批在线调度

• 作者: 唐立新 霍满臣
• 来源期刊: 东北大学学报（自然科学版）
• 学科: 工学
• 关键词: 批在线列表调度 竞争率 同构并行机 批工件列 最大完成时间 加工时间
• 年，卷（期）: 2006,（7）
• 所属期刊栏目: 信息与控制
• 页码范围: 728-730
• 页数: 3页
• 分类号: TP301.6
• 字数: 2297字
• 语种: 中文
• DOI: 10.3321/j.issn:1005-3026.2006.07.006

摘要

研究同构并行机上的批在线调度问题,目标函数是使最大完成时间(最后一个工件的完成时间makespan)最小.工件以批方式到达且每个批中有m个工件,每个工件的加工时间随其批的到达而给定且限定在某个时间区间上.当一批工件到达时,在对其后批的信息不了解的情况下,要立即对该批中的工件进行调度,调度过程中不允许中断.针对这一问题,给出了一个批在线启发式列表调度算法,在同一批中的工件按LPT规则调度,当一批中的全部工件被调度完后,调度下一批中的工件.对算法的最坏情况进行了分析并给出了算法的竞争率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐立新	东北大学信息科学与工程学院	106	2154	24.0	41.0
2	霍满臣	东北大学信息科学与工程学院	4	28	3.0	4.0