一类带特殊序约束的三台机流水作业排序问题

陈占文，张 安，陈 永，陈光亭

(1.杭州电子科技大学理学院，浙江 杭州 310018；2.台州学院电子与信息工程学院，浙江 台州 318000)

0 引 言

带有特定顺序约束的排序问题在实际中有着极为广泛的应用，但是，由于其复杂性大多是NP-难的，因此，很多问题尚未解决。给定m台流水作业机器M1,M2,…,Mm，每个工件必须依次在M1,M2,…,Mm上不重叠地加工一个单位时间，称为工件的m道工序。对任意2个工件Jj,Jk，若其有序约束为JjJk，则工件Jk的第一道工序必须在工件Jj的第m道工序完工后才能加工。工件之间的这种序约束关系可以用有向无圈图(Directed Acyclic Graph，DAG)来刻画，称为序约束图。没有序约束的流水作业排序可视为序约束图为空图的特殊情形，其中三台机流水作业排序问题是强NP-难的[1]，从而有序约束的对应问题F3|prec|Cmax也是强NP-难的。当考虑单位工件时，常数台(m≥3)机器流水作业排序问题Fm|prec,pij=1|Cmax的计算复杂性仍是一个尚未解决的公开难题[2](两台机情形是多项式时间可解的[3])。当机器台数作为输入时，F|prec,pij=1|Cmax问题是强NP-难的[4]。如果序约束图具有某些特殊结构，比如当序约束图为树时，即使机器台数作为输入，流水作业排序问题F|tree,pij=1|Cmax也是多项式时间可解的[3]。文献[5]在研究有序约束的开放作业排序问题时引入了一类新型序约束图，该图中所有顶点(即工件)均包含于某条最长链上，它是不同于树的特殊序约束结构，本文称之为最长链图(Longest Chains Graph，LCG)。LCG的发现对设计开放作业排序问题的近似算法起到重要作用。本文研究单位工件、有LCG型序约束的三台机流水作业排序问题F3|LCG,pij=1|Cmax，设计了一个最坏情况界是3/2的近似算法。

1 最优排序结构与最优值估计

令图G=(J,A)为给定的LCG，其中J={J1,J2,…,Jn}为顶点集，A为有向边集。若(Jj,Jk)∈A，则表示工件Jj,Jk之间有序约束关系JjJk。假设工件Jj在机器Mi上的开工时间为sij。对于单位工件、有序约束的三台流水作业排序问题，其最优排序具有以下性质。

性质1单位工件、有序约束的三台机流水作业最优排序为：使得每个工件的三道工序可以进行无等待加工，即对任意工件Jj，有si+1,j=sij+1。

证明用数学归纳法证明。假设工件在机器M1上的加工顺序为J1,J2,…,Jn，机器M1上可以存在空闲，机器M1的开工时刻为0时刻。

首先证明工件J1满足性质1。s11=0时，假设最优排序中工件J1在机器M2上的开工时间s21≠1，此时，机器M2上的1至2时刻无工件加工。同时考虑机器M1上1至2时刻的工件加工情况，当M1上1至2时刻为空闲时，工件J1在机器M2上的1时刻开工不会与M1上加工的工件冲突；当机器M1上1至2时刻加工的工件为J2时，工件J1与J2无序约束关系；同样，工件J1可以在机器M2上的1时刻开工，与假设s21≠1矛盾，即最优排序s21=1。同理可证s31=2。所以，工件J1可以进行无等待加工。

假设前k个工件J1,J2,…,Jk满足性质1，下面证明工件Jk+1满足性质1。设工件Jk+1在机器M1上的开工时刻为k+1，且最优排序有s2,k+1≠k+2，则机器M2上k+2至k+3时刻无工件加工。同理可得机器M1上的k+2至k+3时刻无工件加工或者加工的工件为Jk+2时，都有工件Jk+1可以在机器M2上的时刻k+2开工。与假设s2，k+1≠k+2矛盾，所以最优排序s2，k+1=k+2。同理可证s3,k+1=k+3。所以，工件Jk+1可以进行无等待加工。

综上所述，当机器M1加工工件顺序为J1,J2,…,Jn时，由si+1,j=sij+1且s11=0，可知机器M2和M3的开工时刻分别为1时刻和2时刻，并且机器M2和M3按照相同的顺序加工工件，因此，当机器M1上加工的工件Ji前存在空闲时，机器M2和M3上工件Ji之前存在同样的空闲，结论成立。证毕。

在算法设计和分析之前，首先需要对LCG进行自然分层。具体步骤为：将所有当前可加工的工件(序约束图入度为0的顶点)分为一层，删去已分层的工件并更新LCG，对剩余的子图重复操作，直至所有工件分层完毕。如果工件满足J1J3，J3J2时，仍有J1J2，称有向边(J1,J2)为多余边，分层完成后，将LCG中的多余边删除。假设自然分层将LCG分为l层，每一层构成一个工件集合，得到工件集的划分：D1,D2,…,Dl。自然分层的实例如图1所示，将LCG共分为l层，每一层的工件用虚线圈出，多余边为虚线所示的有向边。

图1 LCG的自然分层

2 近似算法设计与最坏情况分析

任一顶点集Di中的工件相互之间无序约束关系，因此按D1,D2,…,Dl顺序最优安排各顶点集中的工件并在相邻顶点集之间空闲2个单位时间，所得排序一定为可行排序，但相应的最大工件完工时间Cmax较大。

本文提出的改进算法就是在保证算法解可行的情况下，将相邻顶点集之间的空隙缩减至1个单位时间。为此，需要为相邻顶点集尽可能寻找一组相容的工件对，作为相邻顶点集的邻接工件，相容的定义如下：

定义1假设工件Jα∈Di，工件Jβ∈Di+1，当工件Jα与Jβ之间无序约束关系时，工件对Jα与Jβ称为相邻顶点集Di与Di+1的相容工件对。工件Jα与工件Jβ的关系称为相容。

问题F3|LCG,pij=1|Cmax的近似算法具体步骤如下。

输入：一个LCGG=(V,E)

输出：图G中顶点(工件)的一个可行排序

(1)将LCG自然分层，得到各层顶点集D1,D2,…,Dl；

(2)寻找Di与Di+1(i=1,2,…,l-1)的相容工件对(同一工件至多与一个顶点集的某工件组成相容工件对)；

(3)按D1,D2,…,Dl顺序最优安排顶点集的工件，如果相邻顶点集找到相容工件对，则将相容工件对作为两顶点集的邻接工件，并在相邻顶点集之间空闲1个单位时间。否则相邻顶点集之间空闲2个单位时间。

下面分析算法的最坏情况界。

算法在顶点集Di与Di+1之间无法找到相容工件对时，算法在顶点集Di的全部工件加工完毕后空闲2个单位时间。此时顶点集Di与下层顶点集Di+1的结构有以下两种情况：

情况2顶点集Di与下层顶点集Di+1之间不为完全二部图。假设满足条件的顶点集共有k个，则有如下定理：

定理2算法的最坏情况界至多为3/2，且是紧的。

根据定理1的结论，可得：

图2 算法的紧例

3 结束语

针对单位工件、有最长链图型序约束的三台机流水作业排序问题，本文通过对序约束图自然分层并为相邻顶点集寻找相容工件对的方法设计了多项式时间近似算法，证明了算法的最坏情况界为3/2，同时给出紧例。由于算法仅通过相邻顶点集的结构来确定相容工件对，存在寻找相容工件对效率不高的问题，后续将改进寻找方法，得到更好的下界。