许可图约束下带释放时间的两机排序算法

作者：童昕; 张亮; 张安^*; 陈永; 陈光亭

来源：杭州电子科技大学学报(自然科学版), 2022, 42(06): 90-94.

DOI：10.13954/j.cnki.hdu.2022.06.015

• 平行机排序
• 许可图
• 匹配
• 近似算法
• 最坏情况界

研究一类许可图约束下的2台平行机排序问题，目标是最小化时间表长。针对许可图为二部图，在加工时间为1的工件仅在0时刻释放而加工时间为2的工件在0时刻或r时刻释放的强NP-难情形下，设计了基于最大权匹配方法的近似算法，证明了算法的最坏情况界为■。

• 单位
  浙江水利水电学院; 杭州电子科技大学