袁際軍,黃敏鎂,楊宏林,單汨源

(1.廣東財(cái)經(jīng)大學(xué) 金融學(xué)院，廣東 廣州 510320；2.廣東財(cái)經(jīng)大學(xué) 信息學(xué)院，廣東 廣州 510320； 3.華南師范大學(xué) 公共管理學(xué)院，廣東 廣州 510006；4.湖南大學(xué) 工商管理學(xué)院，湖南 長(zhǎng)沙 410082)

1 問題的提出

在大規(guī)模定制環(huán)境下，不同客戶間的現(xiàn)有需求存在差異，不同時(shí)間段同一客戶的潛在需求具有可變性[1-2]。以客戶群體內(nèi)不同現(xiàn)有需求和可預(yù)期潛在需求為基礎(chǔ)，建立各種形式化且具較強(qiáng)表達(dá)能力的產(chǎn)品配置模型，提出相應(yīng)配置求解方法，是近十年產(chǎn)品配置領(lǐng)域內(nèi)主流的研究邏輯[3-4]。這類研究邏輯大多存在一個(gè)隱含的前提，即客戶下達(dá)訂單前，必須清楚自己的配置需求并明確地予以表達(dá)；訂單下達(dá)后至已配置產(chǎn)品交付前，客戶的原有配置需求被固化，不可更改。實(shí)際上，這類配置邏輯將客戶群體中每個(gè)客戶的個(gè)性配置需求視作一次性任務(wù)，在市場(chǎng)偏好穩(wěn)定且產(chǎn)品生產(chǎn)周期較短的環(huán)境下，這類產(chǎn)品配置方法體現(xiàn)出了較強(qiáng)的適應(yīng)性。然而，隨著市場(chǎng)偏好波動(dòng)性的增強(qiáng)以及產(chǎn)品生產(chǎn)周期的延長(zhǎng)，這類產(chǎn)品配置方法開始呈現(xiàn)出一定的局限性。一個(gè)值得注意的現(xiàn)象是，在已配置產(chǎn)品的實(shí)際生產(chǎn)過程中，企業(yè)經(jīng)常會(huì)根據(jù)客戶需求的變更修改和完善生產(chǎn)中已配置產(chǎn)品的組成結(jié)構(gòu)，從而獲得滿足客戶新需求的重構(gòu)產(chǎn)品配置方案并重新組織生產(chǎn)[5-6]，本文將該活動(dòng)稱為產(chǎn)品配置更新設(shè)計(jì)，如圖1所示。Zhang等[7]也指出，為了對(duì)不同階段的客戶需求進(jìn)行快速響應(yīng)，企業(yè)應(yīng)對(duì)訂單處理及生產(chǎn)相關(guān)的系統(tǒng)進(jìn)行集成，使定制產(chǎn)品的生產(chǎn)狀態(tài)信息能夠被實(shí)時(shí)獲取和利用。這些事實(shí)初步表明，產(chǎn)品配置更新設(shè)計(jì)研究已引起學(xué)界的關(guān)注。

因此，本文研究以已配置產(chǎn)品生產(chǎn)過程中的客戶需求變更為切入點(diǎn)，以可配置產(chǎn)品中配置知識(shí)的識(shí)別及生產(chǎn)過程中已配置產(chǎn)品所處的實(shí)時(shí)狀態(tài)引致的生產(chǎn)約束為基礎(chǔ)，建立產(chǎn)品配置更新優(yōu)化數(shù)學(xué)模型，并提出一種多目標(biāo)優(yōu)化方法，以實(shí)現(xiàn)模型的優(yōu)化求解。通過該方法，可以實(shí)時(shí)自動(dòng)地評(píng)估客戶需求變更的可滿足性，確定客戶需求變更導(dǎo)致初始產(chǎn)品配置方案中零件重調(diào)整的波及范圍，獲得符合客戶需求變更的最優(yōu)產(chǎn)品配置推薦更新方案。

2 文獻(xiàn)述評(píng)

產(chǎn)品配置指對(duì)預(yù)先定義的一組組件在一定約束條件下進(jìn)行重組，形成滿足客戶需求的組件集合[8]。最早成功應(yīng)用于商業(yè)的產(chǎn)品配置器是美國(guó)DEC公司和卡內(nèi)基—梅隆大學(xué)(Carnegie-Mellon University)合作開發(fā)的用于配置VAX計(jì)算機(jī)的R1/XCON配置系統(tǒng)[9]。R1/XCON配置系統(tǒng)采用“if…then…”的產(chǎn)生式規(guī)則將客戶需求、組件功能等與具體組件關(guān)聯(lián)在一起，其優(yōu)點(diǎn)是求解速度快，不足之處是將配置模型知識(shí)與具體的求解策略知識(shí)耦合在一起，導(dǎo)致配置知識(shí)庫(kù)維護(hù)困難。為了開發(fā)出可維護(hù)性強(qiáng)的產(chǎn)品配置器，配置知識(shí)的識(shí)別與表示成為配置領(lǐng)域的研究重點(diǎn)。Mittal等[10]認(rèn)為某些組件是否出現(xiàn)在配置結(jié)果中依賴于“關(guān)鍵”組件是否被挑選參與配置，并采用激活性約束描述這類配置知識(shí);Juengst等[11]發(fā)現(xiàn)在產(chǎn)品配置過程中，有些組件生產(chǎn)某種資源，如內(nèi)存容量、電能等，而另外一些組件則需要消耗這類資源,在一個(gè)可行的配置結(jié)果中，資源產(chǎn)生的數(shù)量與消耗的數(shù)量應(yīng)該平衡,他們將這類配置知識(shí)定義為資源約束;Stumptner等[12]提出“端口”的概念，用于描述組件間連接的配置知識(shí);Soininen等[13]對(duì)配置知識(shí)進(jìn)行了系統(tǒng)的總結(jié)，認(rèn)為配置知識(shí)包括客戶配置需求知識(shí)、配置模型知識(shí)和配置求解知識(shí)，并從可重用性角度構(gòu)建了配置知識(shí)本體。在配置知識(shí)識(shí)別后，構(gòu)建一個(gè)易于維護(hù)的產(chǎn)品配置知識(shí)庫(kù)的關(guān)鍵在于采用何種語言形式化地描述這些配置知識(shí)。對(duì)配置知識(shí)的形式化描述，從最初的產(chǎn)生式規(guī)則語言[9]，到隨后的約束語言[10,14-15]、面向?qū)ο笳Z言[16]及現(xiàn)在廣為使用的本體語言[17]，其語言的可擴(kuò)展性、可維護(hù)性和描述能力變得越來越強(qiáng)；但也帶來了一些不足，如配置求解能力越來越差。為了彌補(bǔ)配置求解能力的不足，同時(shí)保留面向?qū)ο笳Z言或本體語言配置知識(shí)描述能力強(qiáng)、可重用性高、易于維護(hù)的優(yōu)勢(shì)，已有學(xué)者提出一些新的產(chǎn)品配置建模與求解方法。張良等[18]提出基于灰色關(guān)聯(lián)與權(quán)重順序交叉的產(chǎn)品配置方案重構(gòu)技術(shù)，以便同時(shí)兼顧復(fù)雜產(chǎn)品的配置效率和配置質(zhì)量;Frutos等[19]采用面向?qū)ο笳Z言構(gòu)建形式化的產(chǎn)品配置模型，然后將配置模型映射為整數(shù)線性規(guī)劃模型，利用現(xiàn)有的優(yōu)化技術(shù)實(shí)現(xiàn)了配置模型的優(yōu)化求解。相比Frutos構(gòu)建整數(shù)線性規(guī)劃模型時(shí)，僅考慮了兼容性約束與非兼容性約束等兩類配置知識(shí)，Yang等[20]以統(tǒng)一建模語言(Unified Modeling Language, UML)描述配置知識(shí)為基礎(chǔ)，更全面地實(shí)現(xiàn)了配置知識(shí)(如兼容性約束、產(chǎn)品結(jié)構(gòu)約束、資源約束等)向整數(shù)規(guī)劃模型的映射，然后利用現(xiàn)有優(yōu)化技術(shù)實(shí)現(xiàn)配置模型的優(yōu)化求解。

