摘要：研究工件可提前预知信息的在线分批排序问题,工件的预知信息时间依时间到达,目标为极小化最大完工时间.已知从工件的信息可预知到该工件可加工需要时间a,所有工件的最大加工时间为p_（max）,多个工件可以作为一批被机器同时加工,批的加工时间为该批工件中最长加工时间.对于批容量无限的单机问题给出一个在线算法γH-∞,并证明其竞争比和问题的下界都为1＋γ,其中γ=（-1＋（1＋（4p（max））/（p（max）＋a）））/2,进而算法是最优的.
分类：期刊> 自然科学与工程技术> 基础科学> 数学
收录：北大期刊(中国人文社会科学期刊) > CSCD 中国科学引文数据库来源期刊(含扩展版) > 统计源期刊(中国科技论文优秀期刊) > 知网收录(中) > 维普收录(中) > 万方收录(中) > JST 日本科学技术振兴机构数据库(日) > 国家图书馆馆藏 > 上海图书馆馆藏
关键词：分批排序 竞争比 在线算法
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
