工件有尺寸的同型機(jī)分批排序問(wèn)題

盧文麗,柏慶國(guó)

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

0 引 言

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

1 工件有尺寸的分批排序

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

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

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

2 算法描述

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

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

2.1 算法A1

算法A1的具體步驟為:

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

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

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

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

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

2.2 算法A2

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

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

2.3 算法 FA

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

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

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

張?chǎng)蔚萚6]證明了如下引理成立.

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

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

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

因此有,

從而有,

因此,

由引理1知,

而由引理2可得,

從而有,

所以,

又因?yàn)?

所以,

綜上所述,定理得證.

3 結(jié) 論

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

[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é)報(bào),2005,31(3):10-12.