劉 恒, 張亞加, 邵樂樂, 邵建龍*

1.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院, 云南 昆明 650504;2.云南開放大學(xué), 云南 昆明 650500

隨著汽車行業(yè)的不斷發(fā)展,個(gè)性化、多品種的批量定制服務(wù)成為了競爭的焦點(diǎn)之一。在這種服務(wù)模式下,消費(fèi)者可以根據(jù)自身的喜好和需求,搭配出自己喜歡的顏色、車型和配置等,因此,提供個(gè)性化服務(wù)是提高顧客滿意度、滿足現(xiàn)代顧客多樣化需求的關(guān)鍵所在。然而,與傳統(tǒng)少品種的批量化生產(chǎn)模式不同,汽車產(chǎn)品的個(gè)性化訂制生產(chǎn)需要在同一條生產(chǎn)線上生產(chǎn)不同噴涂顏色、不同型號(hào)車身和配置不同零部件的汽車。這種多品種混流生產(chǎn)方式對(duì)汽車制造系統(tǒng)各個(gè)車間生產(chǎn)環(huán)節(jié)的軟硬件協(xié)調(diào)和硬件控制系統(tǒng)的響應(yīng)速度提出了很高的要求。

國內(nèi)外已有大量針對(duì)緩存區(qū)重排序問題的研究。Boysen等[1]以卡車生產(chǎn)過程為例,將緩存區(qū)重排序分為物理重排序和虛擬重排序兩種方式。其中,虛擬重排序不改變實(shí)際生產(chǎn)的車輛在加工序列中的位置,只將運(yùn)輸相同物料的車輛進(jìn)行生產(chǎn)序號(hào)的交換,物理重排序則需要將實(shí)際生產(chǎn)的車輛按照生產(chǎn)要求進(jìn)行重新排序。Gerrit等[2]將緩存區(qū)分為無限容量緩存區(qū)和有限容量緩存區(qū)兩類,其中,有限容量緩沖區(qū)又可分為先入先出型和自由進(jìn)出型兩類。然而,無限容量緩存區(qū)在現(xiàn)實(shí)場景中是無法實(shí)現(xiàn)的,具有自由進(jìn)出方式特點(diǎn)的有限容量緩沖區(qū)的調(diào)度方式對(duì)于硬件及空間的要求過高,難以被汽車生產(chǎn)商采用[3]。

針對(duì)緩存區(qū)提出的啟發(fā)式算法和智能優(yōu)化算法很多,如Muhl等[4]研究汽車在各個(gè)生產(chǎn)車間的擾動(dòng)和約束,針對(duì)緩存區(qū)重排序問題,提出了一種局部排序的方法,并使用啟發(fā)式算法求解。Bulgak等[5]提出將人工神經(jīng)網(wǎng)絡(luò)與遺傳算法結(jié)合的方法用于解決裝配生產(chǎn)線的最佳緩存區(qū)容量問題,以此最大化提高裝備效率。Hartmann等[6]將PBS重排序問題分解成顏色檢索和顏色存儲(chǔ)兩個(gè)子問題,并使用蟻群優(yōu)化算法求解,求解的結(jié)果優(yōu)于傳統(tǒng)基于規(guī)則的啟發(fā)式算法,但當(dāng)排產(chǎn)序列長度增加和所包含的顏色復(fù)雜時(shí),該求解算法不能保證最終求解效果。Boysen等[7]以涂裝車間和總裝車間的PBS緩存區(qū)平臺(tái)為研究對(duì)象,建立下游車間汽車排序目標(biāo)優(yōu)化模型。Boysen針對(duì)PBS入口介紹了基于特定規(guī)則的貪婪算法,接著使用一種改進(jìn)的蟻群優(yōu)化算法用于求解;針對(duì)PBS出口,作者將其歸納為最短路徑問題,同時(shí)提出基于啟發(fā)式的搜索算法用于求解。Moon等[8]提出在涂裝車間與總裝車間除了PBS之外再增加一個(gè)線性結(jié)構(gòu)緩存平臺(tái),并在該平臺(tái)中設(shè)置返回道以返回車輛。因?yàn)榫彺鎱^(qū)調(diào)度是一個(gè)組合優(yōu)化問題,需要在有限的時(shí)間內(nèi)對(duì)不同的訂單進(jìn)行排序,達(dá)到最大化生產(chǎn)效益,因此被歸類為NP-hard問題。