為了開發(fā)出用戶友好的產(chǎn)品配置系統(tǒng)，交互式配置成為配置領(lǐng)域中的又一研究熱點(diǎn)。所謂交互式產(chǎn)品配置是指在產(chǎn)品配置過程中，配置系統(tǒng)(或配置器)對(duì)客戶提出的配置需求進(jìn)行逐項(xiàng)反饋，引導(dǎo)客戶最終獲得滿足要求的配置結(jié)果。在交互式產(chǎn)品配置過程中，當(dāng)客戶配置需求與配置模型不一致而導(dǎo)致無解時(shí)，系統(tǒng)需要對(duì)客戶配置需求中的沖突部分進(jìn)行診斷，并將最優(yōu)的診斷結(jié)果反饋給客戶。診斷結(jié)果是一個(gè)配置需求子集，取消這些配置需求可以使配置問題重新恢復(fù)到可解狀態(tài)。因此，對(duì)于交互式產(chǎn)品配置，尋找較好的求解方法是該領(lǐng)域的研究重心。例如Felfernig等[21]針對(duì)與配置知識(shí)庫(kù)不一致的用戶需求，提出一種用于求解個(gè)性化診斷的新算法—PersDiag(personalized diagnosis algorithm)；為了進(jìn)一步提高消解配置沖突的診斷計(jì)算效率，F(xiàn)elfernig等[22]又提出基于分治策略的診斷算法—FASTDIAG(divide and conquer-based diagnosis algorithm)，實(shí)驗(yàn)表明在求解個(gè)性化診斷時(shí)，該算法的性能優(yōu)于傳統(tǒng)基于模型診斷計(jì)算方法。

在產(chǎn)品交付客戶使用后，由于產(chǎn)品升級(jí)換代或客戶需求的變更，需要對(duì)原產(chǎn)品進(jìn)行再配置，即根據(jù)當(dāng)前的配置模型對(duì)歷史配置結(jié)果進(jìn)行修改和完善，使其成為一個(gè)新的、合理的產(chǎn)品，新形成的產(chǎn)品要與原產(chǎn)品在結(jié)構(gòu)和功能上保持等同或有所增強(qiáng)。文獻(xiàn)[23-24]對(duì)企業(yè)進(jìn)行產(chǎn)品再配置的需求進(jìn)行了分析，并對(duì)企業(yè)對(duì)再配置的支持與否進(jìn)行了調(diào)查;文獻(xiàn)Krenz等[25-26]對(duì)再配置系統(tǒng)中的知識(shí)更新問題進(jìn)行了分析研究;Williams等[27]采用基于模型的方法對(duì)再配置進(jìn)行了研究;Wang[28]認(rèn)為產(chǎn)品配置變更活動(dòng)在產(chǎn)品全生命周期中都可能發(fā)生,當(dāng)對(duì)現(xiàn)存產(chǎn)品進(jìn)行修改時(shí)會(huì)涉及一些部件的更換，而每個(gè)部件分別由不同的供應(yīng)商提供，其成本、質(zhì)量等都存在一些差異。文獻(xiàn)[28]主要關(guān)注的是產(chǎn)品功能升級(jí)以及為了增加產(chǎn)品附加值過程中產(chǎn)生的產(chǎn)品再配置活動(dòng)。

上述文獻(xiàn)對(duì)產(chǎn)品配置技術(shù)的研究主要集中在客戶訂單下達(dá)前和產(chǎn)品交付后這兩階段。Wang等[5]認(rèn)為在產(chǎn)品全生命周期中，客戶個(gè)性化需求存在可變性;Zheng等[29]也認(rèn)為客戶需求變更、設(shè)計(jì)錯(cuò)誤糾正及零件質(zhì)量問題等會(huì)引發(fā)配置變更活動(dòng)，并提出一種動(dòng)態(tài)優(yōu)化方法，用于處理復(fù)雜產(chǎn)品設(shè)計(jì)中出現(xiàn)的配置變更問題;Jiang等[6]研究了生產(chǎn)過程中因零件庫(kù)存短缺引起的產(chǎn)品配置變更活動(dòng),認(rèn)為在產(chǎn)品的生產(chǎn)過程中，供應(yīng)商的延誤、零件的毀壞、零件的誤用等可能會(huì)使處于生產(chǎn)過程中的零件庫(kù)存出現(xiàn)短缺，從而發(fā)生產(chǎn)品配置變更。零件的替換可能會(huì)帶來產(chǎn)品成本、產(chǎn)品交貨期或零件庫(kù)存的變化，因此文獻(xiàn)[6]關(guān)注的焦點(diǎn)是如何替換產(chǎn)品結(jié)構(gòu)中的短缺部件，使所涉及的所有更換部件在滿足一定配置約束下的總成本最小、產(chǎn)品交貨期延誤最短、庫(kù)存更均衡。

