時間錯位限制下最小化總完工時間的繼列分批重新排序

郭 曉, 馮密羅, 慕運動

(1.河南工業(yè)大學(xué) 理學(xué)院 河南 鄭州 450001； 2.鄭州大學(xué) 數(shù)學(xué)系 河南 鄭州 450001)

0 引言

工件錯位即在原始排序中產(chǎn)生的錯位限制下，最小化最大延誤時間和總完工時間的單機(jī)重新排序問題[1]．Potts等[2-4]考慮了在單機(jī)情況下，分批排序的排序方法以及分批排序問題不同情況下的不同算法． Agnetis等[5]主要考慮的是具有兩個代理和兩個目標(biāo)函數(shù)的最小化加權(quán)總完工時間等問題．Baker等[6]考慮了多準(zhǔn)則模型的機(jī)器排序問題，且給出了多代理目標(biāo)函數(shù)的線性組合時的結(jié)果．Yuan等[7-8]考慮了具有到達(dá)時間的最大序列或時間錯位限制下的最小化最大完工時間的重新排序問題．根據(jù)Hall等[1]的描述，單機(jī)重新排序問題可表示為：令J0={J1,J2,…,Jn0}為單機(jī)上的原始工件集．在模型中，假定J0中的工件已經(jīng)在最小化某一經(jīng)典目標(biāo)函數(shù)下最優(yōu)地安排加工，且π*是一個最優(yōu)序．令JN={Jn0+1,Jn0+2,…,Jn0+nN}為新工件集,記J=J0∪JN,J中的每一個工件Jj的加工時間為整數(shù)且滿足pj≥0,π*和σ*分別表示J0和J工件的最優(yōu)序．對于J的工件的任意排序σ，定義2個變量：Cj(σ)表示J中工件Jj在σ中的完工時間;Δj(π*,σ)=|Cj(σ)-Cj(π*)|表示J0中工件Jj的時間錯位．在不引起混淆的前提下，上面的參數(shù)可以分別簡化為Cj,Δj(π*)．需要說明的是，在繼列分批排序中，由于同一批的工件的完工時間相同，因此,在同一批中工件沒有先后次序之分．

在研究問題的過程中，主要考慮兩個方面：第一，研究分批重新排序問題的可行排序和最優(yōu)排序的結(jié)構(gòu)性質(zhì)；第二，基于這些性質(zhì)設(shè)計問題的最優(yōu)算法．本文證明了這些問題能在擬多項式時間內(nèi)可解．

1 問題的性質(zhì)

首先研究1|s-batch,Δmax(π*)≤k|∑Cj和|s-batch,∑Δj(π*)≤k|∑Cj兩個問題的結(jié)構(gòu)性質(zhì)．

引理1對于問題1|s-batch,Δmax(π*)≤k|∑Cj，如果存在一個最優(yōu)排序，使得J0中的工件在排序π*和σ*中具有相同的次序，那么一定存在工件間沒有空閑時間的最優(yōu)排序，使得排在J0最后一個工件所在批之前的JN中的工件加工時間之和不大于k．

證明因為在排序π*和σ*中J0中的工件具有相同的排序，移走排序σ*中的任何一個空閑時間仍能夠保持其可行性，且∑Cj的數(shù)值不會增大．那么，該問題存在工件間沒有空閑時間的最優(yōu)排序．優(yōu)先級指標(biāo)序列排序原則表明,J0中的工件在排序π*和σ*中具有相同的次序．因此，Δmax(π*)的值是由排在J0最后一個工件之前的工件的加工時間之和決定的．

引理2對于問題1|s-batch,Δmax(π*)≤|∑Cj和1|s-batch,∑Δj(π*)≤k|∑Cj，都存在一個最優(yōu)排序，滿足J0中的工件與排序π*一樣按照SPT序排列，JN中工件按照SPT序排列，且所有工件間沒有空閑時間．

證明首先分析J0中的工件．假設(shè)最優(yōu)排序σ*中J0的工件并沒有與排序π*一樣按照SPT序排列．令工件Ji是σ*中比排序π*中相對于J0的其他工件更靠后的具有最小指標(biāo)的工件，工件Jj(j>i)為σ*中排在工件Ji之前的J0的一個工件，如果它們在同一批次中，顯然不會增加∑Cj，所以主要討論的是它們不在同一個批次中的情況．因為π*是一個SPT序列，所以有pi≤pj．通過相互交換σ*中工件Ji和Jj的位置得到一個新的排序，記為σ′，那么，Ci(σ′)=Cj(σ′)-pj+pi，Cj(σ′)=Ci(σ′)，且σ′中位于Ji和Jj所在批之間的各批工件都比σ*中提早完工pj-pi個單位時間．這樣可知，通過這種互換JN中工件的完工時間不會增加，J0中的工件的時間錯位不會超過k．如果σ′中工件Jj的位置不比π*中的位置靠前(與工件Ji的情形一樣)，若Cj(σ′)≥Ci(σ′)，那么Δj(π*,σ′)<Δi(π*,σ*)；否則Δj(π*,σ′)<Δj(π*,σ*).這兩種情形下，Δj(π*,σ′)=Δj(π*,σ*)-h′，Δj(π*,σ′)≤Δj(π*,σ*)+h′，其中,h′=Ci(σ*)-Ci(σ′)，都有Δmax(π*,σ′)≤Δmax(π*,σ*),∑Δi(π*,σ′)≤∑Δj(π*,σ*).因此，排序σ′是可行的且是最優(yōu)的．重復(fù)上述有限次討論可以說明一定存在與排序π*一樣按照SPT序排列的最優(yōu)序．顯然，如果工件之間存在著空閑時間，減去相應(yīng)的空閑時間，那么∑Ci肯定會減小，因此工件之間不存在空閑時間．

