汽車涂裝中虛擬重排序問(wèn)題建模與求解

張 光 前， 何 曉 飛

(大連理工大學(xué) 經(jīng)濟(jì)管理學(xué)院，遼寧 大連 116024)

0 引 言

在汽車涂裝時(shí)，當(dāng)兩個(gè)即將面漆的車身噴不同顏色時(shí)，噴頭必須重新清洗.為避免噴槍清洗以及更換涂料等過(guò)程所引發(fā)的高昂切換成本[1]，涂裝車間希望相同顏色的車身盡量排在一起.通常，從上一車間出來(lái)的車身序列無(wú)法自然地滿足這一要求，需對(duì)進(jìn)入的車身序列進(jìn)行一定調(diào)整，盡量滿足涂裝車間對(duì)車身序列的要求.這就形成了汽車涂裝中的重排序問(wèn)題.在汽車生產(chǎn)中，不同車間對(duì)車身序列的要求也各不相同，因此重排序問(wèn)題普遍存在于汽車生產(chǎn)過(guò)程中.

重排序模式有兩種：帶緩沖區(qū)的物理重排序(physical re-sequencing)和不帶緩沖區(qū)的虛擬重排序(virtual re-sequencing)[2-3].物理重排序是通過(guò)設(shè)置緩沖區(qū)(buffer)來(lái)調(diào)整序列，重排序后的個(gè)體在序列中的位置會(huì)發(fā)生改變.在虛擬重排序中，個(gè)體在序列中的位置不變，發(fā)生變化的是分配到個(gè)體上的屬性，以此實(shí)現(xiàn)序列重排.本文關(guān)注的是虛擬重排序問(wèn)題.

Epping等[4]將需要涂裝的車身序列看成是由一串有色字母組成的單詞，通過(guò)置換相同的字母得到一個(gè)顏色變化次數(shù)最少的單詞(paint shop problem for words，PPW)，并采用動(dòng)態(tài)規(guī)劃的方法求解了該問(wèn)題.Epping等也證明涂裝的虛擬重排序問(wèn)題是NPC(NP-complete)問(wèn)題.隨后，一些學(xué)者對(duì)PPW問(wèn)題進(jìn)行了研究，如對(duì)PPW問(wèn)題的一種特殊情況，即二元PPW問(wèn)題，Bonsma等[5]探討了該問(wèn)題的下界；Andres等[6]得出了二元PPW問(wèn)題顏色轉(zhuǎn)換的期望值；Gorbenko等[7]提出了PPW(2，1)問(wèn)題求解算法.Inman等[8]研究了按單裝配(assemble to order，ATO)敏捷系統(tǒng)中位于涂裝車間前和總裝車間前的虛擬重排序問(wèn)題，證明了在噴漆前后解耦和重新分配訂單可以顯著提高敏捷組裝-訂購(gòu)系統(tǒng)的性能.Ribeiro等[9]綜合考慮了噴涂和裝配兩個(gè)階段的要求對(duì)車身進(jìn)行排序，通過(guò)設(shè)立啟發(fā)規(guī)則并結(jié)合tabu搜索，建立了車身排序問(wèn)題的求解算法，并用數(shù)值試驗(yàn)進(jìn)行了驗(yàn)證.Gavranovi[10]針對(duì)汽車涂裝排序問(wèn)題，建立了貪心算法和本地搜索相結(jié)合的求解算法，得到該顏色排序問(wèn)題的近似解.黃剛等[11]介紹了實(shí)際生產(chǎn)中汽車涂裝的虛擬重排序問(wèn)題，給出了涂裝問(wèn)題顏色轉(zhuǎn)換計(jì)數(shù)表達(dá)式，并用遺傳算法(genetic algorithm)解決了車身排序問(wèn)題，通過(guò)算例驗(yàn)證了算法的有效性.Sun等[3，12]提出了物理重排序和虛擬重排序相結(jié)合來(lái)解決汽車涂裝問(wèn)題思路，并針對(duì)不同情形提出了相應(yīng)的啟發(fā)式算法，數(shù)值試驗(yàn)表明了這些算法的性能和有效性.Estellon等[13]針對(duì)車身排序問(wèn)題設(shè)計(jì)了兩個(gè)搜索算法，并通過(guò)數(shù)值試驗(yàn)做了對(duì)比分析.Elahi等[14]針對(duì)通用汽車涂裝車間傳送系統(tǒng)，把離散事件仿真和決策優(yōu)化相結(jié)合進(jìn)行排序決策.