受文獻(xiàn)[5-6]研究思想的啟發(fā)，本文認(rèn)為在客戶訂單下達(dá)后至已配置產(chǎn)品完工前，產(chǎn)品配置方案不可更改的傳統(tǒng)假定難以滿足客戶需求存在可變性的現(xiàn)實(shí)要求。客戶潛在的個(gè)性化產(chǎn)品需求規(guī)范具有高度不確定性和難以預(yù)測(cè)性，而且在客戶下達(dá)訂單后的已配置產(chǎn)品生產(chǎn)期間，還存在不斷變更當(dāng)初提出的產(chǎn)品規(guī)范要求的動(dòng)態(tài)性?？蛻粜枨笞兏芊癖唤邮埽瑳Q定于最新產(chǎn)品配置知識(shí)庫(kù)中的配置約束以及已配置產(chǎn)品的生產(chǎn)狀態(tài)約束能否被滿足。客戶滿意度能否進(jìn)一步增加，決定于配置更新系統(tǒng)能否快速檢測(cè)客戶需求變更的可接受性，并對(duì)可接受的需求變更給出最優(yōu)的產(chǎn)品配置更新推薦方案。因此，本文將圍繞這一議題，以目前已有的產(chǎn)品配置知識(shí)識(shí)別相關(guān)研究成果為基礎(chǔ)，剖析產(chǎn)品配置更新問題；構(gòu)建產(chǎn)品配置更新問題優(yōu)化模型，并提出一種多目標(biāo)優(yōu)化求解方法，以實(shí)現(xiàn)對(duì)產(chǎn)品配置更新問題的優(yōu)化求解，獲得滿足客戶個(gè)性化需求變化的最優(yōu)產(chǎn)品配置更新推薦方案。

2 問題描述

產(chǎn)品配置更新優(yōu)化問題指在滿足產(chǎn)品配置約束和已配置產(chǎn)品當(dāng)前生產(chǎn)狀態(tài)形成的制造約束下，基于可接受的客戶需求變更，對(duì)已配置產(chǎn)品組成結(jié)構(gòu)進(jìn)行修改或完善，獲得滿足客戶需求的最優(yōu)重構(gòu)產(chǎn)品配置方案。在已配置產(chǎn)品生產(chǎn)過程中，當(dāng)客戶對(duì)原有配置需求規(guī)范提出變更時(shí)，會(huì)涉及對(duì)已配置產(chǎn)品中的部分組件的置換。置換產(chǎn)品中某一組件可能會(huì)引起與其他組件的沖突，導(dǎo)致其他組件的置換，而其他組件的置換又會(huì)引發(fā)類似的沖突，從而引起一系列連鎖沖突反應(yīng)。本文假定在客戶的配置需求變更要求得不到完全滿足的條件下，為了消解出現(xiàn)的配置沖突，客戶容忍企業(yè)變更其原配置需求規(guī)范中的部分剩余需求或撤銷部分新需求，以此來部分滿足客戶的配置需求變更要求。產(chǎn)品配置更新優(yōu)化的決策前提在于判斷：①客戶的新需求之間是否存在沖突；②需要被置換的舊需求其對(duì)應(yīng)的組件是否已處于制造狀態(tài)；③客戶的新需求與被保留的剩余需求之間是否存在沖突。產(chǎn)品配置更新優(yōu)化目標(biāo)是使所獲得的產(chǎn)品配置更新推薦方案滿足：①盡可能少的變更客戶的部分剩余需求；②盡可能少地撤銷客戶的部分新需求。因此，產(chǎn)品配置更新優(yōu)化問題的解是一組最優(yōu)Pareto解。

考慮一個(gè)簡(jiǎn)單的產(chǎn)品配置更新優(yōu)化問題：某一可配置產(chǎn)品內(nèi)包含A,B,C,D 4類可配置單元,配置單元A包括A1,A2兩個(gè)可選具體組件，配置單元B包括B1,B2兩個(gè)可選具體組件，配置單元C包括C1，C2兩個(gè)可選具體組件，配置單元D包括D1，D2，D3，D44個(gè)可選具體組件。其中，組件A2與D2不兼容，組件B1與D1不兼容，組件C2與D3不兼容。假設(shè)在T0時(shí)刻，處于生產(chǎn)狀態(tài)的已配置產(chǎn)品由組件A1，B2，C2，D1等組件構(gòu)成，其中組件C2處于已制造狀態(tài)。客戶需求變更要求為將組件A1和B2分別更換為組件A2和B1。

如圖2所示，組件A1和B2分別更換為組件A2和B1后，組件B1與組件D1因不兼容而產(chǎn)生配置沖突。消解沖突的方法是取消組件B2的變更，從而獲得第1個(gè)產(chǎn)品配置更新解{A2,B2,C2,D1}。若不取消組件B2的更換，則將組件D1更換為配置單元D所包含的其他組件。假定將組件D1更換為組件D2，此時(shí)又因組件D2與組件A2不兼容而產(chǎn)生配置沖突。消解沖突的方法是取消組件A1的變更，從而獲得第2個(gè)產(chǎn)品配置更新解{A1,B1,C2,D2}。若不取消組件A1的更換，則需將組件D2更換為配置單元D所包含的其他組件。假定將組件D2更換為組件D3，此時(shí)又因組件D3與組件C2因不兼容而產(chǎn)生沖突。組件C2處于已制造狀態(tài)不可更換；因此消解沖突的方法是將D3再更換為配置單元D所包含的其他組件。在將組件D3更換為組件D4后，無沖突發(fā)生，從而獲得第3個(gè)產(chǎn)品配置更新解{A2,B1,C2,D4}。其中，解3相比解2而言，對(duì)剩余需求有相同的修改量，對(duì)客戶新需求有更少的修改量，因此是比解2占優(yōu)的一個(gè)產(chǎn)品配置更新推薦解。解1與解3互不占優(yōu)，是該問題的一組Pareto最優(yōu)產(chǎn)品配置更新推薦解。

