朱 輝,楊立乾,趙金樓
(哈爾濱工程大學(xué) 經(jīng)濟(jì)管理學(xué)院,黑龍江 哈爾濱150001)
空間調(diào)度問題是一類同時(shí)考慮時(shí)間約束和空間約束的調(diào)度問題。該問題起源于船舶建造領(lǐng)域[1-2]。在現(xiàn)代船舶建造模式中,船舶以分段為單元進(jìn)行生產(chǎn)。如何安排分段的開工時(shí)間和在車間內(nèi)的加工位置,使其同時(shí)滿足時(shí)間約束和空間約束,并在建造車間內(nèi)形成最優(yōu)的動(dòng)態(tài)空間布局就是空間調(diào)度問題。在實(shí)際生產(chǎn)過程中,一個(gè)船體的上百個(gè)分段通常大小不一、形狀各異,并且時(shí)間約束也各不相同,這使得通過人工手段進(jìn)行空間調(diào)度更困難。因此,研究高效率、智能化的空間調(diào)度方法對(duì)提高船廠以及其他大型單件生產(chǎn)企業(yè)(如飛機(jī)制造、建筑業(yè)等)的生產(chǎn)效率和資源利用率有一定的現(xiàn)實(shí)意義。
目前,常用的空間調(diào)度問題解決方法包括啟發(fā)式算法、數(shù)學(xué)規(guī)劃方法和智能優(yōu)化算法。早期的研究主要基于啟發(fā)式算法。Lee等[1-2]最早對(duì)船舶分段空間調(diào)度問題進(jìn)行研究,提出了最大剩余空間利用策略、最大空閑矩形空間策略、初始定位策略、邊策略和混合策略等啟發(fā)式調(diào)度策略。Park等[3]基于部分枚舉和分解策略提出了一種調(diào)度方法,同時(shí),設(shè)計(jì)了一種簡(jiǎn)化空間布置和分段形狀的啟發(fā)式算法。Cho等[4]提出了一套針對(duì)分段涂裝作業(yè)的啟發(fā)式算法,包括操作策略算法、分段調(diào)度算法、分段布局算法和分段分配算法。Park等[5]拓展了Cho等[4]的研究,在其研究的基礎(chǔ)上加入了策略仿真。Shin等[6]定義了一種基于最下最左填滿策略的分段布局方法,并且提出了一種改進(jìn)的啟發(fā)式分段排序算法。郭美娜等[7]提出了一種基于樹搜索的動(dòng)態(tài)空間調(diào)度方法,在每個(gè)時(shí)間段內(nèi)使用局部啟發(fā)調(diào)度算法進(jìn)行空間布置搜索。張志英等[8]基于時(shí)間和空間綜合分解方法,將復(fù)雜的動(dòng)態(tài)空間調(diào)度問題分解為若干短周期和單作業(yè)平臺(tái)上調(diào)度子問題。聶蘭順等[9]在配置空間理論的基礎(chǔ)上提出了基于任務(wù)優(yōu)先級(jí)和啟發(fā)式空間布局規(guī)劃的單場(chǎng)地空間調(diào)度算法。啟發(fā)式算法便于理解,易于實(shí)現(xiàn),但是都是基于經(jīng)驗(yàn)及工況環(huán)境提出的,針對(duì)性較強(qiáng),且難以獲得最優(yōu)解。因此,也有學(xué)者采用數(shù)學(xué)規(guī)劃方法解決空間調(diào)度問題。Raj等[10]采用線性規(guī)劃方法解決分段空間調(diào)度問題,并同時(shí)考慮了開工時(shí)間和順序約束。接著,Raj等[11]針對(duì)分段空間調(diào)度問題建立了混合整數(shù)規(guī)劃模型并使用CPLEX進(jìn)行求解。Garcia等[12]做了和文獻(xiàn)[11]相似的工作并將模型擴(kuò)展至多場(chǎng)地的情況。Kwon等[13]考慮負(fù)載均衡、對(duì)稱分段、分段分配等因素,建立了分段空間調(diào)度的混合整數(shù)規(guī)劃模型并嘗試使用Lingo求解。張志英等[14]以場(chǎng)地平均時(shí)空利用率為目標(biāo),構(gòu)建了考慮加工優(yōu)先順序、交貨期等因素的非線性規(guī)劃模型。雖然數(shù)學(xué)規(guī)劃方法能夠獲得最優(yōu)解,但其只考慮分段間的相對(duì)時(shí)空位置,并且已被證明只能求解小規(guī)模問題。智能優(yōu)化算法是一種求解空間調(diào)度問題的新思路。Varghese等[15]應(yīng)用遺傳算法和最下最左定位策略實(shí)現(xiàn)了船舶分段空間調(diào)度,但沒有考慮分段的旋轉(zhuǎn)。Koh等[16]應(yīng)用遺傳算法產(chǎn)生分段的調(diào)度序列,然后根據(jù)各個(gè)分段的最晚開工時(shí)間在空間維上按照最左最右策略布局,但其實(shí)質(zhì)是一維空間布局方法。Hu等[17]提出一個(gè)兩階段算法,采用模擬退火算法對(duì)分段的調(diào)度序列進(jìn)行優(yōu)化,采用最下最左填滿策略對(duì)分段進(jìn)行空間布局,但沒有編程實(shí)現(xiàn)算法,算法驗(yàn)證過程較為簡(jiǎn)單。張志英等[18]提出了一種改進(jìn)粒子群算法的空間調(diào)度方法,同樣利用智能優(yōu)化算法對(duì)分段進(jìn)行排序,利用啟發(fā)式策略對(duì)分段進(jìn)行布局。馬少輝等[19-20]分別針對(duì)矩形分段和不規(guī)則分段利用遺傳算法優(yōu)化調(diào)度順序,并提出平均最大空閑矩形策略進(jìn)行空間布局。
本文在上述文獻(xiàn)的基礎(chǔ)上,以時(shí)空利用率最大化為目標(biāo),建立了空間調(diào)度問題的混合整數(shù)規(guī)劃模型,提出了基于優(yōu)先規(guī)則的兩階段混合調(diào)度算法。第1階段在優(yōu)先規(guī)則的基礎(chǔ)上采用禁忌搜索算法生成可行的分段調(diào)度序列。第2階段采用啟發(fā)式定位算法——最下最左填滿(bottom left-fill,BLF)策略將分段按調(diào)度順序布局在車間內(nèi),算出該調(diào)度方案的時(shí)空利用率,回調(diào)至第1個(gè)階段的算法繼續(xù)尋優(yōu),直到找到最優(yōu)解。以某船廠實(shí)際分段數(shù)據(jù)為例,驗(yàn)證模型的合理性和算法的有效性。
空間調(diào)度問題可以描述為:在一定的調(diào)度周期T內(nèi),將N個(gè)待建造的分段按照一定的調(diào)度順序布局在建造車間內(nèi),以達(dá)到最優(yōu)的動(dòng)態(tài)空間布局。調(diào)度過程中需要同時(shí)滿足分段建造的時(shí)間約束和空間約束,另外還要確保分段建造車間空間利用的連續(xù)性。時(shí)間約束是指分段的實(shí)際開工時(shí)間必須介于最早開工時(shí)間和最晚開工時(shí)間之間,并且應(yīng)該在交貨期之前完工??臻g約束是指在同一時(shí)刻,車間每個(gè)位置上只能建造一個(gè)分段,各個(gè)分段之間不能交叉和堆疊,也不能超出建造車間的邊界;分段在加工周期內(nèi)不能移動(dòng)位置,直至完工才能被移出建造車間,騰出的空間可以被重復(fù)使用。
由于分段之間在豎直方向上不能堆疊,且建造車間的高度一般足夠高,所以在調(diào)度的過程中不需要考慮分段和建造車間的高度約束[2,5]。因此,分段在建造車間內(nèi)的布局問題類似于動(dòng)態(tài)二維裝箱問題,即分段的水平投影在建造車間平面上的動(dòng)態(tài)布局問題。根據(jù)船廠實(shí)際情況,分段建造車間可以看作長(zhǎng)為L(zhǎng)、 寬為W的矩形;分段的形狀取其在平面投影的最小包絡(luò)矩形,并選其左下角點(diǎn)為定位的參考點(diǎn),如圖1所示。
圖1分段最小包絡(luò)矩形和定位參考點(diǎn)Figure 1 Minimum enclosure rectangle and locating reference points
本文借鑒文獻(xiàn)[11]和文獻(xiàn)[12]中空間調(diào)度問題的建模方法,建立了如下混合整數(shù)規(guī)劃模型。
考慮到空間調(diào)度問題的特點(diǎn)和可處理性,并在不影響調(diào)度效果的前提下,進(jìn)行如下假設(shè)。
1)分段建造車間和分段的形狀均為矩形。
2)分段被布置到車間并開工后,不能被移動(dòng),直至分段加工完成后才能移出車間。
3)在布置分段的時(shí)候,分段有 0°和 90°2個(gè)旋轉(zhuǎn)方向。 0°是指分段的長(zhǎng)邊與建造車間的長(zhǎng)邊平行,90°是指分段的長(zhǎng)邊與建造車間的長(zhǎng)邊垂直,如圖2所示。
圖2分段在建造車間的放置角度Figure 2 Blocks at angles of 0°and 90°
4)考慮分段的最早開工時(shí)間、最晚開工時(shí)間、交貨期等時(shí)間約束,但不考慮分段之間的工藝約束。
5)非空間資源(如人員、設(shè)備等)充足。
索引符號(hào):待建造分段總數(shù)為N,待建造分段集合為J,J={1,2,···,N};分段編號(hào)分別為i和j,分段i和 分段j之間的位置關(guān)系為i j。
孟子武德觀念中以道抗勢(shì)、對(duì)于現(xiàn)實(shí)功利的拒斥,使其上升成為不因現(xiàn)實(shí)環(huán)境而動(dòng)搖的理想信念,具有為法家、縱橫家所不及的歷史眼光:
模型輸入:一個(gè)足夠大的數(shù)M,分段i的長(zhǎng)度、寬度和加工周期分別為li、wi和 pti;分段i的最早開工時(shí)間和最晚開工時(shí)間分別為 esti和 lsti;分段建造車間的長(zhǎng)度和寬度分別為L(zhǎng)和W;所有分段的計(jì)劃調(diào)度周期為T。
模型輸出:分段i參考點(diǎn)的橫坐標(biāo)為xi和縱坐標(biāo)為yi,分段i的開工時(shí)間為 sti,以及0-1決策變量分別為li j,ri j,fi j,bi j,ui j,vi j, roti。如果分段i布置在分段j的左邊,則li j=1, 否則,li j=0;如果分段i布置在分段j的右邊,則ri j=1, 否則,ri j=0;如果分段i布置在分段j的前邊,則fi j=1,否則,fi j=0;如果分段i布置在分段j的后邊,則bi j=1,否則bi j=0;如果分段i的開工時(shí)間早于分段j,則ui j=1,否則,ui j=0;如果分段i的開工時(shí)間晚于分段j,則vi j=1, 否則,vi j=0;如果分段i的長(zhǎng)邊垂直于建造車間的長(zhǎng)邊,則r oti=1,否則 r oti=0。
該模型以最大化時(shí)空利用率為優(yōu)化目標(biāo),如式(1)所示,其中,m ax(sti+pti)為真實(shí)的調(diào)度周期。
其中,約束(2)和(3)表示所有分段不能超過建造車間的物理邊界;約束(4)表示所有分段的完工時(shí)間不能晚于計(jì)劃的調(diào)度周期;約束(5)表示所有分段的開工時(shí)間必須介于最早開工時(shí)間和最晚開工時(shí)間之間;約束(6)~(9)表示同時(shí)處于建造車間內(nèi)的任意兩個(gè)分段在物理空間內(nèi)不能重疊;約束(10)和(11)表示處于同一平面位置的任意2個(gè)分段在時(shí)間維度上不能有重疊;約束(12)表示約束(6)~(11)至少有一個(gè)成立;約束(13)表示分段的定位點(diǎn)坐標(biāo)及開工時(shí)間非負(fù);約束(14)是0-1約束。
文獻(xiàn)[10-14]已經(jīng)證明空間調(diào)度問題是NP-hard問題。雖然混合整數(shù)規(guī)劃方法能夠獲得該問題的最優(yōu)解,但其只適用于規(guī)模較小的問題。實(shí)踐中多采用啟發(fā)式算法或智能優(yōu)化算法求解大規(guī)模的空間調(diào)度問題。由式(1)可知,優(yōu)化目標(biāo)是最大化分段車間的時(shí)空利用率。對(duì)于給定的一組分段,當(dāng)時(shí)空利用率取得最大值時(shí), max(sti+pti)取得最小值。即,可將優(yōu)化目標(biāo)從最大化時(shí)空利用率轉(zhuǎn)換為最小化完工時(shí)間。優(yōu)先規(guī)則是求解最小化完工時(shí)間的一個(gè)常用方法[21-24],如文獻(xiàn)[19-20]考慮到實(shí)際調(diào)度中希望所有分段的加工周期越短越好,所以將分段按照最早開工時(shí)間升序排序產(chǎn)生初始調(diào)度序列;文獻(xiàn)[9]和文獻(xiàn)[25]將分段的實(shí)際開工時(shí)間和最早開工時(shí)間的差值定義為延期時(shí)間,并將分段按延期時(shí)間降序排序,優(yōu)先調(diào)度延期時(shí)間長(zhǎng)的分段;文獻(xiàn)[13]將交貨期減去加工時(shí)間再減去最早開工時(shí)間定義為緊急程度,并將分段按緊急程度降序排序,優(yōu)先調(diào)度緊急程度高的分段;文獻(xiàn)[26]的研究與文獻(xiàn)[13]的研究類似。本文借鑒上述文獻(xiàn)的研究思路,并依據(jù)空間調(diào)度的實(shí)際需求,提出了一種確定分段調(diào)度順序的雙重優(yōu)先規(guī)則。
優(yōu)先規(guī)則1將所有待調(diào)度的分段按照最早開工時(shí)間進(jìn)行升序排序,優(yōu)先調(diào)度最早開工時(shí)間較小的分段。
優(yōu)先規(guī)則2針對(duì)最早開工時(shí)間相同的分段,定義最晚開工時(shí)間和最早開工時(shí)間的差值為其關(guān)鍵程度。差值越小,說(shuō)明該分段越關(guān)鍵,應(yīng)優(yōu)先調(diào)度。
基于上述優(yōu)先規(guī)則,進(jìn)一步設(shè)計(jì)了禁忌搜索算法和啟發(fā)式布局算法相結(jié)合的兩階段求解算法,即“一維排序+二維空間布局”。算法的整體流程如圖3所示。該算法的總體思路:通過優(yōu)先規(guī)則和禁忌搜索算法產(chǎn)生分段的調(diào)度序列,由啟發(fā)式定位策略將分段按調(diào)度順序進(jìn)行空間布局,再經(jīng)禁忌搜索算法不斷調(diào)整調(diào)度序列,最終得到滿意解。
根據(jù)優(yōu)先規(guī)則1和優(yōu)先規(guī)則2,對(duì)于任意的2個(gè)分段,當(dāng)其最早開工時(shí)間和關(guān)鍵程度均相同時(shí),它們的調(diào)度順序是可變的。不同的調(diào)度順序會(huì)產(chǎn)生不同的空間布局。因車間的空間資源有限,并非所有的分段都會(huì)按其最早開工時(shí)間開工。某個(gè)分段因車間空間不足而無(wú)法按最早開工時(shí)間開工時(shí)就會(huì)被推遲開工,從而影響整體的完工時(shí)間。故,需要在優(yōu)先規(guī)則的基礎(chǔ)上進(jìn)一步采用禁忌搜索算法對(duì)分段的調(diào)度順序進(jìn)行優(yōu)化。算法的詳細(xì)設(shè)計(jì)過程如下。
1)編碼方式。使用一組表示分段ID的序列進(jìn)行編碼,每個(gè)編碼序列代表一個(gè)調(diào)度序列。例如,有8個(gè)分段,其ID分別為1、2、3、4、5、6、7、8,則(2,5,8,1,4,3,6,7)就是一個(gè)合法的編碼序列,代表了一個(gè)可行的分段調(diào)度序列。
圖3算法流程Figure 3 Flow diagrams of algorithm
2)解碼方式。解碼是指把分段的調(diào)度序列還原成在車間的布局圖形。即按照一定的定位規(guī)則,將代表分段的小矩形布局在代表建造車間的大矩形內(nèi),使空間布局最優(yōu)。本文采用最下最左填滿(BLF)策略進(jìn)行解碼,具體過程見3.2節(jié)。
3)適值函數(shù)。如上文所述,采用最小化完工時(shí)間作為算法的適值函數(shù)。
4)初始解。先將所有分段按最早開工時(shí)間進(jìn)行升序排序。對(duì)于最早開工時(shí)間相同的分段,再根據(jù)分段的關(guān)鍵程度,即l sti-esti進(jìn)行升序排序。若某些分段的最早開工時(shí)間和關(guān)鍵程度均相同,則將這些分段隨機(jī)排序,從而產(chǎn)生一個(gè)初始解xint。
5)鄰域移動(dòng)規(guī)則。對(duì)于任意2個(gè)分段,只有當(dāng)其最早開工時(shí)間和關(guān)鍵程度均相同時(shí),才可以進(jìn)行順序交換,產(chǎn)生新的調(diào)度序列;若2個(gè)分段的最早開工時(shí)間和關(guān)鍵程度有一個(gè)不同則不可交換調(diào)度順序。例如,在調(diào)度序列(2,5,8,1,4,3,6,7)中,分段1和分段4的最早開工時(shí)間和關(guān)鍵程度均相同,則它們可以交換調(diào)度順序,如圖4所示。
6)禁忌對(duì)象和禁忌長(zhǎng)度。最早開工時(shí)間和關(guān)鍵程度均相同的2個(gè)分段之間調(diào)度順序的變化即為禁忌對(duì)象;可將一組待調(diào)度分段按最早開工時(shí)間進(jìn)一步分為k個(gè)小組,設(shè)每個(gè)小組中關(guān)鍵程度相同的分段數(shù)量分別為m1,m2,···,mk-1,mk,則該算法的禁忌長(zhǎng)度可以定義為其中,為組合數(shù)。
圖4禁忌搜索算法的鄰域移動(dòng)Figure 4 The neighborhood move of Taboo search algorithm
7)特赦準(zhǔn)則。采用基于適值函數(shù)的特赦準(zhǔn)則,設(shè)xbest是歷史最優(yōu)解,xnow是候選集中出現(xiàn)的一個(gè)解,當(dāng)f(xnow)<f(xbest)時(shí),即使從xbest到xnow的移動(dòng)是被禁忌的,也令xbest:=xnow,即將xnow賦 值給xbest。
8)停止準(zhǔn)則。當(dāng)適值函數(shù)連續(xù)未得到改善的步數(shù)達(dá)到100時(shí)停止迭代,算法結(jié)束。
最下最左填滿策略由Chazelle[27]在最下最左(bottom-left,BL)策略的基礎(chǔ)上提出,并被證明是一種比BL策略更為有效的空間定位算法[28]。BLF策略可以描述為:將布局空間內(nèi)所有空域的左下角點(diǎn)組成待搜索點(diǎn)集合;從最下的待搜索點(diǎn)開始搜索,將待布局對(duì)象放置在該布局點(diǎn);如果該待布局對(duì)象和已布局對(duì)象(包括布局空間邊界)不存在重疊,則將其布置在該點(diǎn)右側(cè)的空域,并更新待搜索點(diǎn)集合;如果存在重疊,則向左依次搜索剩余的待搜索點(diǎn),直到待布局對(duì)象可以被放置在布局空間內(nèi),如圖5所示。
圖5 BLF定位策略Figure 5 BLF location strategy
以BLF定位策略為基礎(chǔ),結(jié)合分段調(diào)度的實(shí)際需求設(shè)計(jì)了分段空間定位算法,具體流程如下。
步驟1對(duì)于給定的一組分段,由3.1節(jié)的算法可以確定其調(diào)度序列為g={g1,g2,···,gN},其中g(shù)i∈J代表某一分段。
步驟2從g1開始,按照BLF定位策略對(duì)其進(jìn)行布局,若在第一個(gè)搜索點(diǎn)布局不成功,則將分段旋轉(zhuǎn) 90°后繼續(xù)布局,若仍不成功,則轉(zhuǎn)向下一個(gè)搜索點(diǎn),若所有搜索點(diǎn)都無(wú)法布局成功,則將g1的開工時(shí)間推遲1 d。
步驟3按照步驟2布置下一個(gè)分段,直到所有分段布置完成,并計(jì)算最終的完工時(shí)間。
為驗(yàn)證本文空間調(diào)度算法的有效性,選取某船舶企業(yè)的實(shí)際分段數(shù)據(jù)進(jìn)行計(jì)算分析。分段建造車間的長(zhǎng)度L=195 m,寬度W=30 m;分段數(shù)量N=44,對(duì)應(yīng)2009年10月的調(diào)度計(jì)劃,部分分段的尺寸及時(shí)間約束數(shù)據(jù)如表1所示。為便于分析,假設(shè)開工前車間為空。這是實(shí)際生產(chǎn)中的一個(gè)特例,但并不影響對(duì)所提出的算法進(jìn)行驗(yàn)證和比較。
表1部分分段數(shù)據(jù)Table 1 The data of blocks(partial)
本文以C++為編程語(yǔ)言,實(shí)現(xiàn)了該空間調(diào)度算法。表2列出了該算法的部分調(diào)度結(jié)果。同時(shí),計(jì)算出了完工時(shí)間、延遲開工的分段數(shù)量和建造車間每天的空間利用率。在本實(shí)例中,完工時(shí)間為36 d,延遲開工的分段數(shù)量為1個(gè),建造車間每天的空間利用率如圖6所示。由圖6可知,建造車間的平均空間利用率為54.11%,車間的空間利用率于2009年10月24日達(dá)到最大,為73.32%,該日車間內(nèi)的分段布局情況如圖7所示。
圖6建造車間每天的日空間利用率Figure 6 Space utilization ratio(every day)
圖7 2009年10月24日車間內(nèi)的分段布局情況Figure 7 The layout situation on the day of Oct.24, 2009
為了進(jìn)一步驗(yàn)證本文算法的有效性,對(duì)比了3種算法的實(shí)驗(yàn)結(jié)果,如表3所示。其中,算法1為本文算法,算法2是優(yōu)先規(guī)則1和優(yōu)先規(guī)則2結(jié)合的啟發(fā)式算法(與算法1相比,缺少禁忌搜索部分);算法3是算法2的進(jìn)一步簡(jiǎn)化,僅使用優(yōu)先規(guī)則1(最早開工時(shí)間)對(duì)分段進(jìn)行排序。而上述3種算法的定位策略相同,都是BLF策略。
表3不同算法結(jié)果對(duì)比Table 3 The results of different algorithms
由表3可知,本文算法在平均空間利用率、最大空間利用率、完工時(shí)間和延遲開工的分段數(shù)量等性能指標(biāo)上均最優(yōu)。與算法2和算法3相比,本文所提算法運(yùn)用了雙重優(yōu)先規(guī)則,充分考慮了空間調(diào)度問題的實(shí)際情況;同時(shí),將啟發(fā)式的優(yōu)先規(guī)則與禁忌搜索算法(智能算法)結(jié)合使用,兼顧了算法的收斂速度和尋優(yōu)能力,從而能夠更好地解決空間調(diào)度問題。
本文以船舶分段建造為背景,研究了動(dòng)態(tài)空間調(diào)度問題,對(duì)其建立了混合整數(shù)規(guī)劃模型;提出了基于優(yōu)先規(guī)劃的兩階段混合調(diào)度算法。該算法的創(chuàng)新之處在于將啟發(fā)式優(yōu)先規(guī)則與智能化的禁忌搜索算法結(jié)合使用,兼顧了算法的收斂速度和尋優(yōu)能力。實(shí)例分析表明該算法能夠得到比較理想的調(diào)度結(jié)果,并在平均空間利用率、最大空間利用率、完工時(shí)間和延遲開工的分段數(shù)量等性能指標(biāo)上均優(yōu)于純啟發(fā)式優(yōu)先規(guī)則。下一步研究包括:1)探索多場(chǎng)地動(dòng)態(tài)空間調(diào)度問題;2)根據(jù)船廠的實(shí)際情況,總結(jié)求解空間調(diào)度問題的常用優(yōu)先規(guī)則,并探究不同優(yōu)先規(guī)則的適用性及優(yōu)劣性。