張 波 梁利東

(廣東科學(xué)技術(shù)職業(yè)學(xué)院1) 珠海 519090) (安徽工程科技學(xué)院2) 合肥 230009)

船廠開展中間產(chǎn)品專業(yè)化,不同中間產(chǎn)品任務(wù)包對(duì)應(yīng)不同的組合作業(yè)方案,作業(yè)人工分配的不同對(duì)于其生產(chǎn)工時(shí)產(chǎn)生直接影響,在中間產(chǎn)品作業(yè)過程中如何協(xié)調(diào)人工獲得合理工時(shí)具有實(shí)際意義.中間產(chǎn)品作業(yè)工時(shí)優(yōu)化涉及的變量多且作業(yè)關(guān)系復(fù)雜,屬有約束混合離散優(yōu)化問題,因此難以針對(duì)整個(gè)過程建立統(tǒng)一的優(yōu)化模型.目前關(guān)于造船工時(shí)的研究主要集中在中間產(chǎn)品定額工時(shí)及其工時(shí)物量之間關(guān)聯(lián)領(lǐng)域[1-3].本文基于遺傳算法及動(dòng)態(tài)規(guī)劃理論提出將中間產(chǎn)品嵌套作業(yè)的工時(shí)優(yōu)化問題分解為兩個(gè)嵌套層次建模并進(jìn)行工時(shí)優(yōu)化,通過實(shí)例計(jì)算,方法具可行性.

1 中間產(chǎn)品的組合作業(yè)、歸類及其工時(shí)問題分析

1.1 中間產(chǎn)品及其作業(yè)歸類

在造船系統(tǒng)中,中間產(chǎn)品是生產(chǎn)的作業(yè)單元,是對(duì)最終產(chǎn)品進(jìn)行作業(yè)任務(wù)分解的一個(gè)組成部分,也是逐級(jí)形成最終產(chǎn)品的組成部分.其內(nèi)容十分廣泛,既包括船體的分段、組件、部件和零件,也包括舾裝的托盤、模塊、單元和管件等.造船成組技術(shù)依據(jù)作業(yè)的相似特征,將種類繁多的中間產(chǎn)品分類成組,用相同的施工處理方法擴(kuò)大中間產(chǎn)品的成組批量,以建立批量的流水定位,從而提高造船生產(chǎn)率[4].以中間產(chǎn)品為對(duì)象進(jìn)行專業(yè)化造船,其作業(yè)過程及作業(yè)對(duì)象相對(duì)傳統(tǒng)造船更為固定,建立柔性流水線是中間產(chǎn)品專業(yè)化造船的實(shí)質(zhì).以柔性流水線的建立為對(duì)象,根據(jù)作業(yè)關(guān)聯(lián),中間產(chǎn)品建造的組合作業(yè)類型可以單元化為如下3類,見圖1～3所示.

圖1 串聯(lián)式作業(yè)

圖2 并聯(lián)式作業(yè)

圖3 嵌套式作業(yè)

1.2 中間產(chǎn)品的作業(yè)工時(shí)問題分析

其中,在實(shí)際建造過程中,多數(shù)中間產(chǎn)品的生產(chǎn)過程是上述3類單元作業(yè)的組合,而以上述3種作業(yè)形式單獨(dú)生產(chǎn)的中間產(chǎn)品比例很少.針對(duì)第1類串聯(lián)單元作業(yè)(各單元作業(yè)之間存在緊前開工與緊后開工關(guān)聯(lián)),網(wǎng)絡(luò)計(jì)劃法已經(jīng)能夠很好的根據(jù)不同作業(yè)的緊前及緊后關(guān)系對(duì)整個(gè)作業(yè)的最優(yōu)工時(shí)進(jìn)行求解;第2類并聯(lián)單元(各作業(yè)單元可以獨(dú)立開工不受其他作業(yè)影響)能夠以階段為單元基于傳統(tǒng)動(dòng)態(tài)規(guī)劃法進(jìn)行求解;第3類嵌套作業(yè)(子層各單元作業(yè)為并聯(lián)作業(yè)關(guān)系執(zhí)行完成后又與父層形成新的并聯(lián)作業(yè))包括多重并聯(lián)作業(yè)組合(圖示為2層),其工時(shí)優(yōu)化無法直接應(yīng)用相關(guān)工具及軟件求解,而該類作業(yè)在中間產(chǎn)品的生產(chǎn)過程中其比例最大,因此本文重點(diǎn)對(duì)第3類工時(shí)問題進(jìn)行優(yōu)化.