3 產(chǎn)品配置更新優(yōu)化數(shù)學(xué)模型

根據(jù)產(chǎn)品配置更新優(yōu)化問題的描述以及表1所示符號(hào)的意義，產(chǎn)品配置更新優(yōu)化問題的數(shù)學(xué)模型(多目標(biāo)混合整數(shù)規(guī)劃模型)表述如下：

(1)

(2)

s.t.

(3)

(4)

(5)

xi,k+xj,g≤1,?(ci,k,cj,g)∈Re；

(6)

xj,g-xi,k≥0,?(ci,k,cj,g)∈Rd；

(7)

(8)

(9)

表1 產(chǎn)品配置更新優(yōu)化模型涉及的符號(hào)及其含義

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

式(1)表示最小化新可選配置項(xiàng)重新恢復(fù)成客戶需求變更前對(duì)應(yīng)的舊可選配置項(xiàng)的數(shù)量，代表了對(duì)客戶新需求的滿足程度。當(dāng)f1=0時(shí)，表明產(chǎn)品配置更新優(yōu)化結(jié)果完全滿足客戶新需求。式(2)表示最小化已配置產(chǎn)品PT0中對(duì)被保留可選配置項(xiàng)進(jìn)行變更的數(shù)量，代表了對(duì)客戶所保留的舊需求的滿足程度。當(dāng)f2=0時(shí)，表明產(chǎn)品配置更新優(yōu)化結(jié)果完全滿足客戶所保留的舊需求;當(dāng)f1=0且f2=0時(shí)，表明客戶的需求變更要求得到完全滿足；否則，表明客戶的需求變更要求得到部分滿足或沒有得到滿足。

(2)約束

4 求解產(chǎn)品配置更新優(yōu)化模型的多目標(biāo)遺傳算法

根據(jù)產(chǎn)品配置更新問題的特征及其復(fù)雜性，以非占優(yōu)排序遺傳算法-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ)為基礎(chǔ)[30-31]，本文采用基于非占優(yōu)排序與擁擠距離排序的多目標(biāo)多約束遺傳算法，求解產(chǎn)品配置更新優(yōu)化問題。多目標(biāo)多約束產(chǎn)品配置更新優(yōu)化遺傳算法的一般流程如圖3所示。

4.1 產(chǎn)品配置更新染色體的表示

本質(zhì)上而言，產(chǎn)品配置更新優(yōu)化問題求解在是在一定約束條件和優(yōu)化目標(biāo)下，利用可選配置項(xiàng)對(duì)可配置單元進(jìn)行實(shí)例化，獲得滿足客戶期望的產(chǎn)品配置更新優(yōu)化結(jié)果。因此，本文采用整數(shù)編碼的染色體表達(dá)方式，其中，基因代表可配置單元，基因值的取值范圍由代表可配置單元實(shí)例(即可選配置項(xiàng))的索引值組成。例如可配置單元ck包含2個(gè)可選配置項(xiàng)實(shí)例ck,1和ck,2，分別用索引值1和2代表可選配置項(xiàng)ck,1和ck,2，則用于實(shí)例化可配置單元ck的基因取值范圍為{1,2}。在產(chǎn)品配置更新問題中，可配置單元存在可選和必選兩類。對(duì)于可選類型的可配置單元，在某些產(chǎn)品配置中，任何實(shí)例都不會(huì)出現(xiàn)在其中；而對(duì)于必選類型的可配置單元，在任一產(chǎn)品配置中，必有一個(gè)實(shí)例出現(xiàn)在其中。因此，對(duì)于可選類型的可配置單元基因，本文將“0”添加到基因的取值范圍中，若基因值取為“0”，則表示該可配置單元的任何實(shí)例都不出現(xiàn)在與染色體對(duì)應(yīng)的產(chǎn)品配置更新結(jié)果中(如圖4)。當(dāng)已配置產(chǎn)品處于生產(chǎn)過程中，客戶提出需求變更時(shí)，已配置產(chǎn)品的組成部分由已處于制造狀態(tài)的可選配置項(xiàng)和未處于制造狀態(tài)的可選配置項(xiàng)兩部分構(gòu)成。本文假定已處于制造狀態(tài)的可選配置項(xiàng)不可更換，處于未制造狀態(tài)的可選配置項(xiàng)可以更換，對(duì)與已處于制造狀態(tài)的可選配置項(xiàng)相對(duì)應(yīng)的可配置單元而言，本文對(duì)基因取值施加一個(gè)一元約束，即其基因取值始終限定為與已處于制造狀態(tài)的可選配置項(xiàng)相對(duì)應(yīng)的索引值。如在圖4中，當(dāng)客戶提出需求變更要求時(shí)，可配置單元ci的第2個(gè)實(shí)例ci,2已處于制造狀態(tài)(圖4中灰色區(qū)域)，當(dāng)構(gòu)建產(chǎn)品配置更新染色體時(shí)，與可配置單元ci對(duì)應(yīng)的基因值始終固定為2。

4.2 算法描述

產(chǎn)品配置更新多目標(biāo)優(yōu)化遺傳算法步驟包括種群初始化、染色體優(yōu)化目標(biāo)函數(shù)值與約束違反量計(jì)算、非占優(yōu)排序與擁擠距離排序、產(chǎn)品配置個(gè)體進(jìn)化、種群合并與替換、產(chǎn)品配置更新優(yōu)化設(shè)計(jì)的Pareto最優(yōu)解集的輸出6個(gè)步驟。

(1)種群初始化

