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

摘要

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