2 基于遺傳算法及動(dòng)態(tài)規(guī)劃法的嵌套并聯(lián)作業(yè)工時(shí)優(yōu)化

2.1 作業(yè)工時(shí)的基本概念及嵌套并聯(lián)作業(yè)工時(shí)優(yōu)化問題描述

總工時(shí)(T) 指某個(gè)作業(yè)施工所需的“工人數(shù)量×工人工作的時(shí)間”,對(duì)于一個(gè)作業(yè),從一定時(shí)期而言,由該作業(yè)的生產(chǎn)設(shè)備及方法決定,故不論其工人數(shù)量或工人作業(yè)時(shí)間怎么調(diào)整,這兩者的乘積認(rèn)為是不變的.

作業(yè)時(shí)間(t) 某個(gè)作業(yè)步驟完成所需絕對(duì)時(shí)間,一般來說,作業(yè)時(shí)間等于工人的實(shí)際工作時(shí)間.作業(yè)時(shí)間的研究對(duì)于控制該作業(yè)實(shí)際作業(yè)工時(shí)具有重要作用.

總工期(∑t) 各分段作業(yè)耗費(fèi)的總時(shí)間.總工期等于關(guān)鍵路徑上所有工序作業(yè)時(shí)間的總和.

典型嵌套并聯(lián)作業(yè)(以兩層嵌套為例)的工時(shí)優(yōu)化問題描述為如下

某工序i由隊(duì)伍A執(zhí)行完成,該隊(duì)伍有m個(gè)工人,工序i包括n項(xiàng)作業(yè)(每個(gè)人工均可執(zhí)行任意工序作業(yè)),其中1,2,…,n-j+1項(xiàng)作業(yè)構(gòu)成一個(gè)子工序,n-j+1,…,n為子工序獨(dú)立作業(yè)2≤j≤n-1,每項(xiàng)作業(yè)的總工時(shí)可按經(jīng)驗(yàn)獲得分別為 T1,T2,…,Tn,子工序及各作業(yè)之間無關(guān)聯(lián),均需從開工到完工結(jié)束,該工序才算完工,求該作業(yè)工序i作業(yè)時(shí)間最短的人工分配方案及作業(yè)工時(shí).

2.2 遺傳算法及動(dòng)態(tài)規(guī)劃方法在嵌套并聯(lián)作業(yè)中的應(yīng)用

2.2.1 遺傳算法在子層并聯(lián)作業(yè)的應(yīng)用 遺傳算法是一種廣泛用于求解尋優(yōu)問題的方法.它是按概率在解空間進(jìn)行搜索,因此能較為有效地避開局部極值,以較高的效率逼近全局最優(yōu)解.同時(shí),將待解決問題轉(zhuǎn)化為編碼序列問題,對(duì)設(shè)計(jì)變量和目標(biāo)函數(shù)要求少,因此適用面廣[5].

由前所述,典型的子層并聯(lián)作業(yè)可描述為m個(gè)工人在n項(xiàng)工作中的分配,各項(xiàng)工作的總工時(shí)T已知,要求由人工分配不同而形成所有作業(yè)共同完成工作時(shí)間最少的方案,優(yōu)化目標(biāo)為:t=min{max(ti)}.式中:ti為工作i的作業(yè)時(shí)間:i=1,2,…,n.

遺傳算法設(shè)計(jì) 將遺傳算法用于子層并聯(lián)作業(yè)的人工分配問題關(guān)鍵是采用有效的編碼和解碼方式以及適當(dāng)?shù)慕徊妗⒆儺惒僮?遺傳算法對(duì)種群重復(fù)地進(jìn)行選擇、交叉、變異等基本遺傳操作,不斷產(chǎn)生出比父代更適應(yīng)環(huán)境的新一代種群,直到滿足要求條件為止.