根據(jù)產(chǎn)品配置個(gè)體染色體的表達(dá)方式，針對(duì)每一個(gè)可配置單元，從可配置單元(基因)實(shí)例集合中隨機(jī)挑選一個(gè)可選配置項(xiàng)(基因值)實(shí)例化可配置單元，生成N個(gè)互不相同的染色體(產(chǎn)品配置個(gè)體)構(gòu)成初始種群Pop1。

(2)染色體的優(yōu)化目標(biāo)函數(shù)值與約束違反次數(shù)計(jì)算

1)目標(biāo)函數(shù)值計(jì)算 評(píng)估種群中每個(gè)染色體代表的產(chǎn)品配置個(gè)體對(duì)客戶新需求和被保留的舊需求的滿足程度，獲得種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值(如f1和f2)。

2)約束違反次數(shù)計(jì)算 種群中并非每個(gè)染色體所代表的產(chǎn)品配置解都滿足可制造性約束和客戶個(gè)性要求(如產(chǎn)品交貨期)。因此，需要評(píng)估染色體的約束違反次數(shù)，以確定解的優(yōu)劣性。設(shè)nj表示染色體j的約束違反總次數(shù)，

(11)

(3)非占優(yōu)排序與擁擠距離排序

1)非占優(yōu)解 在多目標(biāo)優(yōu)化問題中，處于較低Pareto前沿等級(jí)的解優(yōu)于較高Pareto前沿等級(jí)的解。令si和sj分別是染色體種群中染色體i和j所代表的兩個(gè)產(chǎn)品配置解。解si的Pareto前沿等級(jí)低于解sj的Pareto前沿等級(jí)，當(dāng)且僅當(dāng)下列條件之一成立：①解si是可行解而解sj是不可行解；②當(dāng)解si和解sj均為可行解時(shí)，解si的所有目標(biāo)函數(shù)值都分別不劣于解sj的目標(biāo)函數(shù)值，并且解si存在至少一個(gè)目標(biāo)函數(shù)值優(yōu)于解sj的目標(biāo)函數(shù)值；③當(dāng)解si和解sj均為不可行解時(shí)，解si的約束違反次數(shù)少于解sj的約束違反次數(shù)。

2)擁擠距離 擁擠距離用于度量處于同一Pareto前沿等級(jí)的染色體個(gè)體之間的稀疏程度，擁擠距離越小表明染色體之間越緊密。擁擠距離的計(jì)算方法如下：假設(shè)存在m個(gè)目標(biāo)函數(shù)和n個(gè)處于同一Pareto前沿上的產(chǎn)品配置解，則產(chǎn)品配置解si在所有m個(gè)目標(biāo)函數(shù)上與相鄰兩個(gè)產(chǎn)品配置解的擁擠距離

(12)

(13)

“非占優(yōu)排序+擁擠距離排序”是指首先對(duì)種群中染色體所代表的產(chǎn)品配置解的優(yōu)劣程度進(jìn)行非占優(yōu)排序，使較優(yōu)的染色體具有較低的Pareto前沿等級(jí),然后對(duì)處于同一Pareto前沿的染色體根據(jù)個(gè)體擁擠距離按降序排列。

(4)產(chǎn)品配置個(gè)體進(jìn)化

1)復(fù)制/選擇操作 遺傳算法采用適應(yīng)度函數(shù)值作為染色體復(fù)制/選擇操作的依據(jù)。處于不同Pareto前沿等級(jí)的個(gè)體，Pareto前沿等級(jí)較低的個(gè)體具有較高的適應(yīng)度；處于同一Pareto前沿等級(jí)的個(gè)體，擁擠距離大的個(gè)體具有較高的適應(yīng)度。在遺傳進(jìn)化過程中，本文采用聯(lián)賽選擇的復(fù)制/選擇操作方式，首先從父代種群Popt中隨機(jī)挑選兩個(gè)染色體，以適應(yīng)度函數(shù)值為標(biāo)準(zhǔn)，選取具有較高適應(yīng)度值的個(gè)體并放至交配池，然后重復(fù)之前的操作，直到交配池染色體規(guī)模達(dá)到父代種群規(guī)模的一半為止。

2)交叉操作 本文采用單點(diǎn)交叉方式,即從交配池中隨機(jī)挑選兩個(gè)染色體，根據(jù)交叉概率決定是否進(jìn)行交叉操作。對(duì)參與交叉操作的兩個(gè)父代染色體，隨機(jī)選擇一個(gè)交叉點(diǎn)進(jìn)行單點(diǎn)交叉，互換父代染色體部分相同位置基因值，產(chǎn)生兩個(gè)新的子代染色體(如圖5)。

3)變異操作 本文采用單點(diǎn)變異操作，即對(duì)交叉操作產(chǎn)生的子代染色體，根據(jù)變異概率決定是否進(jìn)行變異操作。對(duì)參與變異操作的子代染色體，隨機(jī)選擇一個(gè)基因座，并從基因座對(duì)應(yīng)的值域中隨機(jī)挑選一個(gè)基因值替換當(dāng)前基因座上的基因值，產(chǎn)生新的子代染色體(如圖6)。

(5)種群合并與替換 對(duì)交配池中的染色體進(jìn)行交叉/變異操作至規(guī)定次數(shù)，產(chǎn)生新的子代染色體種群Cildt。然后，合并父代染色體Popt和子代染色體Cildt，剔除重復(fù)個(gè)體后，產(chǎn)生臨時(shí)種群Tempt。對(duì)臨時(shí)種群進(jìn)行非占優(yōu)排序和擁擠距離排序，根據(jù)適應(yīng)度函數(shù)值從大到小挑選N個(gè)互不相同的染色體(產(chǎn)品配置個(gè)體)形成下一代用于遺傳進(jìn)化操作的種群Popt+1。

(6)產(chǎn)品配置更新優(yōu)化設(shè)計(jì)的Pareto最優(yōu)解集的輸出 染色體種群遺傳進(jìn)化操作次數(shù)(用計(jì)數(shù)器t進(jìn)行計(jì)數(shù))至規(guī)定最大迭代次數(shù)G后，終止遺傳進(jìn)化操作，并輸出處于Pareto最優(yōu)前沿的染色體個(gè)體，即一組可行的最優(yōu)產(chǎn)品配置更新推薦方案。

5 仿真實(shí)驗(yàn)