針對(duì)以上方法存在的不足,本文通過深入調(diào)研整車制造流程,以汽車制造涂裝-總裝緩存調(diào)序區(qū)(Painted Body Store,PBS)為研究對(duì)象,探討流水車間在生產(chǎn)過程中存在的調(diào)度優(yōu)化問題。

1 問題描述與假設(shè)

汽車整車生產(chǎn)的三大工藝流程為“焊裝-涂裝-總裝”,焊裝車間、涂裝車間和總裝車間每個(gè)生產(chǎn)車間都有自己的優(yōu)化排序目標(biāo),但它們存在上下游關(guān)聯(lián)關(guān)系。汽車的混流生產(chǎn)模式使得生產(chǎn)過程更復(fù)雜,因此生產(chǎn)管控的難度也隨之大大增加。這個(gè)問題在汽車的涂裝車間和總裝車間尤為突出,由于涂裝車間和總裝車間的生產(chǎn)序列差異較大,因此需要在兩生產(chǎn)車間之間增加一個(gè)具有調(diào)序功能的緩存區(qū),即汽車制造涂裝-總裝緩存調(diào)序區(qū)(PBS)(見圖1),用以將涂裝車間的出車序列調(diào)整到適應(yīng)總裝車間約束的進(jìn)車序列。

圖1 汽車制造涂裝-總裝緩存調(diào)序區(qū)示意圖

根據(jù)對(duì)汽車制造涂裝-總裝緩存調(diào)序區(qū)調(diào)度優(yōu)化問題進(jìn)行研究,統(tǒng)籌涂裝-總裝緩存調(diào)序區(qū)(PBS)的出車口、接/送橫移機(jī)、返回道停車位等,建立涂裝-總裝緩存調(diào)序區(qū)的優(yōu)化調(diào)度方案,用來將涂裝車間的出車序列調(diào)整到滿足總裝車間約束的進(jìn)車序列。首先要根據(jù)總裝車間的工位信息和汽車訂單信息,為總裝車間生成汽車車身序列,入站過程為總裝車間車身序列依次進(jìn)入PBS,得到入站矩陣,出站過程為PBS存儲(chǔ)的車身進(jìn)入涂裝車間,進(jìn)而得到出站矩陣。本文根據(jù)某車企一天生產(chǎn)的車輛進(jìn)行分析,每天上線生產(chǎn)的車輛的車型、顏色等屬性均有變化,這里主要研究車型,車型有A、B兩種,兩種車型又可以根據(jù)動(dòng)力和驅(qū)動(dòng)細(xì)分為混動(dòng)、燃油、兩驅(qū)、四驅(qū)?？紤]到動(dòng)力及驅(qū)動(dòng)列為“混動(dòng)”“兩驅(qū)”等漢字,需將其轉(zhuǎn)化為可用的整數(shù)形式,對(duì)車身的動(dòng)力及驅(qū)動(dòng)類型進(jìn)行相應(yīng)的編號(hào)處理,令0為燃油,1為混動(dòng),兩驅(qū)為0,四驅(qū)為1,便于后面數(shù)據(jù)的處理。

為了方便問題的求解,根據(jù)某車企所得出的優(yōu)化目標(biāo)及其權(quán)重系數(shù)(用于多目標(biāo)得分加權(quán),各權(quán)重系數(shù)相加等于1,此權(quán)重系數(shù)為最優(yōu))可設(shè)定以下假設(shè)條件:

1)送車橫移機(jī)不能將返回道的車身送入PBS-總裝接車口;

2)車身在進(jìn)車道和返回道的移動(dòng)方向?yàn)楣潭ǚ较?不可反方向前進(jìn);

3)同一車道內(nèi),多個(gè)車身在不同停車位上的移動(dòng)可以不同步;

4)車身在進(jìn)車道和返回道不同停車位之間的移動(dòng)過程中,不能被調(diào)度;

5)接車橫移機(jī)和送車橫移機(jī)在執(zhí)行任何動(dòng)作過程中,均不能被打斷;

6)混動(dòng)車型間隔2臺(tái)非混動(dòng)車型為優(yōu),權(quán)重系數(shù)0.4;

7)四驅(qū)車型與兩驅(qū)車型傾向1∶ 1出車序列,權(quán)重系數(shù)0.3;

8)返回道使用次數(shù)傾向于0,權(quán)重系數(shù)0.2;

9)傾向總調(diào)度時(shí)間越短越好,權(quán)重系數(shù)0.1。

2 汽車制造涂裝-總裝緩存調(diào)序區(qū)排序優(yōu)化模型

針對(duì)PBS排序問題,本文基于所建立的調(diào)序區(qū)排序優(yōu)化模型變量符號(hào)說明見表1,決策變量說明見表2。

表1 變量符號(hào)及其含義說明

表2 決策變量及其說明

目標(biāo)函數(shù)為

F=min(0.4f1+0.3f2+0.2f3+0.1f4),

假設(shè)在車身的進(jìn)、出車過程中,對(duì)于1—6進(jìn)車道,消耗時(shí)間分別為18、12、6、0、12、18 s;在車身的進(jìn)、出返回道過程中,對(duì)于1—6進(jìn)車道,消耗時(shí)間分別為24、18、12、6、12、18 s,可知選擇不同的進(jìn)車道,接、送車橫移機(jī)所花費(fèi)的時(shí)間是不同的,當(dāng)然接、送車橫移機(jī)花費(fèi)的時(shí)間越少對(duì)車間調(diào)度越有利。為達(dá)到使接、送車橫移機(jī)盡可能走近處的車道,引入進(jìn)車道優(yōu)先級(jí):

式中,l=(A1,A2,…,A5,A6,B)為車身進(jìn)、出車過程中所處通道,α1、α2、α3、α4為優(yōu)先級(jí)權(quán)重。由于A4通道所用時(shí)間最少,因此安排α1的優(yōu)先級(jí)權(quán)重最高,又權(quán)重必須滿足α1+α2+α3+α4=1,因此分配α1、α2、α3、α4的權(quán)重分別為0.4、0.3、0.2、0.1。

同理,為使返回時(shí)間最短,引入返回道優(yōu)先級(jí):

約束條件:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

式(1)表示t時(shí)刻車身只能在某一處區(qū)域(涂裝-PBS出車口、接車橫移機(jī)、進(jìn)車道任意停車位、返回道任意停車位、送車橫移機(jī)、PBS-總裝接車口)內(nèi);式(2)表示t時(shí)刻接車橫移機(jī)最多有一個(gè)車身;式(3)表示t時(shí)刻送車橫移機(jī)最多有一個(gè)車身;式(4)表示接車橫移機(jī)在完成任意動(dòng)作后,必須返回中間初始位置才可以執(zhí)行下一步動(dòng)作;式(5)表示送車橫移機(jī)在完成任意動(dòng)作后,必須返回中間初始位置才可以執(zhí)行下一步動(dòng)作;式(6)表示當(dāng)返回道10停車位有車身,同時(shí)接車橫移機(jī)空閑時(shí),優(yōu)先處理返回道10停車位上的車身;式(7)表示當(dāng)進(jìn)車道1停車位有車身等候,同時(shí)送車橫移機(jī)空閑時(shí),優(yōu)先處理最先到達(dá)1停車位的車身;式(8)表示進(jìn)車道每個(gè)時(shí)刻最多容納10個(gè)車身;式(9)表示返回道每個(gè)時(shí)刻最多容納10個(gè)車身;式(10)表示每個(gè)停車位最多容納1個(gè)車身;式(11)為0-1變量,表示當(dāng)?shù)趇與第(i+1)輛混動(dòng)車之間的非混動(dòng)車數(shù)量為2時(shí),qi為0,否則為1。