個(gè)體編碼 針對(duì)本文編碼有兩種.(1)直接編碼,以工序?yàn)閷?duì)象,將分配工人數(shù)作為碼值;(2)間接編碼,以工人為狀態(tài),將工人的分配作業(yè)作為狀態(tài),算法優(yōu)化結(jié)果即包括最短工時(shí),也包括各人工的分配狀態(tài),對(duì)每一位工人可以有n(作業(yè)數(shù))個(gè)編碼位選擇,僅選擇其中一位,不同工人的分配碼值構(gòu)成基因.相比較而言,后者的基因會(huì)因工人數(shù)的增多而變長(zhǎng),影響算法運(yùn)行,同時(shí),前者編碼方法也避免了同一工人在不同作業(yè)中的操作運(yùn)算產(chǎn)生死鎖現(xiàn)象,本文選擇前者編碼,以3個(gè)工人在4項(xiàng)作業(yè)中的2種分配方案為例:

n1 n2 n3 n4 m1 0 1 0 0 m2 1 0 0 0 m3 1 0 0 0 n1 n2 n3 n4 m1 0 1 0 0 m2 0 0 1 0 m3 1 0 0 0

獲得染色體編碼如下(以兩位二進(jìn)制碼構(gòu)成基因座,根據(jù)實(shí)際作業(yè)工人數(shù)調(diào)整二進(jìn)制碼位)

10 01 00 00 01 01 01 00

群體規(guī)模選擇:合適的群體規(guī)模對(duì)遺傳算法的收斂具有重要意義.群體太小難以求得滿意的結(jié)果,群體太大則計(jì)算復(fù)雜,根據(jù)經(jīng)驗(yàn),群體規(guī)模一般取10～160.

適值函數(shù):由于并行作業(yè)具獨(dú)立性,面向并行作業(yè)工人作業(yè)分配理論上可以有多種方式,如部分作業(yè)先不執(zhí)行,待部分作業(yè)完工后再進(jìn)行等,本文模型建立考慮最復(fù)雜的情況,假設(shè)n項(xiàng)并行作業(yè)經(jīng)過m個(gè)過程完成,其中(A1,A2,…Aa)k表示第k個(gè)作業(yè)組內(nèi)同時(shí)開工的作業(yè)項(xiàng)目,其中,0≤a,b,m≤n,m≥1各作業(yè)組的作業(yè)時(shí)間,故得到適值函數(shù)為

在造船過程中,由于工時(shí)及工序的固定性,多項(xiàng)并行工序多存在一次人工分配,盡管二次或者更多次的分配能夠進(jìn)一步優(yōu)化縮短工時(shí),但是對(duì)實(shí)際作業(yè)過程而言,其人工分配及調(diào)整相對(duì)煩瑣,多項(xiàng)并聯(lián)作業(yè)如果按照分工序進(jìn)行人工分配,其工序基本已經(jīng)限定,因此模型中本文選取m=1,即n項(xiàng)作業(yè)單獨(dú)作為一項(xiàng)工序優(yōu)化求其最短工時(shí),盡管將問題簡(jiǎn)化,但是可以在此基礎(chǔ)上對(duì)工廠實(shí)際并聯(lián)作業(yè)的多項(xiàng)工序分別進(jìn)行優(yōu)化,最后求其總和,結(jié)果趨近于最優(yōu)工時(shí),同時(shí)縮短了程序的運(yùn)行時(shí)間及操作過程.

選擇:選擇是用來確定重組或交叉?zhèn)€體,以及備選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體.選擇的第一步是計(jì)算適值,采用按比例的適應(yīng)度分配,是利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性.若有m個(gè)個(gè)體,其中某個(gè)個(gè)體i,其適值為fi,則其被選擇的概率表示為

然后對(duì)各個(gè)染色體計(jì)算其累積概率,如第k個(gè)個(gè)體的累積概率為

第二步用輪盤賭選擇法進(jìn)行選擇.為了選擇交配個(gè)體,需要進(jìn)行多輪選擇,每一輪產(chǎn)生一個(gè)[0,1]均勻隨機(jī)數(shù),將該隨機(jī)數(shù)作為選擇指針來確定備選個(gè)體.

