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

慕運動， 皮軍德， 郭 曉

（河南工業(yè)大學理學院，鄭州 450001）

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

慕運動， 皮軍德， 郭 曉

（河南工業(yè)大學理學院，鄭州 450001）

在單機分批排序中，一個原始工件集已經分好批排好順序，使得給定的目標函數最小.當一個新的工件集到來時，決策者需要插入這些新工件到原來的順序中，這樣使得原始工件就會產生一些錯位.但為了滿足對原始工件集的要求而不過分的打亂它們的順序的條件下，使得新的目標值為最優(yōu).本文主要研究的是在序列錯位量限制的條件下，繼列分批最小化總完工時間的重新排序問題，對于最大序列錯位和總序列錯位的不同約束情況下，研究可行排序和最優(yōu)排序的結構性質，進而設計了它們的多項式時間算法.

重新排序；單機；分批；分批排序；序列錯位

1 引言和問題闡述

在本文中，我們研究單機分批排序中的繼列分批，即s分批重新排序問題.所謂s分批是指在同一批的工件，具有相同的開工時間和完工時間，其加工時間等于全部工件的加工時間之和.假設原始工件已經按照總完工時間最優(yōu)地排列，新工件在零時刻都已經到達，當新工件安排加工時，我們必須要考慮原始工件的錯位問題，使得在時間錯位約束下，繼列分批的繼列分批最小化總完工時間的重新排序問題.Hall和Potts［5］在前人研究的基礎上首先引入了工件錯位的概念，考慮了在對從原始排序中產生的錯位限制下的具有新來工件的最小化最大延誤時間和總完工時間的單機重新排序問題.Potts和Brucker［7］［8］考慮了在單機情況下，分批排序的集中排序方法以及分批排序問題不同情況下的不同算法.Agnetis［1］主要考慮的是具有兩個代理和兩個目標函數的最小化加權總完工時間.Baker和Smith［2］考慮了多準則模型的機器排序問題，且給出了多代理目標函數的線性組合時的結果.Yuan和Mu［9，10］考慮了具有到達時間的最大序列或時間錯位限制下的最小化完工時間的重新排序問題.根據Hall和Potts［5］的描述，單機重新排序問題能表示為：令JO＝｛J1，J2，…｝為單機上的原始工件集.在模型中，我們假定JO中的工件已經在最小化某一經典目標函數下最優(yōu)地安排加工，且π＊是一個最優(yōu)序.令JN＝｛，，…，｝為新工件集.記J＝JO∪JN.J中的每一個工件Jj的加工時間為整數且滿足pj≥0.π＊和σ＊分別表示JO和J工件的最優(yōu)序.對于J的工件的任意排序σ，我們定義下面幾個變量：

·Cj（σ）表示J中工件Jj在σ中的完工時間.

·Dj（π＊，σ）表示JO中工件Jj的序列錯位，即如果工件Jj在序列π＊和σ中分別是第x和y個工件，那么Dj（π＊，σ）＝.

在不引起混淆的前提下，上面的參數可以分別簡化為Cj，Dj（π＊）.

排序問題的標準分類方法［3，4］是三參數法分類αβγ，其中α表示排序環(huán)境，β描述工件特征或者限制要求，γ為最優(yōu)化準則.本文僅討論單機分批問題，也就是α＝1時的情形.對于β，討論繼列分批時對錯位的限制，這些限制有下面的二種形式：

對于γ，這里的函數為總完工時間，因此研究模型可記為

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

2 問題的性質

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

證首先分析JO中的工件.最優(yōu)序σ＊中JO的工件并沒有與排序π＊一樣按照SPT序排列.令工件Ji是σ＊中比排序π＊中相對于JO的其它工件更靠后的具有最小指標的工件，工件Jj（j＞i）為σ＊中排在工件Ji之前的JO的一個工件，如果它們在同一批次中，顯然不會增加∑Cj，所以主要討論的是它們不在同一個批次中的情況.因為π＊是一個SPT序列，所以有pi≤pj.通過相互交換σ＊中工件Ji和Jj的位置得到一個新的排序，記為σ′，那么

且σ′中所有位于Ji和Jj所在批之間各批的工件都比σ＊中提早完工pj－pi個單位時間.這樣可知，通過這種互換JN中工件的完工時間不會增加，JO中的工件的序列錯位不會超過k.如果σ′中工件Jj的位置不比π＊中的位置靠前（與工件Ji的情形一樣），那么，Dj（π＊，σ′）＜Di（π＊，σ＊），否則，Dj（π＊，σ′）＜Dj（π＊，σ＊）.在兩種情形下，

其中h表示σ＊中位于Ji和Jj所在批之間各批以及Ji所在批中含有JN的工件數，都有Dmax（π＊，σ′）≤Dmax（π＊，σ＊）和∑Dj（π＊，σ′）≤∑Di（π＊，σ＊）.因此，排序σ＇是可行的且是最優(yōu)的.重復上述有限次討論可以說明一定存在與排序π＊一樣按照SPT序排列的最優(yōu)序.顯然，如果工件之間存在著空閑時間，減去相應的空閑時間，那么∑Ci肯定會減小，因此工件之間不存在著空閑時間.

