帶精確時間延遲的單機排序問題

王煥男

(三亞學院理工學院，海南 三亞 572022)

1 引言

本研究的問題用三參數(shù)分別表示為：1|exactlj,aj=bj=a,lj=ka|∑wjCj，1|exactlj,aj=bj=a,lj=ka|Lmax，1|exactlj,aj=bj=a,lj=ka|∑Uj這3個問題。

關于帶精確時間延遲的單機排序問題主要成果有：文獻[1]對于1|exactlj|Cmax的一種特殊情況提出一個貪婪算法(greedy heuristic)。文獻 [2]對于問題 1|exactlj|Cmax提出一個神經(jīng)網(wǎng)絡算法(Hopfield neural network)。文獻[3]研究最小化雷達的空閑時間，他們制定一個單機排序問題的確切延誤而不是最小化延誤；證明一些特殊的例子是多項式可解的；即使在某些特殊情況下，這個問題仍是強NP-難的；如果所有操作的加工時間相同，這個問題已經(jīng)是強NP-難的。文獻[4]基于離散化的時間跨度問題提出一個拉格朗日松弛算法(Lagrange relaxation algorithm)。文獻[5]對于問題1|exactlj|Cmax設計1個3.5的近似算法，2-ε的難近似界，O(nlogn)時間內(nèi)可解；對于問題 1|exactlj,aj≤bj|Cmax設計一個3的近似算法，2-ε的難近似界，O(nlogn)時間內(nèi)可解；對于問題1|exactlj,aj≥bj|Cmax設計1個3的近似算法，2-ε的難近似界，O(nlogn)時間內(nèi)可解；對于問題 1|exactlj,aj=bj|Cmax設計1個2.5的近似算法，2-ε的難近似界，O(nlogn)時間內(nèi)可解。文獻[6]假設在單位加工時間下，證明了對于問題1|exactlj,aj=bj=1|Cmax的近似因子是 7/4(界不能改進)，并證明單臺機的算法可以在O(nlogn)時間內(nèi)實現(xiàn)，文獻[7]證明這個問題是強NP-難的。

對上述研究綜述進行匯總如表1所示。

表1 帶精確時間延遲的單機排序Tab.1 Single machine scheduling with precise time delay

文章中的符號定義：

aj—工件j的第一道工序加工時間；caj—工件j的第一道工序完工時間；bj—工件j的第二道工序加工時間；pj—工件j的加工時間；Si—工件j的第一道工序開始時間，即工件的開始時間；sbj—工件j的第二道工序開始時間(sbj=cai+lj)；lj—工件j的延誤時間；Lj—工件j的誤工時間；dj—工件j的工期；wj—工件j的權重；Lmax—工件最大延誤時間；Cj—工件j的完工時間；∑Cj—工件總完工時間；wjCj—工件j的加權完工時間；∑wjCj—工件加權總完工時間；Uj—如果Cj≤dj，則Uj= 0，否則，Uj=1；∑Uj—工件的總延誤個數(shù)。

2 1|exact lj,aj=bj=a,lj=ka|∑wjCj的最優(yōu)算法

本節(jié)主要研究帶精確時間延遲的單機排序問題。每個工件記為Jj(aj,bj,lj,wj)，目標函數(shù)為極小化加權總完工時間。分別考慮以下3種情況：

2.1 1|exact lj,aj=bj=lj=a|∑wjCj的最優(yōu)算法

當aj=bj=lj=a時，最優(yōu)排序一定是兩個工件一組，先執(zhí)行兩個第一道工序，再相應執(zhí)行兩個第二道工序。工件個數(shù)是偶數(shù)，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C2n-1=(4n-1)a，C2n=4na(n=1,2,3,…)其中之一。工件的開始時間一定是C2n-1-3a，C2n-3a(n=1,2,3,…)其中之一。

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

定理2.1.1：LWF是問題1|exactlj,aj=bj=lj=a|∑wjCj的最優(yōu)算法，如圖1所示。

