到達時間與工期同序的串行批處理機排序問題

岳雅娟，趙玉芳，許 尉

（沈陽師范大學 數學與系統科學學院，沈陽 110034）

0 引 言

在芯片等電子產品制造系統中，常常把在前一道工序加工完的工件放到貨盤里，把同一貨盤中的工件作為一批，一起放到處理機上依次加工，這就相當于在本道工序中工件是動態到達的，并且批的加工時間等于此批中所有工件的加工時間之和，只有當貨盤中的所有工件都加工完后才可以交貨，相當于批中每個工件的完工時間都相同，等于此批中最后一個工件的完工時間。在實際生產過程中，一般工件都有一個交貨期，其重要程度由權來決定。本文研究的問題是帶有2個不同的到達時間，目標是使得未按時完工工件的總權值最小。

對于批處理機排序問題，Webster等［1］進行了綜述。根據加工特點可將批處理機排序問題分為并行批（p－batch）模型、串行批（s－batch）模型［2］及半連續批（c－batch）模型。并行批模型是由 Lee［3］等根據半導體烤箱模型提出的，每批的加工時間為此批中所有工件的加工時間最大者。當所有工件的加工時間相等且到達時間與工期同序時，他們分別給出了極小化誤工工件數∑Uj及最大誤工Tmax問題的多項式動態規劃算法。Lee等［4］給出了帶有2個到達時間的最大完工時間問題的擬多項式動態規劃算法，Liu等［5］進一步證明了這個問題是一般意義NP難的。文獻［6－9］也對這類批處理機排序問題進行了研究。文獻［10］從鋼鐵工業加熱爐對管坯的加熱過程中提出了一種半連續型批處理機排序問題，文獻［11］研究了鏈式約束下半連續型批處理機排序問題。

本文研究的問題與上述問題不同，主要創新點為：所有工件只有2個不同的到達時間，而工期、加工時間及權可有多個不同值，并且到達時間與工期同序（即ri≤rj，有di≤dj），目標為極小化加權誤工工件數，這個問題目前還沒有人研究過。

1 問題描述

化加權誤工工件數∑wjUj問題，用三參數表示法表示為－batch，rj∈｛0，r｝，agr（rj，djwjUj。

為了敘述方便，先來介紹一些符號。N表示要進行加工的n個工件構成的集合，S0表示在r0時刻到達的工件構成的集合，S1表示在r1時刻到達的工件構成的集合；N0表示在r0到r1之間開始加工的批構成的集合，N1表示在r1或r1之后開始加工的批構成的集合。則S1中的工件只能在N1中加工，而S0中的工件可能在N0中加工，也可能在N1中加工。并且S0∪S1＝N，S0∩S1＝?，N0∩N1＝?。

下面給出本文用到的的定義：

定義1 一批中所有工件的最小工期稱為此批的工期；由按時完工工件構成的批稱為按時完工批。也就是說，若一批的完工時間不超過這批的工期，則這批為按時完工批。

定義2 對于一個排序中的任意兩批P和Q，若批P在批Q前加工，意味著不存在這樣的工件i和j，使得i∈P，j∈Q且di＞dj，則稱此排序為批EDD序。

為了說明上述符號及定義，先來看一個例子。

例 設有8個工件，到達時間r＝（0，0，0，0，0，0，10，10），加工時間p＝（4，1，2，1，6，2，3，3），工期d＝（4，6，8，11，13，21，22，25），s＝1。

若對工件分批為B1＝｛J1｝，B2＝｛J2，J3，J4｝，B3＝｛J5｝，B4＝｛J6，J7，J8｝，則S0＝｛J1，J2，J3，J4，J5，J6｝，S1＝｛J7，J8｝。按照圖1所示分批及安排各批的加工順序，有N0＝｛B2，B3｝，N1＝｛B4，B1｝，按時完工的批為B2，B3，B4，誤工批為B1。

