带精确时间延迟的两台机流水作业问题研究

王焕男

(三亚学院理工学院，海南 三亚 572022)

1 引言

关于带精确时间延迟的两台机流水作业问题主要成果有：文献[1](Ageev and Kononov，2006)对于问题F2| exactlj|Cmax设计1个3的近似算法，1.5-ε的难近似界，O(nlogn)时间内可解；对于问题F2|exactlj,aj≤bj|Cmax设计1个2的近似算法，1.5-ε的难近似界，O(nlogn)时间内可解；对于问题F2|exactlj,aj≥bj|Cmax设计1个2的近似算法，1.5-ε的难近似界，O(nlogn)时间内可解。文献[1](Ageev and Kononov，2006)和[2](Ageev and Kononov，2007)对一般情况也设计了更好的近似算法，他们进一步证明了(1.5-ε)-近似算法的存在性，暗示P=NP。文献 [2](Ageev and Baburin，2007)假设在单位加工时间下，证明了对于问题F2|exactlj,aj=bj= 1 |Cmax的近似因子是3/2，证明两台机的算法可以在O(n2logn)时间内实现。文献[3](Yu，1996)证明这个问题是强NP-难的。文献[4](Josh Glascock，Brian Hunter，2009)开发了基于遗传算法(GA)和蚁群优化(ACO)的两个元启发式算法。文献[5](Yumei Huo，HaibingLi，HairongZha，2009)研究带确切延误的两台机流水作业的排列排序，注意到甚至对于排列排序，这个问题仍然是强NP-难的，证明了对于一些特殊情况一些简单的算法能用于找到最优排序。他们设计了第1个元启发式算法，1个禁忌搜索算法和1个模拟退火算法解决这个问题。研究带确切延误的两台机流水作业的排列排序最小化总完工时间。对于一般情况，这个问题是NP-难的。研究多项式可解的特殊例子，对于一般情况开发了一些简单启发式算法和共通启发式演算法。

对上述研究综述进行汇总如表1所示。

而本研究主要研究带精确时间延迟的两台机流水作业问题。每个工件Jj(j=1,2,…,n)有两道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工时间caj与第二道工序的开始时间sbj之间存在一个精确时间延迟exactlj，即sbj=caj+lj。所有工序操作时间都相等aj=bj=a(j=1,2,…,n)，且精确时间延迟是工序操作时间的整数倍lj=ka(k∈N+)。第一道工序在第一台机器上执行，第二道工序在第二台机器上执行，分别以极小化加权总完工时间，最大延误时间和总延误数为目标函数，设计了最优算法。

表1 带精确时间延迟的两台机流水作业Tab.1 Flow operation of two machines with accurate time delay

上面问题用三参数分别表示为：F2|exactlj,aj=bj=a,lj=ka|∑wjCj，F2|exactlj,aj=bj=a,lj=ka|Lmax，F2|exactlj,aj=bj=a,lj=ka|∑Uj这3个问题。

2 F2|exact lj,aj=bj,lj=ka|∑wjCj的最优算法

本节主要研究带精确时间延迟的两台机流水作业排序问题。每个工件记为Jj(aj,bj,lj,wj)，目标函数为极小化加权总完工时间。分别考虑以下3种情况：

2.1 F2|exact lj,aj=bj=lj=a|∑wjCj的最优算法

当aj=bj=lj=a时，sb1=2a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖∑wjCj。考虑单台机排序问题1‖∑wjCj，该问题存在多项式时间最优算法，Weighted Shortest Processing Time first (WSPT)，即

LWF (Longest Weighted first):将所有工件重新排序，使得w1≥w2≥…≥wn，再按照J1,J2,…,Jn的顺序加工工件。

定理2.1.1 LWF是问题F2|exactlj,aj=bj=lj=a|∑wjCj的最优算法，如图1所示。

证明：用反证法。假设有一个最优排序，比如σ*，违反了LWF规则，则σ*中一定存在相邻的两个工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(sbi+bi)+wk(sbi+bi+bk)-wi(sbi+bi+bk)-wk(sbi+bk)=wkpi-wipk>0

即所得的排序σ目标值比最优值还要小，矛盾！

注：当wj=1时，问题变为1|exactlj,aj=bj=lj=a|∑Cj

图1 最优排序Fig.1 Optimal sorting

2.2 F2|exact lj,aj=bj,lj=2a|∑wjCj的最优算法

