工件有尺寸的同型機分批排序問題

盧文麗,柏慶國

(1.淄博師范高等專科學校教育科學系,山東淄博 255100;2.曲阜師范大學運籌與管理學院,山東日照 276826)

0 引 言

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

1 工件有尺寸的分批排序

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

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

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

2 算法描述

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

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

2.1 算法A1

算法A1的具體步驟為:

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

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

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

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

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

2.2 算法A2

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

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

2.3 算法 FA

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

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

步驟2.設前l-1批已加工完,將第l批安排到最先出現空閑的機器上加工,l=1,2,…,k.

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

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

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

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

因此有,

從而有,

因此,

由引理1知,

而由引理2可得,

從而有,

所以,

又因為,

所以,

綜上所述,定理得證.

3 結 論

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

[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].曲阜師范大學學報,2005,31(3):10-12.