張 光 前， 何 曉 飛

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

0 引 言

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

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

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

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

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

1 問題描述及符號設(shè)定

在涂裝車間需要對白車身進(jìn)行涂漆.白車身是指已完成焊裝工序但尚未面漆的汽車車身.若進(jìn)入涂裝車間的白車身有5種類型，分別用字母A、B、C、D、E表示；需要噴涂的顏色有兩種，分別用1和2表示.若進(jì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次.若對同型車身進(jìn)行顏色互換，如把序列中車型同為A的兩個車身顏色互換，則會使該序列的前兩個車身都為顏色1.這種調(diào)整未實質(zhì)性改變客戶訂單，但噴涂顏色轉(zhuǎn)換次數(shù)可能會減少，從而達(dá)到總的顏色轉(zhuǎn)換次數(shù)最少的要求.由于在此過程中沒有用到緩沖區(qū)，此即車身涂裝的虛擬重排序問題.

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

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

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

1表示每個分量都為1的q維向量.

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

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

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

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

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

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

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

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

根據(jù)顏色唯一性，對序列中的每個個體來說，最終被噴涂的顏色只能是一種，于是有

(1)

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

(2)

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

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

(3)

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

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

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

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

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

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

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

(4)

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

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

(5)

(6)

(7)

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

從表1可見，前3列表示了xi和xj以及xi·xj的所有可能.第4列則是y對應(yīng)xi·xj時的所有可能，此時y和xi·xj毫無關(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是相鄰個體顏色相同的數(shù)目，則實際發(fā)生顏色轉(zhuǎn)換次數(shù)為(n-1)-z4，也就是z2(注意到z2=z3)，故有z2+z4=n-1.表明一個給定序列顏色相同和不同的相鄰個體總數(shù)是固定的，總是序列個體數(shù)減1.

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

4 模型應(yīng)用

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

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

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

表2 原始序列中車型和顏色的個體數(shù)目統(tǒng)計結(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個約束條件(不含關(guān)于變量是0-1整數(shù)這一約束)，有(n-1)q+nq=(12-1)×2+12×2=46個變量.

根據(jù)xi，j的值(也可以根據(jù)yi+1，i值)得到優(yōu)化后的顏色排序為{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個個體以及第9、10個個體間各發(fā)生了一次顏色變化，共發(fā)生了2次顏色變化.若初始序列不進(jìn)行虛擬重排序，則需要5次顏色變化.

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

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

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

(8)

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

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

表3 虛擬重排序的解

5 結(jié) 語

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

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

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