交叉與變異:交叉在遺傳操作中起核心作用,交叉概率較大可增強(qiáng)遺傳算法開辟新搜索空間的能力,但性能好的基因串遭到破壞的可能性較大,算法收斂速度降低且不穩(wěn)定;若交叉概率較小,則遺傳算法搜索可能陷入遲鈍狀態(tài).本文采用循環(huán)交叉操作即對(duì)子個(gè)體中的代碼進(jìn)行順序調(diào)換(本文選擇3個(gè)碼串為一基點(diǎn)進(jìn)行相互調(diào)換)如圖4.遺傳算法的變異主要是為了保證其具有局部的隨機(jī)搜索能力和維持種群的多樣性.當(dāng)遺傳算子在接近最優(yōu)解時(shí),變異可以加速向最優(yōu)解的收斂,但當(dāng)已接近最優(yōu)解時(shí),也可能使最優(yōu)解遭到破環(huán),因此同時(shí)變異的概率應(yīng)取較小值.本問題的變異算子采用如下方法:在隨機(jī)選中染色體(個(gè)體串碼)當(dāng)中首先針對(duì)一個(gè)基點(diǎn)(即作業(yè)人員)增加一個(gè)單位,然后采用隨機(jī)原則,任選其他一個(gè)基點(diǎn)減少一個(gè)單位,即符合變異保證在全局范圍內(nèi),又保證了變異的前提條件即作業(yè)人員的總數(shù)不變,但對(duì)個(gè)體串碼而言實(shí)現(xiàn)了重排序操作,如圖5所示.

圖4 基因交叉過程

圖5 基因變異過程

2.2.2 動(dòng)態(tài)規(guī)劃法 動(dòng)態(tài)規(guī)劃法是研究多階段決策問題的數(shù)學(xué)方法,其原理概括為:無論過去的狀態(tài)和決策如何,對(duì)前面的決策所形成的狀態(tài)而言,余下的諸決策必須構(gòu)成最優(yōu)策略.因此,多階段決策問題的求解過程可看成一個(gè)連續(xù)遞推過程,由后向前逐步計(jì)算[6].

本文通過遺傳算法針首先對(duì)子層并聯(lián)作業(yè)交叉變異優(yōu)化獲得的不同人工分配方案及對(duì)應(yīng)的最優(yōu)工時(shí)后,將其作為一個(gè)階段與該工序內(nèi)其他的獨(dú)立作業(yè)構(gòu)成一族同類型的子問題,建立動(dòng)態(tài)規(guī)劃模型,再進(jìn)行逐個(gè)階段求解,以下為動(dòng)態(tài)規(guī)劃模型的建立.

階段變量 以n項(xiàng)作業(yè)來劃分階段,前述子層并聯(lián)作業(yè)在此視為其中一項(xiàng)作業(yè).

決策變量 uk為分配給第k階段的作業(yè)工人單位數(shù).

狀態(tài)變量 xk表示分配給第k至第n項(xiàng)作業(yè)的人工單位累計(jì)數(shù),顯然,x1=m;n-k+1≤xk≤m-k+1;k=2,3,…,n.

狀態(tài)轉(zhuǎn)移方程 xk+1=xk-uk.

允許決策集合 Dk(xk)={uk∣1≤uk≤min(xk,m-n+1)},uk為正整數(shù).

最優(yōu)指標(biāo)函數(shù) fk(xk)表示用 xk單位工人分配給第k至第n項(xiàng)作業(yè)時(shí),在各種決策方案下完成任務(wù)時(shí)間的最小值,得到動(dòng)態(tài)規(guī)劃基本方程

3 實(shí)例研究

本文以某船廠對(duì)一批“太古船”采用沉浮法改裝加長(zhǎng)的合攏工藝進(jìn)行工時(shí)優(yōu)化為研究對(duì)象.改裝方案是將原船在 81.5號(hào)肋位切斷,嵌入長(zhǎng)28.305 m的平行舯體,然后合攏.改裝內(nèi)容共有15個(gè)大項(xiàng)43個(gè)小項(xiàng),增加重量860～950 t.為提高改裝效率,要求對(duì)該船進(jìn)行工時(shí)優(yōu)化(見表1).其中,新增中部總段與原尾半條船合攏是其主要工序,工作量占整個(gè)船舶改裝作業(yè)的60%.對(duì)該節(jié)點(diǎn)的作業(yè)進(jìn)行工時(shí)控制是本文的主要目標(biāo),限于篇幅,本文以該工序的某組合作業(yè)(檢查縱向定位板、檢查合攏口兩端前后水尺及合攏工裝設(shè)備)為對(duì)象進(jìn)行案例優(yōu)化.

表1 太古船某工序的組合作業(yè)及其完工工時(shí)