圖1 最優(yōu)排序Fig.1 Optimal sorting

證明：用反證法。假設有一個最優(yōu)排序，比如σ*違反了WSPT規(guī)則，則σ*中一定存在相鄰的兩個工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(Si+pi)+wk(Sk+pk)-wi(Sk+pi)-wk(Si+pk)=(wi-wk)(Si-Sk)>0

即：所得的排序σ目標值比最優(yōu)值還要小，矛盾！

注：當wj=1時，問題變?yōu)?|exactlj,aj=bj=lj=a|∑Cj。

2.2 1|exact lj,aj=bj=a,lj=2a|∑wjCj的最優(yōu)算法

當aj=bj=a,lj=2a時，最優(yōu)排序一定是3個工件一組，先執(zhí)行3個第一道工序，再相應執(zhí)行3個第二道工序。工件個數(shù)是3的整數(shù)倍時，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C3n-2=2(3n-1)a，C3n-1=(6n-1)a，C3n=6na其中之一。工件的開始時間一定是C3n-2-4a，C3n-1-4a，C3n-4a其中之一。

定理2.2.1：LWF是問題1|exactlj,aj=bj=a,lj=2a|∑wjCj的最優(yōu)算法，如圖2所示。

圖2 最優(yōu)排序Fig.2 Optimal sorting

證明：用反證法。假設有一個最優(yōu)排序，比如σ*違反了WSPT規(guī)則，則σ*中一定存在相鄰的兩個工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(Si+pi)+wk(Sk+pk)-wi(Sk+pi)-wk(Si+pk)=(wi-wk)(Si-Sk)>0

即：所得的排序σ目標值比最優(yōu)值還要小，矛盾！

注：當wj=1時，問題變?yōu)?|exactlj,aj=bj=a,lj=2a|∑Cj。

2.3 1|exact lj,aj=bj=a,lj=ka|∑wjCj的最優(yōu)算法

當aj=bj=a,lj=ka時，最優(yōu)排序一定是k+1個工件一組，先執(zhí)行k+1個第一道工序，再相應執(zhí)行k+1個第二道工序。工件個數(shù)是k+1的整數(shù)倍時，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C(k+1)n-k=2(k+1)a·(n-1)+(k+2)a，C(k+1)n-(k-1)=2(k+1)a·(n-1)+(k+3)a,…,C(k+1)n=2(k+1)a·n其中之一。工件的開始時間一定是C(k+1)n-k-(k+2)a，C(k+1)n-(k-1)-(k+2)a,…,C(k+1)n-(k+2)a其中之一。

定理2.3.1：LWF是問題1|exactlj,aj=bj=a,lj=ka|∑wjCj的最優(yōu)算法，如圖3所示。

圖3 最優(yōu)排序Fig.3 Optimal sorting

證明：用反證法。假設有一個最優(yōu)排序，比如σ*違反了WSPT規(guī)則，則σ*中一定存在相鄰的兩個工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(Si+pi)+wk(Sk+pk)-wi(Sk+pi)-wk(Si+pk)=(wi-wk)(Si-Sk)>0

即：所得的排序σ目標值比最優(yōu)值還要小，矛盾！

注：當wj=1時，問題變?yōu)?|exactlj,aj=bj=a,lj=ka|∑Cj。

3 1|exact lj,aj=bj=a,lj=ka|Lmax的最優(yōu)算法

本節(jié)主要研究帶精確時間延遲的單機排序問題。每個工件記為Jj(aj,bj,lj,dj)，目標函數(shù)為極小化最大延誤時間。分別考慮以下3種情況：

3.1 1|exact lj,aj=bj=lj=a|Lmax的最優(yōu)算法

當aj=bj=lj=a時，最優(yōu)排序一定是兩個工件一組，先執(zhí)行兩個第一道工序，再相應執(zhí)行兩個第二道工序。工件個數(shù)是偶數(shù)，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C2n-1=(4n-1)a，C2n=4na(n=1,2,3,…)其中之一。工件的開始時間一定是C2n-1-3a，C2n-3a(n=1,2,3,…)其中之一。

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

