带运输时间和单自动机的流水作业排序

来源：石河子大学学报·自然科学版杂志2018年第4期北京时间：

作者：时凌, 张琼, 时义梅, 刘丁酉

单位：（1 广州工商学院基础教学部，广东 广州 510850；2 湖北民族民族学院理学院,湖北 恩施 445000; 3 武汉大学数学与统计学院, 湖北 武汉 430072）

摘要：本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间，所有运输时间都是由单自动机来完成运输，同一时间自动机只能运输一个工件，本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性，并给出新的启发式算法，证明该算法的最坏性能比是32，且上界是紧的。 

关键词：流水作业排序问题;复杂性;运输时间;单自动机

基金资助：国家自然科学基金(6134030)，广州工商学院 2018 院级科研（KA201831）项目