王煥男

(三亞學(xué)院理工學(xué)院，海南 三亞 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個(gè)問題。

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

對上述研究綜述進(jìn)行匯總?cè)绫?所示。

表1 帶精確時(shí)間延遲的單機(jī)排序Tab.1 Single machine scheduling with precise time delay

文章中的符號定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)aj=bj=a,lj=ka時(shí)，最優(yōu)排序一定是k+1個(gè)工件一組，先執(zhí)行k+1個(gè)第一道工序，再相應(yīng)執(zhí)行k+1個(gè)第二道工序。工件個(gè)數(shù)是k+1的整數(shù)倍時(shí)，機(jī)器沒有空閑，否則機(jī)器存在空閑。工件的完工時(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其中之一。工件的開始時(shí)間一定是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

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

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

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

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

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

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

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

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

EDD：將工件重新排序使得d1≤d2≤…≤dn，再按照J(rèn)1,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)算法

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

當(dāng)aj=bj=a,lj=ka時(shí)，最優(yōu)排序一定是k+1個(gè)工件一組，先執(zhí)行k+1個(gè)第一道工序，再相應(yīng)執(zhí)行k+1個(gè)第二道工序。工件個(gè)數(shù)是k+1的整數(shù)倍時(shí)，機(jī)器沒有空閑，否則機(jī)器存在空閑。工件的完工時(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其中之一。工件的開始時(shí)間一定是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é)主要研究帶精確時(shí)間延遲的單機(jī)排序問題。每個(gè)工件記為Jj(aj,bj,lj,dj)，目標(biāo)函數(shù)為極小化工件總延誤個(gè)數(shù)。分別考慮以下3種情況：

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

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

引理4.1.1：工件集存在不誤工的排序且僅當(dāng)EDD序不誤工。

算法H：(1)將工件按照EDD規(guī)則排序。(2)計(jì)算當(dāng)前排序中各工件的完工時(shí)間，如果已無延誤則轉(zhuǎn)(4)，否則轉(zhuǎn)(3)。(3)找出第一個(gè)延誤的工件，比如是第i個(gè)工件，則將其刪除，得到一個(gè)部分排序，返回(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。設(shè)P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第(3)步中刪除的工件集合。不妨設(shè)F≠Φ，令工件i是算法第一次執(zhí)行到第(3)步時(shí)找到的延誤工件，于是i就是算法刪除的第1個(gè)工件，由算法規(guī)則可知 1, …,i-1沒有誤工工件。下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。設(shè)P′=(S′,F′)是一個(gè)最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，注意到引理4.1.1，不妨認(rèn)為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)生延誤，且這些工件的總加工時(shí)間比{π(1), …,π(m)}中工件總加工時(shí)間減少了，這表明在上述工件序列之后加上原來的π(m+1), …,π(r)也不產(chǎn)生誤工工件。換句話說，我們構(gòu)造出了一個(gè)誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

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

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

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

當(dāng)aj=bj=a,lj=2a時(shí)，最優(yōu)排序一定是3個(gè)工件一組，先執(zhí)行3個(gè)第一道工序，再相應(yīng)執(zhí)行3個(gè)第二道工序。工件個(gè)數(shù)是3的整數(shù)倍時(shí)，機(jī)器沒有空閑，否則機(jī)器存在空閑。工件的完工時(shí)間一定是C3n-2=2(3n-1)a，C3n-1=(6n-1)a，C3n=6na其中之一。工件的開始時(shí)間一定是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。設(shè)P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第(3)步中刪除的工件集合。不妨設(shè)F≠Φ，令工件k是算法第一次執(zhí)行到第(3)步時(shí)找到的延誤工件，于是i就是算法刪除的第1個(gè)工件，由算法規(guī)則可知 1, …,i-1沒有誤工工件。下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。設(shè)P′=(S′,F′)是一個(gè)最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，注意到引理4.1.1，不妨認(rèn)為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)生延誤，且這些工件的總加工時(shí)間比{π(1), …,π(m)}中工件總加工時(shí)間減少了，這表明在上述工件序列之后加上原來的π(m+1), …,π(r)也不產(chǎn)生誤工工件。換句話說，我們構(gòu)造出了一個(gè)誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

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

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

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

當(dāng)aj=bj=a,lj=ka時(shí)，最優(yōu)排序一定是k+1個(gè)工件一組，先執(zhí)行k+1個(gè)第一道工序，再相應(yīng)執(zhí)行k+1個(gè)第二道工序。工件個(gè)數(shù)是k+1的整數(shù)倍時(shí)，機(jī)器沒有空閑，否則機(jī)器存在空閑。工件的完工時(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其中之一。工件的開始時(shí)間一定是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。設(shè)P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第(3)步中刪除的工件集合。不妨設(shè)F≠Φ，令工件k是算法第一次執(zhí)行到第(3)步時(shí)找到的延誤工件，于是i就是算法刪除的第1個(gè)工件，由算法規(guī)則可知 1, …,i-1沒有誤工工件。下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。設(shè)P′=(S′,F′)是一個(gè)最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，注意到引理4.1.1，不妨認(rèn)為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)生延誤，且這些工件的總加工時(shí)間比{π(1), …,π(m)}中工件總加工時(shí)間減少了，這表明在上述工件序列之后加上原來的π(m+1), …,π(r)也不產(chǎn)生誤工工件，換句話說，我們構(gòu)造出了一個(gè)誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

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

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

5 結(jié)語

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

需要進(jìn)一步研究和考慮的問題還有：

(1)1|exactlj|∑wjCj帶確切延誤的單機(jī)排序問題，目標(biāo)是加權(quán)總完工時(shí)間。

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

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