工件带运输时间的单机分批排序问题

• 作者: 刘勇 张玉忠 王成飞
• 来源期刊: 洛阳大学学报
• 学科: 数学
• 关键词: 单机 平行批 在线算法 离线算法 运输时间
• 年，卷（期）: lydxxbb_2007,（4）
• 页码范围: 24-28
• 页数: 5页
• 分类号: O223

摘要

主要考虑了在线和离线两种模型下的工件带运输时间的单机分批排序问题，工件一但被加工完将会被马上运往目的地．我们考虑了三种限制模型：（1）在线模型：批量B无穷大，工件的加工时间和运输时间一致，即：若工件Ji的加工时间Pi大于等于工件Jj的加工时间Pj，那么它们的运输时间有qi≥qj（2）在线模型：批量B无穷大，工件的最大运输时间和最小的运输时间的比小于等于1＋√5/2对于（1），（2）这两种模型我们给出了一个竞争比为1＋√5/2的在线算法，并且这个结果是最好的．（3）离线模二型：批量B有限，当工件的到达时间是整数并且加工时间P=1时，我们给出了一个时间复杂性为O（n^2lnn）的多项式时间算法，当工件的加工时间不是1，但工件的到达时间的个数是一个常数m时，我们给出了一个时间复杂性为O（2^m-1nlnn）的多项式时间算法．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张玉忠	曲阜师范大学运筹与管理学院	115	657	14.0	21.0
2	王成飞	曲阜师范大学运筹与管理学院	13	33	3.0	4.0
3	刘勇	曲阜师范大学运筹与管理学院	4	7	2.0	2.0