可見，目前虛擬重排序問(wèn)題的研究焦點(diǎn)體現(xiàn)在建模和求解兩個(gè)方面.由于虛擬重排序是NPC問(wèn)題，導(dǎo)致現(xiàn)有關(guān)于虛擬重排序的模型通常較為復(fù)雜，有時(shí)甚至不能建立完整的數(shù)學(xué)模型；模型也無(wú)一例外地需要設(shè)計(jì)專門解法進(jìn)行求解或采用智能算法求近似解.

本文針對(duì)汽車涂裝涉及的虛擬重排序問(wèn)題，建立相對(duì)易于得到解析解的數(shù)學(xué)模型，使研究成果更接近實(shí)際應(yīng)用，同時(shí)也探討關(guān)于問(wèn)題規(guī)模增大所帶來(lái)的求解困難的解決方向.

1 問(wèn)題描述及符號(hào)設(shè)定

在涂裝車間需要對(duì)白車身進(jìn)行涂漆.白車身是指已完成焊裝工序但尚未面漆的汽車車身.若進(jìn)入涂裝車間的白車身有5種類型，分別用字母A、B、C、D、E表示；需要噴涂的顏色有兩種，分別用1和2表示.若進(jìn)入涂裝車間的白車身順序?yàn)閧A，C，D，A，B，C，C，E，D，B，A，E}.根據(jù)訂單，這些白車身需要在涂裝車間涂裝的顏色分別為{2，1，2，1，1，2，2，2，2，2，1，1}，則進(jìn)入涂裝車間的車身序列為{A2，C1，D2，A1，B1，C2，C2，E2，D2，B2，A1，E1}.若直接按此序列進(jìn)行噴涂，則噴頭顏色需要變化5次.若對(duì)同型車身進(jìn)行顏色互換，如把序列中車型同為A的兩個(gè)車身顏色互換，則會(huì)使該序列的前兩個(gè)車身都為顏色1.這種調(diào)整未實(shí)質(zhì)性改變客戶訂單，但噴涂顏色轉(zhuǎn)換次數(shù)可能會(huì)減少，從而達(dá)到總的顏色轉(zhuǎn)換次數(shù)最少的要求.由于在此過(guò)程中沒有用到緩沖區(qū)，此即車身涂裝的虛擬重排序問(wèn)題.

為了便于問(wèn)題描述和建模，對(duì)本文所用符號(hào)說(shuō)明如下：一般地，給定一個(gè)初始序列{N}，共有n個(gè)個(gè)體，每個(gè)個(gè)體同時(shí)擁有兩種屬性，其中第1種屬性有p個(gè)屬性值，第2種屬性有q個(gè)屬性值.對(duì)涂裝問(wèn)題把車型看作第1種屬性，顏色看作第2種屬性.

ej表示第j種顏色，是q維0-1向量，其第j個(gè)分量為1，其余分量為0.

Xi=(xi，1xi，2…xi，q)T，是一個(gè)q維0-1向量，表示給定序列{N}中第i個(gè)個(gè)體的顏色.

1表示每個(gè)分量都為1的q維向量.

nkj表示給定序列{N}中具有第k個(gè)第1種屬性，第j個(gè)第2種屬性的個(gè)體數(shù)量.

/·/是自定義的一種數(shù)學(xué)運(yùn)算，表示對(duì)處于其中的向量的每個(gè)分量取絕對(duì)值.

Yi，i+1表示對(duì)應(yīng)向量Xi、Xi+1的q維向量.

2 汽車涂裝車間虛擬重排序的數(shù)學(xué)模型

涂裝車間根據(jù)訂單為汽車噴指定顏色的漆.由于噴頭在轉(zhuǎn)換顏色時(shí)會(huì)增加時(shí)間、物料、人工等方面的成本，涂裝車間希望盡可能地減少噴槍顏色的轉(zhuǎn)換次數(shù).