具體問題描述如下：設有n個工件J1，…，Jn，要在一臺批處理機上進行加工，這n個工件構成的集合為N。有2個不同的到達時間r0，r1，不失一般性，設r0＝0，r1＝r＞0。工件Jj的到達時間為rj（rj∈｛0，r｝），加工時間為pj，工期為dj，完工時間為Cj；若Cj＞dj，稱工件Jj誤工，有Uj＝1；否則稱工件Jj按時完工，有Uj＝0；權為wj，j＝1，…，n。批處理機的容量無限，即批處理機能將B（B＞n）個工件作為一批同時加工。只有當同一批中的工件都到達后，這一批才可以開始加工。在每一批開始加工之前都有一個固定的調整時間s，即批調整時間。在批的調整時間內機器不能加工任何工件，每一批內的工件間沒有調整時間。假設所有數據都為非負整數。批的加工時間為此批中所有工件的加工時間之和，同一批中所有工件的完工時間都相等，為此批中最后一個工件的完工時間，稱為批的完工時間。對于極小

圖1 工件的加工時間表

2 最優解性質

Hochbaum等［13］證明了帶有非負安裝時間s及一個共同工期d，極小化加權誤工工件數∑wjUj的單機批處理機排序問題是NP難的。顯然，帶有2個不同到達時間的問題1－batch，rj∈｛0，r｝，agr（rj，djwjUj至少也是NP難的。下面給出此問題的最優解的性質。

證明 用反證法。假設存在一最優排序，其中按時完工批l中的工件Jl1，Jl2，…，Jlk不按EDD序排列。不妨設工件Jli，Jlj（1≤i＜j≤k），Jli在Jlj前加工，而dli＞dlj。交換這兩個工件，由于交換工件不改變這批的加工時間，所以交換后批l的完工時間與交換前相等，即工件Jli和Jlj的完工時間不變。又因為批l的工期不變，所以工件Jli和Jlj仍按時完工，交換后目標函數值不增加，故交換后仍是最優排序，其中同一按時完工批中的工件都按EDD序排列。

證明 1）首先用反證法證明N0中按時完工的批是按批EDD序排列的。

假設存在一個最優排序π，N0中按時完工的批不按批EDD序排列，則在此排序中，存在兩相鄰批P和Q，批P和批Q的工期分別為dP和dQ，P在Q前加工，且dP＞dQ，由批的工期的定義，不妨設工件i和j，i∈P，j∈Q，使得dP＝di，dQ＝dj，則di＞dj。

圖2 π和π′的工件加工時間表

由此可得批P′的完工時間提前了，則批Q′的開始加工時間提前了，但完工時間不變。故調換后除工件i外，其他工件的完工時間都不大于調換前的完工時間，從而它們都不誤工。調換后工件i和j在同一批中加工，因此工件i和j的完工時間相等，即C′i＝C′j＝CQ。而工件j按時完工，即Cj′≤dj，又C′j＝C′j，dj＜di，所以工件i也按時完工。如圖2所示。

2）下面來看N1中的情況。N1中的批在r1或r1之后開始加工，此時所有工件都已到達。與證明1）類似，可得N1中按時完工的批也按批EDD序排列。

因此，任意一個最優排序都可通過上述調換使N0和N1中所有按時完工批都按批EDD序排列。

證明 由性質2，N0和N1中按時完工的批分別按批EDD序排列，又S1中的工件在r1＝r時刻到達，只能在N1中加工，故只需考慮S0中的工件在N1中加工的情況即可。

用反證法。假設存在一個最優排序π，其中2個按時完工批P和Q不按批EDD序排列。設批P和Q的工期分別為dP、dQ，加工時間分別為PP、PQ，完工時間分別為CP、CQ，且P∈N0，Q∈N1，dP＞dQ。不失一般性，假設P是N0中最后一個按時完工批，Q是N1中第一個按時完工批，t為批P的開始加工時間。下面考慮兩種情況：

