岳雅娟，趙玉芳，許 尉

（沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

0 引 言

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

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

本文研究的問題與上述問題不同，主要?jiǎng)?chuàng)新點(diǎn)為：所有工件只有2個(gè)不同的到達(dá)時(shí)間，而工期、加工時(shí)間及權(quán)可有多個(gè)不同值，并且到達(dá)時(shí)間與工期同序（即ri≤rj，有di≤dj），目標(biāo)為極小化加權(quán)誤工工件數(shù)，這個(gè)問題目前還沒有人研究過。

1 問題描述

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

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

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

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

定義2 對于一個(gè)排序中的任意兩批P和Q，若批P在批Q前加工，意味著不存在這樣的工件i和j，使得i∈P，j∈Q且di＞dj，則稱此排序?yàn)榕鶨DD序。

為了說明上述符號(hào)及定義，先來看一個(gè)例子。

例 設(shè)有8個(gè)工件，到達(dá)時(shí)間r＝（0，0，0，0，0，0，10，10），加工時(shí)間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｝，按時(shí)完工的批為B2，B3，B4，誤工批為B1。

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

圖1 工件的加工時(shí)間表

2 最優(yōu)解性質(zhì)

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

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

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

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

圖2 π和π′的工件加工時(shí)間表

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

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

因此，任意一個(gè)最優(yōu)排序都可通過上述調(diào)換使N0和N1中所有按時(shí)完工批都按批EDD序排列。

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

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

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

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

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，

由以上分析可得：調(diào)換后P和Q中工件仍按時(shí)完工；其他批開始加工時(shí)間不增加，仍然按時(shí)完工；這樣經(jīng)過有限次調(diào)換，得到新排序，其所有按時(shí)完工批都按批EDD序排列，目標(biāo)函數(shù)值不增加，故仍是最優(yōu)排序。

由于所有工件的到達(dá)時(shí)間與工期同序，由上述3個(gè)性質(zhì)可得以下推論。

3 動(dòng)態(tài)規(guī)劃算法

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

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

1）工件j誤工；

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

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

4）工件j排在了N1中最后一個(gè)按時(shí)完工批中的末尾；

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

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

1）工件j誤工；

2）工件j排在了N1中最后一個(gè)按時(shí)完工批中的末尾；

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

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

1）工件j誤工。工件1，…，j－1的加權(quán)誤工工件數(shù)為W－wj，所以Cj（W，t，d）＝Cj－1（W－wj，t，d）；

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

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

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

由此可以得到以下的動(dòng)態(tài)規(guī)劃算法（DP）：

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

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

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

下面來分析此動(dòng)態(tài)規(guī)劃算法的復(fù)雜性。

4 結(jié) 論

本文主要研究了工件帶有2個(gè)不同的到達(dá)時(shí)間，且到達(dá)時(shí)間與工期同序的極小化加權(quán)誤工工件數(shù)的單機(jī)串行批處理機(jī)排序問題，說明了此問題是NP難的，分析了最優(yōu)解的性質(zhì)，并給出了擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法及其時(shí)間復(fù)雜性。進(jìn)一步，這個(gè)問題的FPTAS的設(shè)計(jì)，以及對于有多個(gè)到達(dá)時(shí)間，加工時(shí)間與工期同序或到達(dá)時(shí)間與工期同序等問題也具有較強(qiáng)的實(shí)際背景和理論意義，還有待研究。

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

［2］唐國春，張峰，羅守成，等.現(xiàn)代排序論［M］.上海：上海科學(xué)普及出版社，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］趙玉芳，唐立新.極小化最大完工時(shí)間的單機(jī)連續(xù)型批調(diào)度問題［J］.自動(dòng)化學(xué)報(bào)，2006，32（5）：730－737.

［11］趙玉芳.鏈?zhǔn)郊s束下的一種半連續(xù)型批處理機(jī)調(diào)度問題［J］.沈陽師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，28（3）：335－338.

［12］鐘雪靈.基于動(dòng)態(tài)規(guī)劃的分批排序算法［J］.計(jì)算機(jī)工程與應(yīng)用，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.