進(jìn)入涂裝車間的車身序列是上游車間的出車間序列.對(duì)涂裝車間來(lái)說(shuō)，相當(dāng)于給定了入車間序列.涂裝車間需對(duì)入車間的車身序列進(jìn)行調(diào)整以實(shí)現(xiàn)噴槍顏色轉(zhuǎn)換次數(shù)最少的目標(biāo).在序列調(diào)整過(guò)程中，所關(guān)注的汽車屬性為車身型號(hào)和車身顏色.通過(guò)互換相同車型的顏色，能做到訂單無(wú)實(shí)質(zhì)變化，但顏色序列會(huì)發(fā)生改變，從而實(shí)現(xiàn)車身序列的虛擬重排序.

根據(jù)虛擬重排序的特點(diǎn)，可以總結(jié)出涂裝虛擬重排序的基本性質(zhì)：(1)顏色唯一性.不論如何調(diào)整車身序列，每個(gè)車身最終只能有唯一的涂裝方案.(2)統(tǒng)計(jì)結(jié)果不變性.重排序只改變了訂單順序，排序前后的兩個(gè)序列中任一車型和顏色的車的數(shù)量保持不變.

用Xi表示第i輛車的涂裝顏色.若其第j個(gè)分量為1，其余分量為0，則該輛車涂裝第j種顏色.

根據(jù)顏色唯一性，對(duì)序列中的每個(gè)個(gè)體來(lái)說(shuō)，最終被噴涂的顏色只能是一種，于是有

(1)

根據(jù)統(tǒng)計(jì)結(jié)果不變性，對(duì)于Xi、Sk和nkj來(lái)說(shuō)，存在如下關(guān)系：

(2)

上式保證了顏色互換只發(fā)生在相同車型中，因此，任何特定車型和顏色的個(gè)體數(shù)目在序列優(yōu)化前后保持不變.

此外，還需把顏色變化次數(shù)表示出來(lái).在序列中相鄰的兩個(gè)個(gè)體，當(dāng)用后一個(gè)個(gè)體的顏色向量減去前一個(gè)個(gè)體的顏色向量，并對(duì)得到顏色差值向量的每個(gè)分量取絕對(duì)值，則相鄰兩個(gè)個(gè)體(第i+1個(gè)個(gè)體和第i個(gè)個(gè)體)之間的顏色變化次數(shù)為

(3)

若相鄰兩個(gè)個(gè)體顏色不同，則式(3)的值為1，表示顏色發(fā)生了一次變化；當(dāng)前后兩個(gè)個(gè)體顏色相同，則式(3)的值為0，表示兩個(gè)相鄰個(gè)體顏色相同.

綜合式(1)～(3)，建立汽車涂裝虛擬重排序問(wèn)題的數(shù)學(xué)模型：

i∈Sk，j=1，2，…，q，k=1，2，…，p

Xi分量取值均為0-1變量

該模型為基本模型，其目標(biāo)函數(shù)是總的噴槍顏色轉(zhuǎn)換次數(shù)最少，對(duì)應(yīng)式(3).約束分為3類，從上到下依次是：顏色唯一性約束，對(duì)應(yīng)式(1)；統(tǒng)計(jì)結(jié)果不變性約束，對(duì)應(yīng)式(2)；向量的每個(gè)分量均為0-1變量的約束.

3 對(duì)基本模型的轉(zhuǎn)化與分析

基本模型建立了關(guān)于汽車涂裝車間虛擬重排序問(wèn)題的含義明確、關(guān)系清晰的數(shù)學(xué)模型.但目標(biāo)函數(shù)含有本文定義的對(duì)向量分量取絕對(duì)值的運(yùn)算，是非線性的，難以直接求解.根據(jù)0-1變量的特點(diǎn)，當(dāng)把目標(biāo)函數(shù)中的向量X用XTX來(lái)替代，此時(shí)，目標(biāo)函數(shù)變?yōu)?/p>

(4)

注意到，Xi的分量都是0-1變量，因此式(4)表示顏色變化次數(shù)與原模型中的目標(biāo)函數(shù)未發(fā)生實(shí)質(zhì)性改變，但自定義的絕對(duì)值符號(hào)已經(jīng)去掉.此時(shí)，基本模型變?yōu)槟繕?biāo)函數(shù)是二次的、約束為線性的0-1整數(shù)規(guī)劃.目前，常用求解軟件不能直接求解一般意義上的0-1二次整數(shù)規(guī)劃，需要對(duì)模型的目標(biāo)函數(shù)進(jìn)一步轉(zhuǎn)化.