1）批P和Q中所有工件都在S0中。則CP＝t＋s＋PP，CQ＝CP＋s＋PQ＝t＋s＋PP＋s＋PQ≤dQ。現將π做變動如下：把批Q中的工件都移到批P中，新批設為P′，且P′中工件按EDD序排列，其余批及各批加工順序不變，從而得到另一個排序π′。在π′中，C′p＝t＋s＋PP＋PQ＜CQ≤dQ＝d′P，故調換后仍為按時完工批，其余批開始加工時間不增加，仍然按時完工。

故CP＜C′P。則C′P、CP與r有以下3種大小關系。

a）若C′P＞r且CP＞r，則CQ＝max｛CP，r｝＋s＋PQ＝CP＋s＋PQ，

b）若C′P＞r且CP≤r，則CQ＝max｛CP，r｝＋s＋PQ＝r＋s＋PQ，

c）若C′P≤r，一定有CP＜r，則CQ＝max｛CP，r｝＋s＋PQ＝r＋s＋PQ，

由以上分析可得：調換后P和Q中工件仍按時完工；其他批開始加工時間不增加，仍然按時完工；這樣經過有限次調換，得到新排序，其所有按時完工批都按批EDD序排列，目標函數值不增加，故仍是最優排序。

由于所有工件的到達時間與工期同序，由上述3個性質可得以下推論。

3 動態規劃算法

根據上述推論，將工件按EDD序重新排列。Cj（W，t，d）表示已排序的工件1，…，j的加權誤工工件數為W，且最后按時完工批的開始加工時間為t、工期為d的最后按時完工工件的最小完工時間。Cj（W）表示Cj（W，t，d）中的最小者，即加權誤工工件數為W的已排序的工件1，…，j中最后按時完工工件的最小完工時間。下面考慮工件1，…，j的任一最優排序。當工件1，…，j－1排完后，工件j的排列情況如下。

若工件j在S0中，則有5種可能的情況：

1）工件j誤工；

2）工件j排在了N0中最后一個按時完工批中的末尾，隱含著工件j的完工時間不超過此批的工期；

3）工件j在N0中單獨形成一個新批，在它的工期dj前完工；

4）工件j排在了N1中最后一個按時完工批中的末尾；

5）工件j在N1中單獨形成一個新批，在它的工期dj前完工。

若工件j在S1中，則有3種可能的情況：

1）工件j誤工；

2）工件j排在了N1中最后一個按時完工批中的末尾；

3）工件j在N1中單獨形成一個新批，在它的工期dj前完工。

通過以上分析，工件j的排序可歸納為以下兩種情況：

1）工件j誤工。工件1，…，j－1的加權誤工工件數為W－wj，所以Cj（W，t，d）＝Cj－1（W－wj，t，d）；

2）工件j不誤工，也就是Cj（W，t，d）≤dj，有下面兩種情況：

① 工件j排在當前排序的最后一個按時完工批中的末尾，即Cj－1（W，t，d）＞0。只有當工件都到達后才可以進行加工，故t≥rj。此時工件j的最小完工時間為Cj（W，t，d）＝Cj－1（W，t，d）＋pj。由于工件的到達時間與工期同序，所以排完j后，最后按時完工批的工期仍為d，即Cj（W，t，d）≤d。

② 工件j單獨形成一個新批，也就是 max｛Cj－1（W，k，b），t｝＋s＋pj≤d（0≤k≤t，b∈｛d1，…，dj－1｝），此時d＝dj。其完工時間為t＋s＋pj，其中t≥Cj－1（W，k，b）且t≥rj。下面具體分析t的取值。若工件j在N0里單獨形成一個新批，此時rj＝0，t＝Cj－1（W，k，b）；若工件j在N1里單獨形成一個新批，當rj＝0時，t＝max｛Cj－1（W，k，b），r｝；當rj＝r時，t＝max｛Cj－1（W，k，b），r｝；所以若工件j單獨形成一個新批，對于0≤k≤t，b∈｛d1，…，dj－1｝，其完工時間為 max｛Cj－1（W，k，b），t｝＋s＋pj。對于t＜min｛Cj－1（W，k，b），rj｝，此時要么機器不空閑，要么工件未到達，故定義Cj（W，t，d）＝＋∞。