下面以某公司生產(chǎn)的餐飲油水分離器為例，說明本文所提方法的可行性與有效性。

5.1 餐飲油水分離器產(chǎn)品配置更新優(yōu)化問題描述

餐飲油水分離器是一個(gè)典型的可配置產(chǎn)品，其產(chǎn)品族結(jié)構(gòu)和配置約束網(wǎng)絡(luò)圖分別如圖7和圖8所示。表2對(duì)圖8中所示的配置約束進(jìn)行了形式化描述。圖9所示的餐飲油水分離器A為在T0時(shí)刻處于生產(chǎn)狀態(tài)的已配置產(chǎn)品個(gè)體，其中上水箱進(jìn)水管B、上水箱出水管B、桶罩門A 3個(gè)可選配置項(xiàng)正處于制造狀態(tài)。假定在T0時(shí)刻，客戶提出的配置需求變更要求如下：①將上水箱體C更換為上水箱體A，將調(diào)速攪拌電機(jī)B更換為調(diào)速攪拌電機(jī)A；②新產(chǎn)生的產(chǎn)品配置推薦方案的能耗應(yīng)不大于7 440 W；③新產(chǎn)生的產(chǎn)品配置更新推薦方案的交貨期時(shí)延應(yīng)不大于原產(chǎn)品配置方案(即餐飲油水分離器A)的10%，即δ=10%。其中要求①為軟約束，②和③為硬約束。為了滿足客戶的需求變更要求，企業(yè)餐飲油水分離器產(chǎn)品配置更新優(yōu)化的任務(wù)為：①以分別對(duì)初始餐飲油水分離器A和客戶需求變更要求修改最少為目標(biāo)，提供一組Pareto最優(yōu)的產(chǎn)品配置更新推薦方案,以期盡可能滿足客戶的需求變更要求；②該組產(chǎn)品配置更新推薦方案不得違反餐飲油水分離器產(chǎn)品配置約束與T0時(shí)刻生產(chǎn)狀態(tài)形成的制造約束。

表2 可配置餐飲油水分離器中的產(chǎn)品配置約束

配置約束類型約束集合排斥性規(guī)則Re{(上水箱進(jìn)水管A,上水箱體D),(上水箱進(jìn)水管C,上水箱體A),(上水箱出水管A,上水箱體D),(上水箱出水管C,上水箱體A),(桶罩體A,桶罩門B),(主分離箱體D,排水管A),(主分離箱體D,排污管A),(主分離箱體A,排污管B),(主分離箱體A,阻油箱B),(主分離箱體D,阻油箱A),(主分離箱體A,聚油頂C),(聚油頂C,加熱桿A),(上水箱體A,輸送水泵C),(上水箱體D,輸送水泵A),(調(diào)速攪拌電機(jī)A,攪拌桿B),(聚油頂A,葉輪C),(攪拌桿A,葉輪C),(主分離箱體A,清洗泵A),(主分離箱體B,清洗泵A)}依賴性規(guī)則Rd{(上水箱體A,桶罩體A),(上水箱體B,桶罩體B),(上水箱體C,桶罩體C),(上水箱體D,桶罩體D),(桶罩體A,主分離箱體A),(桶罩體B,主分離箱體B),(桶罩體C,主分離箱體C),(桶罩體D,主分離箱體D),(上水箱出水管A,主分離箱體進(jìn)水管A),(上水箱出水管B,主分離箱體進(jìn)水管B),(上水箱出水管C,主分離箱體進(jìn)水管C),(聚油頂B,加熱桿B),(主分離箱體C,清洗泵A),(主分離箱體D,清洗泵A)}

5.2 餐飲油水分離器產(chǎn)品配置更新優(yōu)化問題數(shù)學(xué)建模

在可配置產(chǎn)品中存在3類部件：①公共件(如水位感應(yīng)器)，在所有的可配置產(chǎn)品實(shí)例中都出現(xiàn)；②可選類型的可配置單元(如清洗泵)，在實(shí)例化可配置產(chǎn)品時(shí)，可選類型的可選配置單元并不總被挑選參與實(shí)例化；③必選類型的可配置單元(如主分離箱體)，在實(shí)例化可配置產(chǎn)品時(shí)，必選類型的可配置單元必被挑選參與實(shí)例化，并出現(xiàn)在可配置產(chǎn)品實(shí)例中。因此，在餐飲油水分離器產(chǎn)品配置更新優(yōu)化問題中，本文只關(guān)注兩類變量：可配置單元和可選配置項(xiàng)(如表3)。

根據(jù)第5.1節(jié)餐飲油水分離器產(chǎn)品配置更新優(yōu)化問題的描述，采用第3章所提的產(chǎn)品配置更新優(yōu)化數(shù)學(xué)模型方法，建立如下可配置餐飲油水分離器的產(chǎn)品配置更新優(yōu)化問題數(shù)學(xué)模型：

優(yōu)化目標(biāo)：

minf1=2-(x3,1+x14,1);

minf2=15-(x1,2+x2,2+x4,3+x5,1+

x6,3+x7,2+x8,1+x9,3+x10,1+x11,1+x12,3

+x13,2+x15,2+x16,3+x17,1)。

約束條件：

(1)可配置單元實(shí)例化約束

(2)客戶新需求與被摒棄舊需求之間的關(guān)聯(lián)約束

x3,3+x3,1=1，x14,2+x14,1=1。

(3)可選配置項(xiàng)制造狀態(tài)約束(已處于制造狀態(tài)的可選配置項(xiàng)不可變更)

x1,2=1，x2,2=1，x5,1=1。

(4)排斥性約束

x1,1+x3,4≤1;x1,3+x3,1≤1;

x2,1+x3,4≤1;x2,3+x3,1≤1，x4,1+x5,2≤1;

x6,4+x8,1≤1，x6,4+x10,1≤1，x6,1+x10,2≤1;

x6,1+x11,2≤1，x6,4+x11,1≤1，x6,1+x9,3≤1;

x9,3+x12,1≤1，x3,1+x13,3≤1，x3,4+x13,1≤1;

x14,1+x15,2≤1，x9,1+x16,3≤1，x15,1+x16,3≤1;

x6,1+x17,1≤1，x6,2+x17,1≤1。

