时凌，张琼，时义梅，刘丁酉*

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

带运输时间和单自动机的流水作业排序问题可叙述为:假设给定由m台机器构成的机器集{M1,M2,...,Mm}和由n个工件组成的工件集{J1,J2,...,Jn}。每个工件Jj均有m道工序Qi,j(i=1,2,...,m;j=1,2,...,n),其加工顺序Q1,j→Q2,j→...→Qm,j，其中，每道工序Qi,j在机器上Mi的加工时间为pi,j(pi,j≥0)。每台机器在同一时间只能加工一个工件。

本文假设一个工件在一台机器上完工后在下一台机器加工之前存在一个时间间隔,即工序Qk,j在机器Mk上完工后,下一道工序Qk+1,j在机器Mk+1上加工之前需要一定的运输时间tj,k(tj,k≥0),所有的运输工作均由自动机R来完成，自动机同一时间也只能对一个工件进行运输。这样工件在运输和加工的过程中就可能会出现一定的冲突。

本文研究的目的是要确定可行排序使完工时间的加权和达到最小,即达到最小,其中Cj是工件Jj最后一道工序Qm,j的完工时间。依据Lawer E L等[1]提出的三元法,带运输时间和单自动机的流水作业排序问题可表示为:,如果不带运输时间和单自动机则可表示为。如果只考虑2台机器,自动机只需在机器M1和机器M2之间运输,运输时间可简化为tj,则该问题可表示为。本文主要研究当所有加工时间均等于1,即时流水作业的排序,即研究排序的复杂性和启发式算法。

现在考虑2台加工机器M1、M2和单自动机R,n个工件在机器M1和机器M2上的加工时间分别为p1,j和自动机的运输时间为tj。

假设序列σ和τ分别表示工件在机器M1和机器上的加工顺序,C(σ,τ)表示问题的最小完工时间。……