由此可以得到以下的動態規劃算法（DP）：

步驟1 把工件按EDD序排列，即d1≤d2≤…≤dn；

步驟4 計算Cj（W）＝min｛Cj（W，t，d）｝；

步驟5 若j＝n，計算W＊＝min｛W：Cn（W）＜＋∞｝，利用反向追蹤得到所有工件的一個最優分批，再把誤工工件以任意順序排在最后按時完工批的后面加工。否則，令j＝j＋1，轉步驟3。

下面來分析此動態規劃算法的復雜性。

4 結 論

本文主要研究了工件帶有2個不同的到達時間，且到達時間與工期同序的極小化加權誤工工件數的單機串行批處理機排序問題，說明了此問題是NP難的，分析了最優解的性質，并給出了擬多項式動態規劃算法及其時間復雜性。進一步，這個問題的FPTAS的設計，以及對于有多個到達時間，加工時間與工期同序或到達時間與工期同序等問題也具有較強的實際背景和理論意義，還有待研究。

［1］WEBSTER S，BAKER K R.Scheduling groups of jobs on a single machine［J］.Oper Res，1995，43：692－703.

［2］唐國春，張峰，羅守成，等.現代排序論［M］.上海：上海科學普及出版社，2003.

［3］LEE C Y，UZSOY R，MARTIN－VEGA L A.Efficient algorithms for scheduling semiconductor burn－in operations［J］.Oper Res，1992，40：764－775.

［4］LEE C Y，UZSOY R.Minimizing makespan on a single batch processing with dynamic job arrivals［J］.Int J Prod Res，1999，37：219－236.

［5］LIU Zhaohui，YU Wenci.Scheduling one batch processor subject to job release dates［J］.Disc Appl Math，2000，105（1／2／3）：129－136.

［6］BRUCKER P，GLADKY A，HOOGEVEEN H，et al.Scheduling a batching machine［J］.J Sched，1998，1：31－54.

［7］DENG X T，POON C K，ZHANG Y Z.Approximation algorithms in batch processing［J］.J Comb Opt，2003，7：247－257.

［8］LIU Zhaohui，CHENG T C E.Approximation schemes for minimizing total（weighted）completion time with release dates on a batch machine［J］.Theor Comp Sci，2005，347（1／2）：288－298.

［9］CONDOTTA A，KNUST S，SHAKHLEVICH N V.Parallel batch scheduling of equal－length jobs with release and due dates［J］.J Sched，2010，13：463－477.

［10］趙玉芳，唐立新.極小化最大完工時間的單機連續型批調度問題［J］.自動化學報，2006，32（5）：730－737.

［11］趙玉芳.鏈式約束下的一種半連續型批處理機調度問題［J］.沈陽師范大學學報：自然科學版，2010，28（3）：335－338.

［12］鐘雪靈.基于動態規劃的分批排序算法［J］.計算機工程與應用，2010，46（7）：229－231.

［13］HOCHBAUM D S，LANDY D.Scheduling with batching：minimizing the weighted number of tardy jobs［J］.Oper Res Lett，1994，16：79－86.

［14］BRUCKER P，KOVALYOV M Y.Single machine batch scheduling to minimize the weighted number of late jobs［J］.Math Meth Oper Res，1996，43：1－8.

［15］CHENG T C E，KOVALYOV M Y.Single machine batch scheduling with sequential job processing［J］.IIE Transactions，2001，33：413－420.

［16］BAPTISTE P.Batching identical jobs［J］.Math Meth Oper Res，2000，52：335－367.