2 算法設(shè)計

對于問題1|s-batch,Δmax(π*)≤k|∑Cj，應(yīng)用引理2的SPT序可以得到一個最優(yōu)排序．下面的動態(tài)規(guī)劃算法給出了滿足最大時間錯位限制下的最優(yōu)組合方案．

算法1

標(biāo)號：給JN中所有工件按照SPT規(guī)則標(biāo)號；

值函數(shù)：f(i,j,t,δij)表示最大時間錯位為δij時，部分排序的總完工時間的最小值，其中,i表示為J0的前i個工件，j表示為JN中的前j個工件，t表示當(dāng)前工件的完工時間；

初值條件：f(0,0,0,0)=0；

定理1算法1在時間O(n0nNn(ns+PN))內(nèi)給出了1|s-batch,Δmax(π*)≤k|∑Cj的最優(yōu)排序．

證明由引理1，2可知，只要通過SPT規(guī)則把J0和JN的全部的情況給列出來，算法1通過比較所有的可能出現(xiàn)的情況，就可以得到最優(yōu)排序．現(xiàn)在考慮算法1的時間復(fù)雜性，因為i≤n0,j≤nN,δ≤k≤ns+PN，t的計算次數(shù)最多為2n次，而給JN標(biāo)號所需要的時間為nNlognN，而遞推關(guān)系的變量所需要的時間為O(n0nNn(ns+PN))，因此算法1的時間復(fù)雜性為O(n0nNn(ns+PN)).

對于問題1|s-batch,∑Δj(π*)≤k|∑Cj，應(yīng)用引理2的SPT序可以得到一個最優(yōu)排序．下面的動態(tài)規(guī)劃算法給出了滿足總時間錯位限制下的最優(yōu)組合方案．

算法2

標(biāo)號：給JN中所有工件按照SPT規(guī)則標(biāo)號；

值函數(shù)：f(i,j,t,δ)表示總時間錯位為δ的時候，部分排序總完工時間的最小值．其中i表示為J0的前i個工件，j表示為JN中的前j個工件，t表示當(dāng)前工件的完工時間；

初值條件：f(0,0,0,0)=0；

其中,u表示工件Ji的時間錯位，h0表示當(dāng)前批中屬于J0但是不與Ji在原始排序中分到同一批的工件個數(shù)，h1表示當(dāng)前批中工件個數(shù)(不包含工件Ji)，h2表示當(dāng)前批中屬于J0的工件個數(shù)，h3表示當(dāng)前批中工件個數(shù)(不包含工件Jj)．

定理2算法2在時間O(n0nNn(ns+min{n0PN,nNP0}))內(nèi)給出了1|s-batch,∑Δj(π*)≤k|∑Cj的最優(yōu)排序．

證明由引理2可知，只要通過SPT規(guī)則把J0和JN的全部的情況給列出來，算法2通過比較所有可能出現(xiàn)的情況，就可以得到最優(yōu)排序．現(xiàn)在考慮算法2的時間復(fù)雜性，因為i≤n0,j≤nN,δ≤k≤ns+min{n0PN,nNP0}，t的計算次數(shù)最多為2n次．而給JN標(biāo)號所需要的時間為nNlognN，而遞推關(guān)系的變量所需要的時間為O(n0nNn(ns+min{n0PN,nNP0}))，因此算法2的時間復(fù)雜性為O(n0nNn(ns+min{n0PN,nNP0}))．

[1] Hall N G， Potts C N． Rescheduling for new orders[J]． Operations Research， 2004,52(3)：440-453．

[2] Potts C N，Kovalyov M Y． Scheduling with batching：A review[J]． European Journal of Operational Research,2000，120(2)：228-249．

[3] Brucker P，Gladky A,Hoogeveen H,et al． Scheduling a batching machine[J]．Journal of Scheduling,1998,1(1)：31-54．

[4] 趙永剛,李文華,豆俊梅.最小化時間表長和最大加工運輸時間的單機(jī)繼列批在線排序[J].鄭州大學(xué)學(xué)報:理學(xué)版,2010,42(4):36-39.

[5] Agnetis A，Mirchandani P B，Pacciarelli D， et al．Scheduling problems with two competing agents[J]．Operations Research,2004,52(2)：229-242．

[6] Baker K R，Smith J C． A multiple-criterion model for machine scheduling[J]． Jounrnal of Scheduling， 2003，6(1)：7-16．

[7] Yuan Jinjiang， Mu Yundong． Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption[J]．European Journal of Operational Research，2007，182(2)： 936-944．

[8] Yuan Jinjiang， Mu Yundong， Lu Lingfa，et al． Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan[J]． Asia-Pacific Journal of Operational Research， 2007，24(6)：789-796．

[9] Brucker P．Scheduling Algorithms[M]．Berlin:Springer Verlag，2001．

[10]Graham R L，Lawler E L，Lenstra J K， et al．Optimization and approximation in deterministic sequencing and scheduling: A survey[J]． Annals of Discrete Mathematics,1979,5(2)：287-326．