把式(4)中的通項(xiàng)(Xi+1-Xi)T·(Xi+1-Xi)展開：

(5)

(6)

(7)

表1 0-1變量及其運(yùn)算結(jié)果

從表1可見，前3列表示了xi和xj以及xi·xj的所有可能.第4列則是y對(duì)應(yīng)xi·xj時(shí)的所有可能，此時(shí)y和xi·xj毫無(wú)關(guān)系.當(dāng)加入約束條件(7)后，y的取值即y′(第5列)與xi·xj(第3列)完全一致.由于表1列出了xi·xj和y′所有可能的情形，在每一種情形下，y′和xi·xj都相等.因此，可用y′代替xi·xj.這類約束條件可稱為變量替換約束.當(dāng)引入這一類約束，目標(biāo)函數(shù)就變?yōu)榫€性的，于是基本模型變?yōu)?/p>

i∈Sk，j=1，2，…，q，k=1，2，…，p

i=1，2，…，n-1，j=1，2，…，q

Xi分量取值均為0-1變量

z4是相鄰個(gè)體顏色相同的數(shù)目，則實(shí)際發(fā)生顏色轉(zhuǎn)換次數(shù)為(n-1)-z4，也就是z2(注意到z2=z3)，故有z2+z4=n-1.表明一個(gè)給定序列顏色相同和不同的相鄰個(gè)體總數(shù)是固定的，總是序列個(gè)體數(shù)減1.

對(duì)于給定序列{N}，所建立的0-1線性整數(shù)規(guī)劃(模型1)共有n個(gè)顏色唯一性約束；pq個(gè)統(tǒng)計(jì)結(jié)果不變性約束；2(n-1)q個(gè)變量替換約束；2(n-1)q個(gè)0-1變量約束，也就是0-1變量的個(gè)數(shù).出現(xiàn)在目標(biāo)函數(shù)中的變量有(n-1)q個(gè).

4 模型應(yīng)用

4.1 模型1的應(yīng)用示例

為了從不同側(cè)面清楚地展示模型1的建立和求解，模型用向量的分量表示.以在問(wèn)題描述中給出的例子為例，對(duì)給定的序列{A2，C1，D2，A1，B1，C2，C2，E2，D2，B2，A1，E1}，要求對(duì)該序列進(jìn)行虛擬重排序以實(shí)現(xiàn)顏色轉(zhuǎn)換次數(shù)最少.根據(jù)給定的序列有n=12，p=5，q=2.此時(shí)，原始序列關(guān)于車型和顏色兩種屬性的個(gè)體統(tǒng)計(jì)結(jié)果如表2.

從表2可見，對(duì)SA，有SA=nA1+nA2=2+1=3.對(duì)給定序列，當(dāng)i∈SA時(shí)，有i=1，4，11(見給定序列).

表2 原始序列中車型和顏色的個(gè)體數(shù)目統(tǒng)計(jì)結(jié)果

模型：

s.t.xi，1+xi，2=1；i=1，2，…，12

x1，j+x4，j+x11，j=nAj；i∈SA，j=1，2

x5，j+x10，j=nBj；i∈SB，j=1，2

x2，j+x6，j+x7，j=nCj；i∈SC，j=1，2

x3，j+x9，j=nDj；i∈SD，j=1，2

x8，j+x12，j=nEj；i∈SE，j=1，2

i=1，2，…，11，j=1，2

所有變量均為0-1變量.該模型有n+pq+2(n-1)q=12+5×2+2×11×2=66個(gè)約束條件(不含關(guān)于變量是0-1整數(shù)這一約束)，有(n-1)q+nq=(12-1)×2+12×2=46個(gè)變量.

根據(jù)xi，j的值(也可以根據(jù)yi+1，i值)得到優(yōu)化后的顏色排序?yàn)閧1，1，2，2，2，2，2，2，2，1，1，1}，重排序后的序列為{A1，C1，D2，A2，B2，C2，C2，E2，D2，B1，A1，E1}.可以看出，在第2、3個(gè)個(gè)體以及第9、10個(gè)個(gè)體間各發(fā)生了一次顏色變化，共發(fā)生了2次顏色變化.若初始序列不進(jìn)行虛擬重排序，則需要5次顏色變化.

4.2 考慮最大噴涂量限制的模型擴(kuò)展