定理3.1.1：EDD規(guī)則可以得到問題1|exactlj,aj=bj=lj=a|Lmax的最優(yōu)排序。

3.2 1|exact lj,aj=bj=a,lj=2a|Lmax的最優(yōu)算法

當aj=bj=a,lj=2a時， 最優(yōu)排序一定是3個工件一組，先執(zhí)行3個第一道工序，再相應執(zhí)行3個第二道工序。工件個數(shù)是3的整數(shù)倍時，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C3n-2=2(3n-1)a，C3n-1=(6n-1)a，C3n=6na其中之一。工件的開始時間一定是C3n-2-4a，C3n-1-4a，C3n-4a其中之一。

定理3.2.1：EDD規(guī)則可以得到問題1|exactlj,aj=bj=a,lj=2a|Lmax的最優(yōu)排序。

3.3 1|exact lj,aj=bj=a,lj=ka|Lmax的最優(yōu)算法

當aj=bj=a,lj=ka時，最優(yōu)排序一定是k+1個工件一組，先執(zhí)行k+1個第一道工序，再相應執(zhí)行k+1個第二道工序。工件個數(shù)是k+1的整數(shù)倍時，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C(k+1)n-k=2(k+1)a·(n-1)+(k+2)a，C(k+1)n-(k-1)=2(k+1)a·(n-1)+(k+3)a,…,C(k+1)n=2(k+1)a·n其中之一。工件的開始時間一定是C(k+1)n-k-(k+2)a，C(k+1)n-(k-1)-(k+2)a,…,C(k+1)n-(k+2)a其中之一。

定理3.3.1：EDD規(guī)則可以得到問題1|exactlj,aj=bj=a,lj=ka|Lmax的最優(yōu)排序。

4 1|exact lj,aj=bj=a,lj=ka|∑Uj的最優(yōu)算法

本節(jié)主要研究帶精確時間延遲的單機排序問題。每個工件記為Jj(aj,bj,lj,dj)，目標函數(shù)為極小化工件總延誤個數(shù)。分別考慮以下3種情況：

4.1 1|exact lj,aj=bj=lj=a|∑Uj的最優(yōu)算法

當aj=bj=lj=a時，最優(yōu)排序一定是兩個工件一組，先執(zhí)行兩個第一道工序，再相應執(zhí)行兩個第二道工序。工件個數(shù)是偶數(shù)，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C2n-1=(4n-1)a，C2n=4na(n=1,2,3,…)其中之一。工件的開始時間一定是C2n-1-3a，C2n-3a(n=1,2,3,…)其中之一。

引理4.1.1：工件集存在不誤工的排序且僅當EDD序不誤工。

算法H：(1)將工件按照EDD規(guī)則排序。(2)計算當前排序中各工件的完工時間，如果已無延誤則轉(4)，否則轉(3)。(3)找出第一個延誤的工件，比如是第i個工件，則將其刪除，得到一個部分排序，返回(2)。(4)將刪除的工件以任意順序排到最后，所得部分排序之后，輸出所得排序。

定理4.1.1：算法H可以得到問題1|exactlj,aj=bj=lj=a|∑Uj的最優(yōu)排序如圖4所示。

圖4 最優(yōu)排序Fig.4 Optimal sorting

證明：不妨d1≤d2≤…≤dn。設P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第(3)步中刪除的工件集合。不妨設F≠Φ，令工件i是算法第一次執(zhí)行到第(3)步時找到的延誤工件，于是i就是算法刪除的第1個工件，由算法規(guī)則可知 1, …,i-1沒有誤工工件。下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。設P′=(S′,F′)是一個最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，注意到引理4.1.1，不妨認為dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得

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