(5)依賴性約束

x4,1-x3,1≥0;x4,2-x3,2≥0，x4,3-x3,3≥0;

x4,4-x3,4≥0;x6,1-x4,1≥0，x6,2-x4,2≥0;

x6,3-x4,3≥0;x6,4-x4,4≥0，x7,1-x2,1≥0;

x7,2-x2,2≥0;x7,3-x2,3≥0，x12,2-x9,2≥0;

x17,1-x6,3≥0，x17,1-x6,4≥0。

(6)資源平衡性約束

3 000x12,1+4 000x12,2+5 000x12,3+

2(550x13,1+750x13,2+1 100x13,3)+

90x14,1+120x14,2+120x17,1<7 440。

(7)新配置產(chǎn)品的交貨期時(shí)延要低于客戶容忍的最大時(shí)延(交貨期約束)

(3x1,1+4x1,2+6x1,3)+(4x2,1+5x2,2+7x2,3)+

(6x3,1+7x3,2+8x3,3+9x3,4)+(5x4,1+6x4,2+

7x4,3+8x4,4)+(2x5,1+3x5,2)+(6x6,1+7x6,2+

8x6,3+9x6,4)+(4x7,1+5x7,2+7x7,3)+(7x8,1+

8x8,2)+(6x9,1+7x9,2+8x9,3)+(4x10,1+5x10,2)+

(2x11,1+3x11,2)+(5x12,1+6x12,2+7x12,3)+

(5x13,1+6x13,2+7x13,3)+(5x14,1+6x14,2)+

(3x15,1+4x15,2)+(3x16,1+4x16,2+5x16,3)+

6x17,1≤(1+0.1)×(4+5+8+7+2+

8+5+7+8+4+2+7+6+6+4+5+6)。

(8)變量取值范圍

xi=1,i∈{1,2,…,16}；xi∈{0,1},i=17；

xi,j∈{0,1},i∈N,j∈N。

表3 可配置餐飲油水分離器部分參數(shù)描述

續(xù)表3

5.3 餐飲油水分離器產(chǎn)品配置更新問題優(yōu)化求解與結(jié)果分析

針對(duì)所建立的餐飲油水分離器產(chǎn)品配置更新問題多目標(biāo)優(yōu)化模型，采用本文提出的多目標(biāo)遺傳算法進(jìn)行仿真求解，獲得最優(yōu)的產(chǎn)品配置更新優(yōu)化推薦方案。仿真求解的運(yùn)行環(huán)境是Windows XP，Intel(R)Core(TM)2 Duo CPU T7100 @1.80 GHz 1.79 GHz，0.99 GB內(nèi)存，編程語言為MATLAB 2015a。通過多次實(shí)驗(yàn)，確定算法中的相關(guān)參數(shù)：種群規(guī)模為60(在進(jìn)化迭代過程中始終保持染色體個(gè)體互不相同，種群規(guī)模始終維持為60)，進(jìn)化代數(shù)為1 000次，交叉概率為0.8，變異概率為0.1。

為了衡量本文所提多目標(biāo)遺傳算法的魯棒性與收斂性，采用各個(gè)Pareto前沿解對(duì)應(yīng)的優(yōu)化目標(biāo)值之和(f1+f2)作為衡量指標(biāo)進(jìn)行解的度量，如第1、2、3、4層級(jí)和全部層級(jí)Pareto前沿解優(yōu)化目標(biāo)值之和等5個(gè)衡量指標(biāo)。圖10所示為遺傳進(jìn)化過程中5個(gè)衡量指標(biāo)顯示的解的收斂過程。由圖10可知，在遺傳進(jìn)化的第1代，第1、2、3、4層級(jí)和全部層級(jí)Pareto前沿解優(yōu)化目標(biāo)值之和分別為83、226、64、116和916。前4個(gè)層級(jí)的Pareto前沿解優(yōu)化目標(biāo)值之和為489，小于全部層級(jí)Pareto前沿解優(yōu)化目標(biāo)值之和，表明此時(shí)種群中解的Pareto層級(jí)大于4，解的分散程度比較大。隨著遺傳迭代進(jìn)化的進(jìn)行，第4層級(jí)Pareto前沿解優(yōu)化目標(biāo)值之和的波動(dòng)性逐漸縮小，并從第139代開始趨于穩(wěn)定，此時(shí)目標(biāo)值之和為0，表明種群中解的Pareto層級(jí)開始小于4。接著，第1層級(jí)Pareto前沿解在第349代開始趨于穩(wěn)定，此時(shí)目標(biāo)值之和為20，解的個(gè)數(shù)為5；第2層級(jí)Pareto前沿解在第446代開始趨于穩(wěn)定，此時(shí)目標(biāo)值之和為150，解的個(gè)數(shù)為32；第3層級(jí)Pareto前沿解在第446代開始趨于穩(wěn)定，此時(shí)目標(biāo)值之和為155，解的個(gè)數(shù)為23；全部層級(jí)Pareto前沿解在第446代開始趨于穩(wěn)定，此時(shí)目標(biāo)值之和為325，解的個(gè)數(shù)為60。根據(jù)求解過程中遺傳進(jìn)化的反饋結(jié)果可知，在種群進(jìn)化趨于穩(wěn)定時(shí)，所有解的約束違反量均為0，表明此時(shí)種群個(gè)體均為可行解，其中第1層級(jí)的Pareto前沿集為最優(yōu)可行解集。圖11所示為種群進(jìn)化到1 000代時(shí)，在f1和f2兩個(gè)優(yōu)化目標(biāo)值上解的Pareto層級(jí)圖。其中，目標(biāo)值f1反映了新需求的滿足程度，f1值越大表明被撤銷的新需求越多，客戶新需求的滿足程度越低；目標(biāo)值f2反映了剩余需求的滿足程度，f2值越大表明被變更的客戶剩余需求越多。

表4所示為圖11中處于第1層級(jí)Pareto前沿最優(yōu)解集。其中，解1和解2具有相同的優(yōu)化目標(biāo)值，解3和解4具有相同的優(yōu)化目標(biāo)值。解1和解2表明，如果完全滿足客戶新的配置變更需求(f1=0)，則需要變更6個(gè)客戶的剩余需求(f2=6)，才能使產(chǎn)生的產(chǎn)品配置更新最優(yōu)推薦方案是無違反約束的可行解;解3和解4表明，如果只需部分滿足客戶

