盧文麗,柏慶國

(1.淄博師范高等?？茖W(xué)校教育科學(xué)系,山東淄博 255100;2.曲阜師范大學(xué)運(yùn)籌與管理學(xué)院,山東日照 276826)

0 引 言

排序問題的理論與應(yīng)用研究興起于20世紀(jì)60年代,經(jīng)過40多年的發(fā)展已經(jīng)成為組合優(yōu)化領(lǐng)域的重要組成部分.由于分批排序問題具有較強(qiáng)的應(yīng)用背景又是經(jīng)典排序的推廣,所以此類問題的研究工作自20世紀(jì)90年代以來得到很快的發(fā)展并活躍起來.對于 1│rj,B│Cmax的離線情形,1992年,Lee等[1]在rj=0時給出了一些較基本的結(jié)果.2000年, Liu等[2]證明了對于只有兩個到達(dá)時間的情況下的NP完備性.此外,對工件同時到達(dá),目標(biāo)函數(shù)為總完工時間這種情形,Brucker等[3]給出了時間復(fù)雜性為O(nB(B-1))的動態(tài)規(guī)劃算法,Chandru等[4]給出了分枝定界算法和幾個啟發(fā)式算法.

1 工件有尺寸的分批排序

一般的分批排序問題在對工件進(jìn)行分批時,主要考慮每一批次中工件的個數(shù),但在實(shí)際中,工件尺寸通常大小不一,因而在分批時需要考慮工件尺寸的大小.從工件的尺寸這一角度出發(fā),分批排序可以分為兩大類:一是工件的尺寸都相同,二是工件的尺寸不同.

對于單臺機(jī)器上的分批排序問題,當(dāng)工件不但有不同的加工時間而且有不同的尺寸時,稱此類排序?yàn)楣ぜ谐叽绲姆峙判?假定機(jī)器的尺寸為B,工件Jj的尺寸為時間sj(0＜sj≤B),如果一個批中所含工件的尺寸之和等于B,稱此批為滿批;否則稱為非滿批.與以前考慮不同的是,這里的滿指的是尺寸,而以前所考慮的是工件的個數(shù).批 Bi的加工時間是這批中所含工件的加工時間的最大者.若一個工件的尺寸大于B/2,則稱此批工件為大工件,否則稱為小工件,此問題記為 BPP.如果允許把工件的尺寸分為幾個部分放在不同的批中加工,那么稱工件是允許按尺寸拆分的,此問題記為SBPP.若只允許小的工件按尺寸拆分,記為問題SBPP′.若任一較大工件的加工時間不小于任何一較小工件的加工時間,則稱此問題為工件加工時間和工件尺寸一致排序問題,簡稱一致性排序.

目前,對于工件尺寸不相同的分批排序問題涉及的相關(guān)文獻(xiàn)相對較少.對于1│B,sj│Cmax的情形,Lee等[1]證明了當(dāng)所有工件的加工時間相同時,這個問題等同于裝箱問題,它是NP-完備的.同時,文獻(xiàn)還給出了兩個近似算法,FFLPT和FFSPT,但未給出它們的性能比.Zhang等[5]對于文獻(xiàn)[1]提出的所有近似算法進(jìn)行了分析,并得到了相應(yīng)的近似比,而且對于一致性排序的情形給出了最差性能比為3/2的離線算法,并對一般情形下的離線排序給出了一個最差性能比為7/4的算法.

2 算法描述

在本文中,我們首次考慮了同型機(jī)上的工件具有不同尺寸大小且是一致性排序的分批排序問題,將其用3元素法表示為 pm│B,sj│Cmax.對這一問題,我們提出了一個近似比為5/2-1/m的離線算法.

Zhang等[5]對于1│B,sj│Cmax的一致性排序問題SBPP′,給出了可求其最優(yōu)解的算法A1,而且這個最優(yōu)值是問題BPP的最優(yōu)值的下界.

2.1 算法A1

算法A1的具體步驟為:

步驟1.把工件按加工時間非增的次序編號,大工件的個數(shù)記為 k,k個大工件記為,J1,J2,…,Jk;

步驟2.把大工件Jj放入第j(j=1,2,…,k)批;