在實(shí)際生產(chǎn)過(guò)程中，噴槍在連續(xù)噴涂一定數(shù)量的車體后，也需要進(jìn)行及時(shí)的清洗維護(hù)，以免出現(xiàn)氣孔和通道堵塞等影響車身噴涂質(zhì)量問(wèn)題.且當(dāng)檢查人員面對(duì)過(guò)長(zhǎng)的相同顏色汽車序列時(shí)，其檢查故障的能力會(huì)降低[15].因此，汽車涂裝時(shí)一般會(huì)設(shè)置一個(gè)最大噴涂量，即連續(xù)噴涂相同顏色的車輛不能超過(guò)最大噴涂量.

若允許的最大噴涂量為m，則在任意連續(xù)的m+1個(gè)噴涂車輛中，至少存在一組兩個(gè)位置相鄰的車輛是不同顏色，即：

(8)

式(8)為最大噴涂量約束.該約束條件是非線性的，其非線性項(xiàng)與基本模型目標(biāo)函數(shù)的非線性項(xiàng)完全相同，故可以采用同樣的處理方法，使之變?yōu)榫€性約束.此時(shí)，會(huì)在約束條件中增加n-m個(gè)最大噴涂量約束.

若考慮最大噴涂量限制(設(shè)m=5)，則在模型1基礎(chǔ)上增加該類約束即可.使用Matlab軟件對(duì)該問(wèn)題進(jìn)行求解，結(jié)果匯總?cè)绫?.

表3 虛擬重排序的解

5 結(jié) 語(yǔ)

本文探討了關(guān)于汽車涂裝虛擬重排序問(wèn)題的建模與求解.在對(duì)虛擬重排序特點(diǎn)進(jìn)行提煉的基礎(chǔ)上，把顏色做了編碼，建立了關(guān)于涂裝虛擬重排序的0-1二次整數(shù)規(guī)劃模型，并提出了把模型中二次表達(dá)式轉(zhuǎn)化為線性表達(dá)式的方法，從而最終建立起關(guān)于涂裝虛擬重排序問(wèn)題的0-1線性整數(shù)規(guī)劃模型.由于屬性是顏色還是其他對(duì)所建立的模型并無(wú)實(shí)質(zhì)性影響，故所建模型可用于任何虛擬重排序問(wèn)題.

所建立的0-1線性整數(shù)模型的變量和約束條件的個(gè)數(shù)大致在max{np，nq，pq}數(shù)量級(jí)，即模型本身規(guī)模和問(wèn)題的參數(shù)(n，p，q)之間大體是二次方關(guān)系.盡管0-1線性整數(shù)規(guī)劃目前尚無(wú)一般的多項(xiàng)式時(shí)間算法，但已經(jīng)有很多求解軟件，如Matlab、CPLEX、LINGO等，都可以直接求解這類問(wèn)題，無(wú)須設(shè)計(jì)專門的求解算法就能求得精確解.這是本研究與以往虛擬重排序問(wèn)題研究最大的不同.

此外，除了借助于計(jì)算機(jī)技術(shù)、優(yōu)化方法等，尋找問(wèn)題本身的特點(diǎn)應(yīng)該是解決虛擬重排序問(wèn)題的努力方向之一.因?yàn)閺母L(zhǎng)的時(shí)間跨度看，序列的規(guī)模會(huì)很大，但屬性種類和取值有限，這就意味著這類排序問(wèn)題不但會(huì)存在具有相同序列的片段，而且極可能存在如“再生長(zhǎng)點(diǎn)”類似的性質(zhì)，即對(duì)于給定序列，其中存在一個(gè)或多個(gè)節(jié)點(diǎn).這些節(jié)點(diǎn)有如下的性質(zhì)：當(dāng)按照這些節(jié)點(diǎn)把序列分為小的序列時(shí)，對(duì)每個(gè)小序列進(jìn)行虛擬重排序，這些小序列虛擬重排序的結(jié)果和把整個(gè)序列直接進(jìn)行虛擬重排序的結(jié)果一致.此時(shí)，問(wèn)題的規(guī)模就會(huì)大大降低，計(jì)算復(fù)雜性也隨之大幅下降.“再生長(zhǎng)點(diǎn)”方面的研究，也許是解決虛擬重排序問(wèn)題一個(gè)值得嘗試的思路.