3 模型的求解

根據(jù)涂裝出車序列,綜合考慮PBS區(qū)域調(diào)度能力及限制,使得總裝進(jìn)車序列盡可能滿足總裝生產(chǎn)需求。建立混合整數(shù)規(guī)劃模型,使用粒子群優(yōu)化算法對(duì)所建立的模型進(jìn)行求解,得到優(yōu)化后的車身調(diào)度順序。求解思路如圖2所示。

圖2 模型求解流程圖

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是由J. Kennedy和R. C. Eberhart等于1995年開發(fā)的一種演化計(jì)算技術(shù),來源于對(duì)一個(gè)簡化社會(huì)模型的模擬。PSO和模擬退火算法相似,兩者均是從隨機(jī)解出發(fā),通過迭代來尋找最優(yōu)解。PSO比遺傳算法簡單,沒有“交叉”和“變異”的操作,通過粒子在當(dāng)前搜索到的最優(yōu)解來尋找全局的最優(yōu)解,這種算法具有容易實(shí)現(xiàn)、精度高并且收斂快的優(yōu)點(diǎn),因此本文選擇該算法求解模型。

粒子群優(yōu)化算法的迭代示意圖如圖3所示,運(yùn)算流程如圖4所示。

圖3 PSO算法迭代示意圖

圖4 PSO算法流程圖

4 結(jié)果分析

利用粒子群優(yōu)化算法對(duì)所建立的優(yōu)化模型進(jìn)行求解,得到優(yōu)化后的PBS調(diào)度收斂曲線如圖5所示。圖中可以看到,初始目標(biāo)函數(shù)值為60.9,通過PSO算法進(jìn)行優(yōu)化后的目標(biāo)函數(shù)值為59.2,在迭代70次左右后數(shù)據(jù)便趨于穩(wěn)定,可知所使用的算法能夠有效優(yōu)化目標(biāo)函數(shù),在車輛的排序調(diào)度中具有實(shí)價(jià)值。

圖5 數(shù)據(jù)調(diào)度的收斂曲線

優(yōu)化前后的進(jìn)車順序部分結(jié)果見表3。

表3 優(yōu)化前后的進(jìn)車順序

綜上,針對(duì)多目標(biāo)優(yōu)化問題,建立混合整數(shù)規(guī)劃模型,并使用粒子群優(yōu)化算法對(duì)所建立的模型進(jìn)行求解,能得到每連續(xù)兩輛混動(dòng)車身之間的非混動(dòng)車身數(shù)為2,出車序列中的四驅(qū)車型與兩驅(qū)車型之比為1∶ 1,能夠有效得到優(yōu)化后的PBS調(diào)度順序。

5 結(jié)語

本文針對(duì)汽車制造涂裝-總裝緩存調(diào)序區(qū)(PBS)問題進(jìn)行研究分析,通過某車企的數(shù)據(jù)以及優(yōu)化目標(biāo)建立了混合整數(shù)規(guī)劃模型,并利用某車企一天的生產(chǎn)車輛進(jìn)行可行性分析。基于此問題,提出了粒子群啟發(fā)式算法來求解該多目標(biāo)優(yōu)化模型,結(jié)果表明,該模型能夠良好地解決汽車制造涂裝-總裝緩存調(diào)序區(qū)(PBS)問題,并能夠得到合理的排序方案。較傳統(tǒng)的調(diào)度方案比較,本文所提出的優(yōu)化目標(biāo)方案能有效地提高調(diào)度效率。