新的配置變更需求(f1=1)，則需要變更2個(gè)剩余需求(f2=2)，才能使產(chǎn)生的產(chǎn)品配置更新最優(yōu)推薦方案是無違反約束的可行解。解5表明，如果不變更客戶的剩余需求(f2=0)，則客戶的新需求需要全部撤銷(f1=2)，才能使產(chǎn)生的產(chǎn)品配置更新最優(yōu)推薦方案是無違反約束的可行解，而此時(shí)解5實(shí)際上對(duì)應(yīng)于客戶配置需求變更前的初始產(chǎn)品配置方案。

表4 處第一Pareto前沿的產(chǎn)品配置更新最優(yōu)推薦解集

6 結(jié)束語

為了在已配置產(chǎn)品生產(chǎn)過程中快速響應(yīng)客戶提出的配置需求變更要求，并提供滿足客戶要求的產(chǎn)品配置更新最優(yōu)推薦方案，以便有效地指導(dǎo)企業(yè)的實(shí)際生產(chǎn)活動(dòng)，本文提出一種產(chǎn)品配置更新理論與優(yōu)化方法。首先給出產(chǎn)品配置更新問題的描述，接著在系統(tǒng)剖析可配置產(chǎn)品結(jié)構(gòu)、配置規(guī)則和生產(chǎn)約束的條件下，建立了產(chǎn)品配置更新問題的多目標(biāo)數(shù)學(xué)優(yōu)化模型;然后基于NSGA-Ⅱ的思想，提出求解產(chǎn)品配置更新優(yōu)化問題的多目標(biāo)遺傳算法;最后以某可配置餐飲油水分離器為例，對(duì)本文所提方法進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的可行性與有效性。本文方法在理論上作出了如下貢獻(xiàn)：

(1)拓展了傳統(tǒng)的產(chǎn)品配置理論研究領(lǐng)域。傳統(tǒng)產(chǎn)品配置理論主要關(guān)注客戶訂單下達(dá)前的配置活動(dòng)以及產(chǎn)品交付客戶后的再配置活動(dòng)，并隱含地假定客戶訂單下達(dá)后至產(chǎn)品交付客戶前的生產(chǎn)過程中無配置活動(dòng)發(fā)生。而現(xiàn)實(shí)中，在具有較深交互活動(dòng)的個(gè)性化定制產(chǎn)品生產(chǎn)過程中，客戶需求具有一定的可變性，對(duì)原有產(chǎn)品結(jié)構(gòu)存在一定的重新變更要求，因此有配置活動(dòng)發(fā)生。本文研究成果是對(duì)這一過程的有益補(bǔ)充。

(2)提出一種新的產(chǎn)品配置更新優(yōu)化模型。相比傳統(tǒng)產(chǎn)品配置模型，該模型嵌入了已配置產(chǎn)品生產(chǎn)過程中客戶需求變更約束、實(shí)時(shí)生產(chǎn)約束與產(chǎn)品交貨期約束等信息。通過求解該模型，可獲得既定配置約束與生產(chǎn)約束下最優(yōu)產(chǎn)品配置更新推薦方案，以響應(yīng)已配置產(chǎn)品生產(chǎn)期間客戶配置需求變更要求。

(3)本文所提方法可被借鑒用于處理產(chǎn)品再配置問題。產(chǎn)品再配置問題主要關(guān)注產(chǎn)品功能升級(jí)換代所引起的部件更換而產(chǎn)生的配置沖突問題。在本文模型中，通過剔除生產(chǎn)約束，增加部件版本升級(jí)引發(fā)的配置約束，并將客戶需求變更由軟約束更改為硬約束后，便可采用本文方法處理產(chǎn)品再配置問題。

本文方法在管理方面的意義主要在于：①通過在已配置產(chǎn)品生產(chǎn)過程中不斷滿足客戶需求變更要求，增強(qiáng)了客戶的滿意度，有助于企業(yè)的客戶關(guān)系管理；②借助計(jì)算機(jī)的幫助，及時(shí)自動(dòng)地生成滿足客戶要求的產(chǎn)品配置更新最優(yōu)推薦方案，節(jié)省了企業(yè)人工處理所帶來的耗時(shí)、易出錯(cuò)等生成成本，增加了企業(yè)的生產(chǎn)效率及快速反應(yīng)能力。

本文研究關(guān)注的焦點(diǎn)是在已配置產(chǎn)品生產(chǎn)過程中如何實(shí)時(shí)提供滿足客戶需求變更的最優(yōu)產(chǎn)品配置更新方案，在生產(chǎn)約束方面重點(diǎn)考察了客戶需求變更要求在企業(yè)生產(chǎn)能力內(nèi)的可滿足性以及產(chǎn)品的交貨期限制。另一個(gè)值得關(guān)注的問題是企業(yè)在已配置產(chǎn)品的生產(chǎn)過程中，因滿足客戶需求變更而導(dǎo)致的產(chǎn)品成本上升，是否在客戶的承受能力范圍之內(nèi)。在客戶需求發(fā)生變更時(shí)，新需求對(duì)應(yīng)的零部件與舊需求對(duì)應(yīng)的零部件會(huì)發(fā)生置換，從而導(dǎo)致產(chǎn)品成本的變動(dòng)；另外，考慮到不同部件的裝配順序或一些在途部件的可獲性帶來的客戶需求變動(dòng)難度，變動(dòng)難度越高，變動(dòng)成本越高，這些都會(huì)帶來定制產(chǎn)品最終成本的變化。因此，在現(xiàn)實(shí)的大規(guī)模定制生產(chǎn)過程中，企業(yè)不可能隨意滿足客戶的個(gè)性化需求，客戶的需求變動(dòng)還應(yīng)根據(jù)變動(dòng)成本、變動(dòng)難度及可滿足度進(jìn)行約束。未來將進(jìn)一步研究在上述附加約束下，基于客戶需求變更的最優(yōu)產(chǎn)品配置更新方案求解方法。