3 算法設計

算法1：

輸入：給定pj（j＝1，2，…，n），k，π＊和，且k≤nN；

標號：讓JN中所有工件按照SPT規(guī)則排列好；

值函數：f（i，j，t，δ）表示最大序列錯位為δ的時候，部分工件的總完工時間為最小的排序.其中i表示為JO的i個工件，j表示為JN中的j個工件，t表示當前工件的完工時間；

其中h0表示當前批中工件Ji－1所在批到當前批之前所有批中屬于JN的工件個數（如果在同一批，則h0＝0），h1表示當前批含有工件個數（不包含工件Jj），h2表示工件Ji－1所在批到Jj所在批中屬于JN的工件個數.h3表示當前批含有工件的個數（不包含工件Jj）.

定理1算法1在時間的最優(yōu)排序的算法.

證 由引理1，2可知，只要通過SPT規(guī)則把JO和JN的全部的情況給列出來，算法2通過比較所有的可能出現的情況，就可以得到最優(yōu)排序.現在考慮算法2的時間復雜性.因為i≤n0，j≤nN，δ≤k≤nN，而工件的最后完工時間t計算的次數最多為2n，因此遞推函數的算法復雜性為O）.而上面的排序過程中所產生的的時間復雜性為O），因此總的算法復雜性為O（）.

算法2：

輸入：給定pj（j＝1，2，…，n），k和π＊，且k≤n0nN；

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

值函數：f（i，j，t，δ）表示總序列錯位為δ的時候，部分工件的總完工時間為最小的排序.其中i表示為JO的i個工件，j表示為JN中的j個工件，t表示當前工件的完工時間；

初值條件：f（0，0，0，0）＝0；

其中h0表示為當前批之前所有批中屬于JN的工件個數，h1表示當前批中工件個數（不包含工件Ji），h2表示當前批中工件個數（不包含工件Jj）.

定理2算法2在時間最優(yōu)排序算法.

證由引理2可以知道，只要通過SPT規(guī)則把JO和JN的全部的情況給列出來，算法2通過比較所有的可能出現的情況，就可以得到最優(yōu)排序.現在考慮算法2的時間復雜性，因為i≤n0，j≤nN，δ≤k≤n0nN，而工件的最后完工時間t所計算的次數最多為2n，因此遞推函數的算法復雜性為O（）.而上面的排序過程中所產生的的時間復雜性為O（n＋nNlognN），因此總的算法復雜性為O（n20n2Nn）.

［1］Agnetis A，Mirchandani P B，Pacciarelli D and Pacifici A.Scheduling problems with two completing agents［J］.Operations Research，2004，52：229－242.

［2］Baker K R and Smith J C.A multiple－criterion moderl for machine scheduling［J］.Jounrnal of Scheduling，2003，6：7－16.

［3］Brucker P.Scheduling algorithms［M］.Berlin：Springer Verlag，2001.

［4］Graham R L，Lawler E L，Lenstra J K，et al.Optimization and approximation in deterministic machine scheduling：A survey［J］.Annals of Discrete Mathematics，1979，5：287－326.

［5］Hall N G and Poots C N.Rescheduling for new orders［J］.Operations Research，2004，52：440－453.

［6］Potts C N and Van L N，Wassenhove.Integrating scheduling with batching and lot－sizing：a review of algorithms and complexity［J］.Operational Research，1992，43：395－406.

［7］Potts C N，Kovalyov MY.Scheduling with batching：a Review［J］.European Journal of Operation Research.2000，120：228－249.

［8］Brucker P，Gladky A.Scheduling a batching machine［J］.Journal of Scheduling，1998，1：31－54.

［9］Yuan J J and Mu Y D.Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption［J］.European Journal of Operation Research，2007，182：936－944.

［10］Yuan J J and Mu Y D，Lu L F and Li W H.Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan［J］.Asia－Pacific Journal of Operational Research，2007，24：789－796.

Rescheduling to Minimize Total Completion under a Limit Sequence Disruption of the Series Batching

MUYun－dong，PiJun－de，GUOXiao
（College of Science，Henan University of Technology，Zhengzhou 450001，China）

In the rescheduling on a single batching machine，a set of the original jobs has already been scheduled，in order to make a given objective function is minimal.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.We consider the total completion time of the series batching under the a limit on the sequence disruption，and give the polynomial time algorithms to the maximum sequence disruption and the total sequence disruptions.

rescheduling；single machine；batching；batching sequence；sequence disruption

O224

A

1672－1454（2012）04－0068－04

2010－03－26；［修改日期］2010－09－27

河南省自然科學基金NSFHN（112300410078）；河南省教育廳自然科學基金（2011B110008）；河南工業(yè)大學博士科研基金