并且由i定義，序列1, …,i產(chǎn)生延誤，因而{π(1), …,π(m)}≠{1, … ,i}。于是存在1≤h≤i，h?{π(1), …,π(m)}，所以有：

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

由此可知，{π(1), …,π(m)}∪{h}{i}按照EDD排列后不產(chǎn)生延誤，且這些工件的總加工時間比{π(1), …,π(m)}中工件總加工時間減少了，這表明在上述工件序列之后加上原來的π(m+1), …,π(r)也不產(chǎn)生誤工工件。換句話說，我們構造出了一個誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

根據(jù)上面結論，對工件數(shù)目作歸納，證明定理結論：

顯然，當n=1時，該算法可以得到最優(yōu)排序。假設算法對工件數(shù)為n-1的實例均能找到最優(yōu)排序，則對任一工件數(shù)為n的實例，設P=(S,F)是算法所得的排序，工件i∈F如上定義。所以存在一個最優(yōu)排序P′=(S′,F′)，使得i∈F′，顯然有|S|≤|S′|。另一方面，考慮實例{1, …,i-1,i+1, …,n}，由歸納假設及算法規(guī)則，算法得到的排序形如P=(S,F{i})且是一個最優(yōu)排序；再注意到P′=(S′,F′{i})是該實例的可行排序，所以又可以得到|S|≥|S′|。因此|S|=|S′|，算法對n個工件的實例也得到最優(yōu)排序。

4.2 1|exact lj,aj=bj=a,lj=2a|∑Uj的最優(yōu)算法

當aj=bj=a,lj=2a時，最優(yōu)排序一定是3個工件一組，先執(zhí)行3個第一道工序，再相應執(zhí)行3個第二道工序。工件個數(shù)是3的整數(shù)倍時，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C3n-2=2(3n-1)a，C3n-1=(6n-1)a，C3n=6na其中之一。工件的開始時間一定是C3n-2-4a，C3n-1-4a，C3n-4a其中之一。

定理4.2.1：算法H可以得到問題1|exactlj,aj=bj=a,lj=2a|∑Uj的最優(yōu)排序如圖5所示。

圖5 最優(yōu)排序Fig.5 Optimal sorting

證明：不妨d1≤d2≤…≤dn。設P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第(3)步中刪除的工件集合。不妨設F≠Φ，令工件k是算法第一次執(zhí)行到第(3)步時找到的延誤工件，于是i就是算法刪除的第1個工件，由算法規(guī)則可知 1, …,i-1沒有誤工工件。下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。設P′=(S′,F′)是一個最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，注意到引理4.1.1，不妨認為dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得

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

并且由i定義，序列1, …,i產(chǎn)生延誤，因而{π(1), …,π(m)}≠{1, … ,i}。于是存在1≤h≤i，h?{π(1), …,π(m)}，所以有：

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

由此可知，{π(1), …,π(m)}∪{h}{i}按照EDD排列后不產(chǎn)生延誤，且這些工件的總加工時間比{π(1), …,π(m)}中工件總加工時間減少了，這表明在上述工件序列之后加上原來的π(m+1), …,π(r)也不產(chǎn)生誤工工件。換句話說，我們構造出了一個誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

根據(jù)上面這個結論，對工件數(shù)目作歸納，證明定理結論：

顯然，當n=1時，該算法可以得到最優(yōu)排序。假設算法對工件數(shù)為n-1的實例均能找到最優(yōu)排序，則對任一工件數(shù)為n的實例，設P=(S,F)是算法所得的排序，工件i∈F如上定義。所以存在一個最優(yōu)排序P′=(S′,F′)，使得i∈F′，顯然有|S|≤|S′|。另一方面，考慮實例{1, …,i-1,i+1, …,n}，由歸納假設及算法規(guī)則，算法得到的排序形如P=(S,F{i})且是一個最優(yōu)排序；再注意到P′=(S′,F′{i})是該實例的可行排序，所以又可以得到|S|≥|S′|。因此|S|=|S′|，算法對n個工件的實例也得到最優(yōu)排序。