当aj=bj=a,lj=2a时，sb1=3a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖∑wjCj。考虑单台机排序问题1‖∑wjCj，该问题存在多项式时间最优算法，Weighted Shortest Processing Time first (WSPT)，即

定理2.2.1 LWF是问题F2|exactlj,aj=bj=lj=2a|∑wjCj的最优算法，如图2所示。

图2 最优排序Fig.2 Optimal sorting

证明：用反证法。假设有一个最优排序，比如σ*，违反了LWF规则，则σ*中一定存在相邻的两个工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(sbi+bi)+wk(sbi+bi+bk)-wi(sbi+bi+bk)-wk(sbi+bk)=wkpi-wipk>0

即所得的排序σ目标值比最优值还要小，矛盾！

J1,J2,…,Jn的顺序加工工件。

注：当wj=1时，问题变为1|exactlj,aj=bj=a,lj=2a|∑Cj

2.3 F2|exact lj,aj=bj,lj=ka|∑wjCj的最优算法

定理2.3.1 LWF是问题F2|exactlj,aj=bj,lj=ka|∑wjCj的最优算法，如图3所示。

图3 最优排序Fig.3 Optimal sorting

证明：用反证法。假设有一个最优排序，比如σ*，违反了LWF规则，则σ*中一定存在相邻的两个工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(sbi+bi)+wk(sbi+bi+bk)-wi(sbi+bi+bk)-wk(sbi+bk)=wkpi-wipk>0

即所得的排序σ目标值比最优值还要小，矛盾！

J1,J2,…,Jn的顺序加工工件。

注：当wj=1时，问题变为1|exactlj,aj=bj=a,lj=ka|∑Cj

3 F2|exact lj,aj=bj,lj=ka|Lmax的最优算法

本节主要研究带确切延误的两台机流水作业排序问题。每个工件记为Jj(aj,bj,lj,dj)，目标函数为极小化最大延误。分别考虑以下3种情况：

3.1 F2|exact lj,aj=bj=lj=a|Lmax的最优算法

当aj=bj=lj=a时，sb1=2a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖Lmax。单台机最大延误问题1‖Lmax也可以找到多项式时间算法，Earliest Due Date first (EDD)，且是最优算法。

EDD：将工件重新排序使得d1≤d2≤…≤dn，再按照J1,J2,…,Jn顺序加工。

定理3.1.1 EDD规则可以得到问题F2|exactlj,aj=bj=lj=a|Lmax的最优排序。

3.2 F2|exact lj,aj=bj,lj=2a|Lmax的最优算法

当aj=bj=a,lj=2a时，sb1=3a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖Lmax。单台机最大延误问题1‖Lmax也可以找到多项式时间算法，Earliest Due Date first (EDD)，且是最优算法。

定理3.2.1 EDD规则可以得到问题F2|exactlj,aj=bj,lj=2a|Lmax的最优排序。

3.3 F2|exact lj,aj=bj,lj=ka|Lmax的最优算法

当aj=bj=a,lj=ka时，sb1=(k+1)a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖Lmax。单台机最大延误问题1‖Lmax也可以找到多项式时间算法，Earliest Due Date first (EDD)，且是最优算法.

定理3.3.1 EDD规则可以得到问题F2|exactlj,aj=bj,lj=ka|Lmax的最优排序。

4 F2|exact lj,aj=bj,lj=ka|∑Uj的最优算法

本节主要研究带精确时间延迟的两台机流水作业排序问题，每个工件记为Jj(aj,bj,lj,dj)，目标函数为极小化总延误数。分别考虑以下3种情况：

4.1 F2|exact lj,aj=bj=lj=a|∑Uj的最优算法

当aj=bj=lj=a时，sb1=2a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖∑Uj。对于极小化误工工件数的问题1‖∑Uj，1968年Moore给出了一个多项式时间的最优算法。

算法H:

①将工件按照EDD规则排序；

②计算当前排序中各工件的完工时间，如果已无延误，则转④，否则转③；

③找出第1个延误的工件，比如是第i个工件，则将其删除，得到一个部分排序，返回②；

④将删除的工件以任意顺序排到最后，所得部分排序之后，输出所得排序。

定理4.1.1 算法H可以得到问题F2|exactlj,aj=bj=lj=a|Lmax的最优排序如图4所示。