步驟3.把小工件Jj(j=k+1,k+2,…,n)放入編號最小的非滿批中,必要時可把它拆分,直到此批已滿,并把拆分后的工件放入下一個編號最小的非滿批中,若無非滿批存在,則開始一個新的批.

由算法A1得到問題SBPP′的最優(yōu)排序記為π,并設(shè)π有m批,B1,B2,…,Bm.批 Bj的加工時間記為pj,顯然,p1≥p2≥…≥pm.若一個工件被拆分,則稱其為s-工件,顯然s-工件都是小工件.用q表示s-工件的個數(shù),可知q≤m-1,用J′ik表示工件的第一部分在批Bik的s-工件(1≤i1≤…≤iq≤m-1).

另外,對于一致性排序問題BPP,Zhang等[5]將算法A1作為一個子算法給出了最差性能比為3/2的離線算法A2.

2.2 算法A2

對于一致性的排序問題SBPP′運(yùn)用算法A1得到排序π′,把所有的s-工件從中移走,對于k=1, 2,…,「q/2┐,把工件J′i2k-1和J′i2k放入一批中,其加工時間為 P′i2k-1,得到,m+「q/2┐批的排序π″.

引理1 根據(jù)算法A2對工件進(jìn)行分批,則所得到的批的加工時間按非增的順序排列,而且對于一致性排序問題,算法A2的最差性能比是3/2.

2.3 算法 FA

將算法 A2作為子算法,我們考慮 pm│B, sj│Cmax的一致性排序問題,得到算法 FA,其具體步驟為:

步驟1.利用算法A2對工件進(jìn)行分批,設(shè)得到k批.記每批的加工時間 pj,j=1,2,…,k,顯然 p1≥p2≥…≥pk.

步驟2.設(shè)前l(fā)-1批已加工完,將第l批安排到最先出現(xiàn)空閑的機(jī)器上加工,l=1,2,…,k.

張鑫等[6]證明了如下引理成立.

引理2 對于相同的工件集,令 C＊是 pm│B, sj│Cmax的最優(yōu)分批所對應(yīng)的批的加工時間之和, C′＊是問題 1│B,sj│Cmax的最優(yōu)值,則 C＊≥C′＊.

定理1 不妨設(shè) Cmax為算法 FA對于pm│B, sj│Cmax所得到的最大完工時間,C＊為這個問題的最優(yōu)值,則有,

證明 若k≤m,則每臺機(jī)器至多可以安排一批工件,顯然算法最優(yōu).否則不妨設(shè) Bl是運(yùn)用算法FA最后完工的批,設(shè)它的開工時間為s,且在第t臺機(jī)器上加工,則有,Cmax=s+pl.由算法知,在 s前機(jī)器沒有空閑,否則我們可以將Bl放到空閑的機(jī)器上加工.

因此有,

從而有,

因此,

由引理1知,

而由引理2可得,

從而有,

所以,

又因?yàn)?

所以,

綜上所述,定理得證.

3 結(jié) 論

對于工件有尺寸的同型機(jī)分批排序問題,我們采用3元素法將其表示為,pm│B,sj│Cmax,并對這一問題給出了一個近似比為,5/2-1/m,的離線算法.對于這一問題,若考慮工件有到達(dá)時間的離線情形,尋找其近似算法是下一步將要考慮的問題.

[1]Lee C,Uzsoy R,Martin V.EfficienL algorithms for scheduling semiconductor buming operations[J].Operations Research,1992, 40(1):764-755.

[2]Zhaohui Liu,Wenci Yu.Scheduling one batch processor subjecl to job release dales[J].Discrete Applied Mathematics,2000,105 (1):129-136.

[3]Brucker P,G ladky A,Hoogevreen H,et al.VandeVele Scheduling a batching machine[J].Journal of Scheduling,1998,1(1):31-54.

[4]Chandru V,Lee C Y,Uzsoy R.Minimizing the totle completion time on batch processing machine[J].International Journal of Production Research,1993,31(1):2097-2121.

[5]Zhang Guochuan,Cai Xiaoqiang.Minimizing makespan on a single batch processing machine with nonidentical job sizes[J].Naval Research Logistics,2001,48(1):222-240.

[6]張 鑫,劉景照,張玉忠.工件尺寸不同的平行機(jī)分批排序[J].曲阜師范大學(xué)學(xué)報,2005,31(3):10-12.