4.3 1|exact lj,aj=bj=a,lj=ka|∑Uj的最優(yōu)算法

當aj=bj=a,lj=ka時，最優(yōu)排序一定是k+1個工件一組，先執(zhí)行k+1個第一道工序，再相應執(zhí)行k+1個第二道工序。工件個數(shù)是k+1的整數(shù)倍時，機器沒有空閑，否則機器存在空閑。工件的完工時間一定是C(k+1)n-k=2(k+1)a·(n-1)+(k+2)a，C(k+1)n-(k-1)=2(k+1)a·(n-1)+(k+3)a,…,C(k+1)n=2(k+1)a·n其中之一。工件的開始時間一定是C(k+1)n-k-(k+2)a，C(k+1)n-(k-1)-(k+2)a,…,C(k+1)n-(k+2)a其中之一。

定理4.3.1：算法H可以得到問題1|exactlj,aj=bj=a,lj=ka|∑Uj的最優(yōu)排序如圖6所示。

圖6 最優(yōu)排序Fig.6 Optimal sorting

證明：不妨d1≤d2≤…≤dn。設P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第(3)步中刪除的工件集合。不妨設F≠Φ，令工件k是算法第一次執(zhí)行到第(3)步時找到的延誤工件，于是i就是算法刪除的第1個工件，由算法規(guī)則可知 1, …,i-1沒有誤工工件。下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。設P′=(S′,F′)是一個最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，注意到引理4.1.1，不妨認為dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得

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

并且由i定義，序列1, …,i產(chǎn)生延誤，因而{π(1), …,π(m)}≠{1, … ,i}。于是存在1≤h≤i，h?{π(1), …,π(m)}，所以有：

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

由此可知，{π(1), …,π(m)}∪{h}{i}按照EDD排列后不產(chǎn)生延誤，且這些工件的總加工時間比{π(1), …,π(m)}中工件總加工時間減少了，這表明在上述工件序列之后加上原來的π(m+1), …,π(r)也不產(chǎn)生誤工工件，換句話說，我們構造出了一個誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

根據(jù)上面這個結論，對工件數(shù)目作歸納，證明定理結論：

顯然當n=1時，該算法可以得到最優(yōu)排序。假設算法對工件數(shù)為n-1的實例均能找到最優(yōu)排序，則對任一工件數(shù)為n的實例，設P=(S,F)是算法所得的排序，工件i∈F如上定義。所以存在一個最優(yōu)排序P′=(S′,F′)，使得i∈F′，顯然有|S|≤|S′|。另一方面，考慮實例{1, …,i-1,i+1, …,n}，由歸納假設及算法規(guī)則，算法得到的排序形如P=(S,F{i})且是一個最優(yōu)排序；再注意到P′=(S′,F′{i})是該實例的可行排序，所以又可以得到|S|≥|S′|。因此|S|=|S′|，算法對n個工件的實例也得到最優(yōu)排序。

5 結語

主要研究了帶精確時間延遲的單機排序問題。每個工件Jj(j=1,2,…,n)有兩道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工時間caj與第二道工序的開始時間sbj之間存在一個確切延誤時間exactlj，即sbj=caj+lj。所有工序操作時間都相等aj=bj=a(j=1,2,…,n)，且確切延誤時間是工序操作時間的整數(shù)倍lj=ka(k∈N+ )。所有工序在一臺機器上執(zhí)行。分別以極小化加權總完工時間，最大延誤和總延誤數(shù)為目標函數(shù)，設計了最優(yōu)算法。

需要進一步研究和考慮的問題還有：

(1)1|exactlj|∑wjCj帶確切延誤的單機排序問題，目標是加權總完工時間。

(2)1|exactlj|Lmax帶確切延誤的單機排序問題，目標是極小化最大延誤時間。

(3)1|exactlj|∑Uj帶確切延誤的單機排序問題，目標是總延誤數(shù)。