图4 最优排序Fig.4 Optimal sorting

证明：不妨d1≤d2≤…≤dn，设P=(S,F)为算法所得的排序，其中S为按期完工工件集，F为误工工件集，即算法在第③步中删除的工件集合。不妨设F≠Φ，令工件k是算法第1次执行到第③步时找到的延误工件，于是i就是算法删除的第1个工件。由算法规则可知 1,…,i-1没有误工工件，下面首先证明：存在最优排序P′=(S′,F′)(S′和F′定义同上)，使得i∈F′。

设P′=(S′,F′)是一个最优排序且i∈S′。并记F′=π(r+1)…π(n)，S′=π(1)…π(r)，不妨认为dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得：

i∈{π(1),…,π(m)}⊆{1,…,i}，{π(m+1),…,π(r)}⊆{i+1,…,n}。

并且由i定义，序列1,…,i产生延误，因而{π(1),…,π(m)}≠{1,…,i}。于是存在1≤h≤i，h∉{π(1),…,π(m)}，所以有：

{π(1),…,π(m)}∪{h}{i}⊆{1,…,k}{i}。

由此可知：{π(1),…,π(m)}∪{h}{i}按照EDD排列后不产生延误，且这些工件的总加工时间比{π(1),…,π(m)}中工件总加工时间减少了，这表明在上述工件序列之后加上原来的π(m+1),…,π(r)也不产生误工工件。换句话说，我们构造出了一个误工工件数与P′相同但i是误工工件的排序，即得到了满足要求的最优排序。

根据上面这个结论，对工件数目作归纳，证明定理结论：显然，当n=1时，该算法可以得到最优排序。假设算法对工件数为n-1的实例均能找到最优排序，则对任一工件数为n的实例，设P=(S,F)是算法所得的排序，工件i∈F如上定义。所以存在一个最优排序P′=(S′,F′)，使得i∈F′，显然有|S|≤|S′|。另一方面，考虑实例{1,…,i-1,i+1,…,n}，由归纳假设及算法规则，算法得到的排序形如P=(S,F{i})且是一个最优排序。再注意到P′=(S′,F′{i})是该实例的可行排序，所以又可得到|S|≥|S′|。因此|S|=|S′|，算法对n个工件的实例也得到最优排序。

4.2 F2|exact lj,aj=bj,lj=2a|∑Uj的最优算法

当aj=bj=a,lj=2a时，sb1=3a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖∑Uj。对于极小化误工工件数的问题1‖∑Uj，1968年Moore给出了一个多项式时间的最优算法。

定理4.2.1 算法H可以得到问题F2|exactlj,aj=bj,lj=2a|∑Uj的最优排序如图5所示。

图5 最优排序Fig.5 Optimal sorting

证明：不妨d1≤d2≤…≤dn，设P=(S,F)为算法所得的排序，其中S为按期完工工件集，F为误工工件集，即算法在第③步中删除的工件集合。不妨设F≠Φ，令工件k是算法第1次执行到第③步时找到的延误工件，于是i就是算法删除的第1个工件。由算法规则可知 1,…,i-1没有误工工件，下面首先证明：存在最优排序P′=(S′,F′)(S′和F′定义同上)，使得i∈F′。

设P′=(S′,F′)是一个最优排序且i∈S′。并记F′=π(r+1)…π(n)，S′=π(1)…π(r)，不妨认为dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得：

i∈{π(1),…,π(m)}⊆{1,…,i}，{π(m+1),…,π(r)}⊆{i+1,…,n}。并且由i定义，序列1,…,i产生延误，因而{π(1),…,π(m)}≠{1,…,i}。于是存在1≤h≤i，h∉{π(1),…,π(m)}，所以有：

{π(1),…,π(m)}∪{h}{i}⊆{1,…,k}{i}。

由此可知{π(1),…,π(m)}∪{h}{i}按照EDD排列后不产生延误，且这些工件的总加工时间比{π(1),…,π(m)}中工件总加工时间减少了，这表明在上述工件序列之后加上原来的π(m+1),…,π(r)也不产生误工工件。换句话说，我们构造出了一个误工工件数与P′相同但i是误工工件的排序，即得到了满足要求的最优排序。