由表1,該工序共有8項(xiàng)作業(yè),其中作業(yè)1,2,3,4屬于父層并聯(lián)作業(yè),四項(xiàng)作業(yè)之間無關(guān)聯(lián),可以獨(dú)立開工;5,6,7三項(xiàng)作業(yè)屬于子層(5,6,7子并聯(lián)作業(yè)完成后,再執(zhí)行8作業(yè)成為獨(dú)立作業(yè),本文用[(5,6,7),8]表示其關(guān)聯(lián)關(guān)系),故該工序的各項(xiàng)作業(yè)屬于2層嵌套并聯(lián)作業(yè),為便于優(yōu)化分析,分別設(shè)為獨(dú)立作業(yè)I(1),II(2),III(3),IV(4),V[(5,6,7),8].現(xiàn)已知該廠安排30名員工(10個(gè)班組)進(jìn)行該工序作業(yè),現(xiàn)要求對(duì)10個(gè)班組進(jìn)行合理分配,使完成該工序的作業(yè)時(shí)間最短.

優(yōu)化步驟一 針對(duì)5,6,7子層作業(yè)采用遺傳算法進(jìn)行優(yōu)化,計(jì)算其不同人工分配方案及對(duì)應(yīng)的最短工時(shí),由表一獲得已知數(shù)據(jù),設(shè)置種群規(guī)模為20,交叉概率 0.8,進(jìn)化次數(shù) 100,變異概率0.1,由VISUAL BASIC軟件編制程序得到優(yōu)化結(jié)果,見表2所列.

表2 子層作業(yè)的優(yōu)化結(jié)果

優(yōu)化步驟二 在獲得子層作業(yè)的不同分配小組方案及對(duì)應(yīng)最短作業(yè)工時(shí)的基礎(chǔ)上,采用動(dòng)態(tài)規(guī)劃計(jì)算I(1),II(2),III(3),IV(4),V(5,6,7)的最優(yōu)工時(shí)及人工分配方案,將第[(5,6,7),8]子層作業(yè)視為第五階段 V,得到各階段的 tk=tk(uk).其結(jié)果見表3.

表3 第5階段優(yōu)化結(jié)果

由上述計(jì)算可知:f5(u5)=t5(u5);u5=x5;3≤x5≤6,得出作業(yè)五的數(shù)據(jù)如表4所列.

表4 第5階段最優(yōu)指標(biāo)

依次得到,當(dāng)k=3時(shí),f3(5)=4,f3(6)=2.5,f3(7)=2.5,f3(8)=2;當(dāng) k=2 時(shí),f2(6)=4,f2(7)=3,f2(8)=2.5;當(dāng) k=1 時(shí),f1(x1)={max[t1(u1),f2(x1-u1)]},x1=10,得到f1(x1)=2.5.

通過優(yōu)化,得到該組合作業(yè)的最短完工時(shí)間是2.5 h.同時(shí)得到獲得最短完工的組合作業(yè)分配小組數(shù):u1*=2,u2*=2,u3*=1,u4*=2,u5*=1,=1=1.

4 結(jié) 束 語

本文針對(duì)造船過程中的嵌套并聯(lián)作業(yè)工時(shí)優(yōu)化及人工分配方案問題提出基于遺傳算法和動(dòng)態(tài)規(guī)劃法的解決方法,將嵌套并聯(lián)作業(yè)的子層視為父層相似階段,較為滿意的解決了工時(shí)優(yōu)化問題,通過實(shí)例驗(yàn)證了該方法的有效性,為造船工時(shí)及人工的控制提供決策支持.

[1]陳民俊,潘 斌,劉建峰.應(yīng)用BP網(wǎng)絡(luò)測(cè)算造船作業(yè)任務(wù)包定額工時(shí)[J].中國(guó)造船,2003,44(2):1-5.

[2]劉 濱,蔣祖華.船舶裝配作業(yè)工時(shí)智能估算技術(shù)[J].上海交通大學(xué)學(xué)報(bào),2005(12):20-24.

[3]趙 東,馬曉平,蔣志勇.船舶制造中的工時(shí)/物量數(shù)據(jù)統(tǒng)計(jì)分析系統(tǒng)研究[J].造船技術(shù),2003(2):8-10.

[4]高介估.現(xiàn)代造船工程[M].哈爾濱:哈爾濱工程大學(xué)出版社,1998.

[5] 陳國(guó)良,王煦法.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社,1996.

[6]馮 杰,黃力偉.數(shù)學(xué)建模原理與案例[M].北京:科學(xué)出版社,2006.