平行批排序最小化最大完工时间在线算法的一个注记

• 作者: 农庆琴 原晋江
• 来源期刊: 郑州大学学报（理学版）
• 学科: 数学
• 关键词: 排序 在线算法 平行批 最大完工时间 渐近最优
• 年，卷（期）: 2006,（3）
• 页码范围: 1-3
• 页数: 3页
• 分类号: O224
• 字数: 1030字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-6841.2006.03.001

摘要

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,Naval Research Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algorithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为((√5)+1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1+α)r+αp时刻以后加工,其中α=((√5)-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	原晋江	郑州大学数学系	26	97	6.0	7.0
2	农庆琴	郑州大学数学系	2	10	1.0	2.0