根据上面这个结论，对工件数目作归纳，证明定理结论：显然当n=1时，该算法可以得到最优排序。假设算法对工件数为n-1的实例均能找到最优排序，则对任一工件数为n的实例，设P=(S,F)是算法所得的排序，工件i∈F如上定义。所以存在一个最优排序P′=(S′,F′)，使得i∈F′，显然有|S|≤|S′|。另一方面，考虑实例{1,…,i-1,i+1,…,n}，由归纳假设及算法规则，算法得到的排序形如P=(S,F{i})且是一个最优排序。再注意到P′=(S′,F′{i})是该实例的可行排序，所以又可得到|S|≥|S′|。因此|S|=|S′|，算法对n个工件的实例也得到最优排序。

4.3 F2|exact lj,aj=bj,lj=ka|∑Uj的最优算法

当aj=bj=a,lj=ka时，sb1=(k+1)a。因为每个工件的第一道工序aj在第一台机器上执行，第二道工序bj在第二台机器上执行，并且它们之间存在的是精确时间延迟，所以当第二道工序bj在第二台机器上的开始时间sbj确定时，对应的第一道工序aj在第一台机器的位置也唯一确定。因此只考虑每个工件的第二道工序bj，即此问题等价于1‖∑Uj。对于极小化误工工件数的问题1‖∑Uj，1968年Moore给出了一个多项式时间的最优算法。

定理4.3.1 算法H可以得到问题F2|exactlj,aj=bj,lj=ka|∑Uj的最优排序如图6所示。

图6 最优排序Fig.6 Optimal sorting

证明：不妨d1≤d2≤…≤dn，设P=(S,F)为算法所得的排序，其中S为按期完工工件集，F为误工工件集，即算法在第③步中删除的工件集合。不妨设F≠Φ，令工件k是算法第1次执行到第③步时找到的延误工件，于是i就是算法删除的第1个工件。由算法规则可知 1,…,i-1没有误工工件，下面首先证明：存在最优排序P′=(S′,F′)(S′和F′定义同上)，使得i∈F′。

设P′=(S′,F′)是一个最优排序且i∈S′，并记F′=π(r+1)…π(n)，S′=π(1)…π(r)。不妨认为dπ(1)≤dπ(2)≤…≤dπ(r)，再由于d1≤d2≤…≤dn，所以一定存在m使得：

i∈{π(1),…,π(m)}⊆{1,…,i}，{π(m+1),…,π(r)}⊆{i+1,…,n}。

并且由i定义，序列1,…,i产生延误，因而{π(1),…,π(m)}≠{1,…,i}。于是存在1≤h≤i，h∉{π(1),…,π(m)}，所以有：

{π(1),…,π(m)}∪{h}{i}⊆{1,…,k}{i}。

由此可知{π(1),…,π(m)}∪{h}{i}按照EDD排列后不产生延误，且这些工件的总加工时间比{π(1),…,π(m)}中工件总加工时间减少了，这表明在上述工件序列之后加上原来的π(m+1),…,π(r)也不产生误工工件。换句话说，我们构造出了一个误工工件数与P′相同但i是误工工件的排序，即得到了满足要求的最优排序。

根据上面这个结论，对工件数目作归纳，证明定理结论：显然当n=1时，该算法可以得到最优排序。假设算法对工件数为n-1的实例均能找到最优排序，则对任一工件数为n的实例，设P=(S,F)是算法所得的排序，工件i∈F如上定义。所以存在一个最优排序P′=(S′,F′)，使得i∈F′，显然有|S|≤|S′|。另一方面，考虑实例{1,…,i-1,i+1,…,n}，由归纳假设及算法规则，算法得到的排序形如P=(S,F{i})且是一个最优排序。再注意到P′=(S′,F′{i})是该实例的可行排序，所以又可得到|S|≥|S′|。因此|S|=|S′|，算法对n个工件的实例也得到最优排序。

5 结语

主要研究了带精确时间延迟的两台机流水作业排序问题。第一道工序在第一台机器上执行，第二道工序在第二台机器上执行，分别以极小化加权总完工时间，最大延误时间和总延误数为目标函数，设计了最优算法。

需要进一步研究和考虑的问题还有：

①F2|exactlj|∑wjCj带确切延误的两台机流水作业排序问题，目标是加权总完工时间。

②F2|exactlj|Lmax带确切延误的两台机流水作业排序问题，目标是极小化最大延误时间。

③F2|exactlj|∑Uj带确切延误的两台机流水作业排序问题，目标是总延误数。