带等级约束的多重工件在线(半在线)排序问题
代兵飞
夏玉霞
1.云南大学数学与统计学院 昆明 6500002.云南大学数学与统计学院 昆明 650000
摘要：论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件.目标是寻找一个调度方案,使得机器的最大完工时间最小.当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法.当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法.这些结论对经典带等级约束的两台平行机排序问题进行了推广.
关键词：多重工件等级约束在线算法半在线算法
分类号：TP301.5(计算技术、计算机技术)TP301.6(计算技术、计算机技术)
论文发表日期：2020-03-20
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：5( 586-589,677 )
英文信息