郭 曉, 馮密羅, 慕運(yùn)動

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

0 引言

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

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

1 問題的性質(zhì)

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

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

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

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

證明首先分析J0中的工件．假設(shè)最優(yōu)排序σ*中J0的工件并沒有與排序π*一樣按照SPT序排列．令工件Ji是σ*中比排序π*中相對于J0的其他工件更靠后的具有最小指標(biāo)的工件，工件Jj(j>i)為σ*中排在工件Ji之前的J0的一個(gè)工件，如果它們在同一批次中，顯然不會增加∑Cj，所以主要討論的是它們不在同一個(gè)批次中的情況．因?yàn)棣?是一個(gè)SPT序列，所以有pi≤pj．通過相互交換σ*中工件Ji和Jj的位置得到一個(gè)新的排序，記為σ′，那么，Ci(σ′)=Cj(σ′)-pj+pi，Cj(σ′)=Ci(σ′)，且σ′中位于Ji和Jj所在批之間的各批工件都比σ*中提早完工pj-pi個(gè)單位時(shí)間．這樣可知，通過這種互換JN中工件的完工時(shí)間不會增加，J0中的工件的時(shí)間錯(cuò)位不會超過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)序．顯然，如果工件之間存在著空閑時(shí)間，減去相應(yīng)的空閑時(shí)間，那么∑Ci肯定會減小，因此工件之間不存在空閑時(shí)間．

2 算法設(shè)計(jì)

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

算法1

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

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

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

定理1算法1在時(shí)間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的時(shí)間復(fù)雜性，因?yàn)閕≤n0,j≤nN,δ≤k≤ns+PN，t的計(jì)算次數(shù)最多為2n次，而給JN標(biāo)號所需要的時(shí)間為nNlognN，而遞推關(guān)系的變量所需要的時(shí)間為O(n0nNn(ns+PN))，因此算法1的時(shí)間復(fù)雜性為O(n0nNn(ns+PN)).

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

算法2

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

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

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

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

定理2算法2在時(shí)間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的時(shí)間復(fù)雜性，因?yàn)閕≤n0,j≤nN,δ≤k≤ns+min{n0PN,nNP0}，t的計(jì)算次數(shù)最多為2n次．而給JN標(biāo)號所需要的時(shí)間為nNlognN，而遞推關(guān)系的變量所需要的時(shí)間為O(n0nNn(ns+min{n0PN,nNP0}))，因此算法2的時(shí)間復(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] 趙永剛,李文華,豆俊梅.最小化時(shí)間表長和最大加工運(yùn)輸時(shí)間的單機(jī)繼列批在線排序[J].鄭州大學(xué)學(xué)報(bào):理學(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．