高頻換產(chǎn)情境下手機裝配生產(chǎn)線訂單調(diào)度優(yōu)化

張 磊，劉 強，鄧芳芳，趙榮麗，俞愛林+

(1.廣東工業(yè)大學(xué) 省部共建精密電子制造技術(shù)與裝備國家重點實驗室，廣東 廣州 510006; 2.廣東開放大學(xué) 公共教學(xué)部，廣東 廣州 510091)

0 引言

作為手機生產(chǎn)的末段，手機裝配環(huán)節(jié)具有如下顯著特征：

(1)高頻次換產(chǎn) 手機產(chǎn)品更迭迅速、型號眾多且批量不一，因此手機裝配需要在不同手機產(chǎn)品之間頻繁切換，其平均換產(chǎn)周期通常以小時計。為適應(yīng)這種換產(chǎn)需求，企業(yè)需對裝配生產(chǎn)線進行頻繁重構(gòu)。

(2)交貨期緊迫 手機消費市場競爭異常激烈，客戶對交貨期的要求近乎嚴苛，訂單拖期將給企業(yè)帶來經(jīng)濟損失、客戶流失及其他連鎖效應(yīng)。以上特征對手機產(chǎn)品的生產(chǎn)組織，尤其是對其訂單調(diào)度提出了非常高的要求。

基于上述特點，手機裝配生產(chǎn)訂單調(diào)度需考慮生產(chǎn)線重構(gòu)約束及訂單交貨期約束。高頻換產(chǎn)引發(fā)裝配生產(chǎn)線重構(gòu)，該過程中整條生產(chǎn)線將停產(chǎn)閑置。生產(chǎn)線重構(gòu)部分越多，停產(chǎn)閑置的時間將越長。因此，訂單調(diào)度方案優(yōu)化需要充分考慮訂單切換帶來的生產(chǎn)線重構(gòu)代價。簡單的優(yōu)化方法是盡可能將相同產(chǎn)品的生產(chǎn)訂單合并，但該方法極有可能導(dǎo)致部分交期靠前的訂單拖期。另外，將時間跨度過大的訂單合并會使整個待調(diào)度優(yōu)化的訂單過多，解空間急劇增大，給問題求解帶來較大困難。

針對訂單調(diào)度優(yōu)化問題(Order Scheduling Optimization Problem, OSOP)，國內(nèi)外學(xué)者已有大量研究。LIN等[1]綜述了OSOP，并提出一種算法可應(yīng)用于具有共同交期的OSOP。EGE等[2]使用基于分支定界思想的啟發(fā)式算法，研究了并行裝配工作站的OSOP；HYUN等[3]通過遺傳算法解決了混合模型裝配線的OSOP；TASGETIREN等[4]與LIAN等[5]分別提出一種求解最大完工時間和總流水時間最小的粒子群算法，研究了不同類型流水線的OSOP；GEN等[6]引入了求解多目標(biāo)優(yōu)化問題的分配機制與性能指標(biāo)，并提出多目標(biāo)進化算法，解決了多種類型的OSOP；HAJRI等[7]與張洪業(yè)[8]分別通過基于模糊策略和置信函數(shù)的控制遺傳算法和建立Petri網(wǎng)模型，研究了典型生產(chǎn)車間的OSOP；劉永等[9]通過帶精英策略的蟻群算法研究了多訂單環(huán)境下的OSOP；黎英杰[10]通過基于可行域搜索的遺傳算法，解決了涉及任務(wù)分批與子批調(diào)度的分批調(diào)度問題；劉晨等[11]通過遺傳算法思想研究了多品種小批量訂單型企業(yè)的OSOP；陳保安[12]通過遺傳算法對離散型制造車間雙向OSOP進行優(yōu)化，得到車間生產(chǎn)靜態(tài)調(diào)度優(yōu)化結(jié)果；李浩[13]通過啟發(fā)式算法對大型裝備的大規(guī)模定制生產(chǎn)的OSOP進行了優(yōu)化。楊學(xué)全[14]基于啟發(fā)式算法，考慮訂單總完成時間及換產(chǎn)時間，對單機訂單調(diào)度問題進行了研究。張燕等[15]基于多聯(lián)票據(jù)換產(chǎn)時間長的特點，通過混合遺傳算法研究了其場景的多目標(biāo)優(yōu)化問題，但其換產(chǎn)時間假定為固定值，與手機裝配生產(chǎn)特點不符；張揚等[16]基于服務(wù)不可儲存的特點，建立了有別于產(chǎn)品生產(chǎn)的服務(wù)訂單調(diào)度優(yōu)化模型。WU等[17]研究了OSOP中的加工時間部分的魯棒性，最小化最大總拖期；SHI等[18]通過機器學(xué)習(xí)研究了常見并行生產(chǎn)環(huán)境下的OSOP；BOYER等[19]介紹了一種元啟發(fā)式算法以解決廣義的柔性作業(yè)OSOP。

綜上所述，考慮生產(chǎn)線重構(gòu)及訂單交貨期約束，對手機裝配生產(chǎn)訂單調(diào)度問題的研究較少。為此，本文以手機裝配換產(chǎn)時間以及換產(chǎn)重構(gòu)復(fù)雜度作為考慮因素，研究高頻換產(chǎn)場景下的OSOP，這對于手機生產(chǎn)企業(yè)成本節(jié)約，以及核心競爭力的提升具有重要的現(xiàn)實意義。

1 問題描述與建模

1.1 手機裝配線構(gòu)成及其特性

為便于產(chǎn)品切換并提升生產(chǎn)效率，當(dāng)前大多數(shù)企業(yè)通常采用支持人機雙模靈活切換的模塊化手機裝配線，主要包括上、下料機構(gòu)，TP貼膜、點膠及壓合設(shè)備，貼雙面膠設(shè)備，以及鎖螺絲設(shè)備等裝配設(shè)備單元(Assembly Device Units, ADU)。本文基于對某手機裝配生產(chǎn)企業(yè)的深入調(diào)研，抽象出了一個典型的手機裝配生產(chǎn)線模型，如圖1所示。該生產(chǎn)線采用串行結(jié)構(gòu)，由n臺ADU及上料機構(gòu)組成，物料由托盤裝載，并依靠傳送帶在工序間轉(zhuǎn)運。

當(dāng)進行某型號手機裝配時，托盤從傳送帶的起點上料，一旦經(jīng)第i道裝配工序(即第i臺ADU)，由機械臂對傳送帶上的工件進行吸取，放至該ADU進行裝配作業(yè)后，再由機械臂吸取并放回至傳送帶，由此完成該裝配工序。工件將按工藝順序完成所有裝配作業(yè)，直至該手機完成整機裝配并從生產(chǎn)線下料。當(dāng)該訂單的所有手機裝配完畢，則需要進行產(chǎn)品切換并重構(gòu)裝配線，按照該手機的加工工藝增加、移除或調(diào)整移動ADU，并進行相應(yīng)測試。該重構(gòu)過程需要花費一定時間，期間裝配線進入換產(chǎn)態(tài)，線上所有ADU停產(chǎn)閑置，直至重構(gòu)完成，裝配線重新進入運行態(tài)。

本文研究的OSOP的主要矛盾為產(chǎn)品的高價值與加工設(shè)備的高閑置率，具體表現(xiàn)為：一方面需要靈活完成小批次訂單并按時交貨;另一方面需避免過高的產(chǎn)線重構(gòu)代價。由于不同產(chǎn)品裝配工藝之間存在差異，使用ADU的順序、種類與數(shù)量也存在差異，導(dǎo)致裝配線換產(chǎn)前后所對應(yīng)的換產(chǎn)變更度不同，進而導(dǎo)致不同產(chǎn)品之間的換產(chǎn)時間存在差異，即手機裝配生產(chǎn)過程中的換產(chǎn)過程具有未定特性，而全部訂單完成的總時間由已定的加工時間與未定的換產(chǎn)時間兩部分構(gòu)成，即對于不同的訂單序列，全部訂單完成的總時間會有所差異。因此，如何在滿足產(chǎn)品交期的前提下優(yōu)化訂單順序，縮短不同產(chǎn)品之間未定的換產(chǎn)時間，同時避免因過早完成訂單造成的庫存積壓，是本文將要研究的主要問題。

1.2 模型假設(shè)

為抽取問題核心，便于數(shù)學(xué)建模，特提出以下假設(shè)：

(1)某訂單裝配過程中只在一條流水線上完成所有裝配作業(yè)，中途不會轉(zhuǎn)移到其他裝配線；

(2)裝配線上仍有工件進行裝配的情況下，不會對裝配線進行重構(gòu)換產(chǎn)，直到一個訂單的最后一個工件的最后一個工序完成后才開始重構(gòu)換產(chǎn)；

(3)忽略ADU的故障時間、修復(fù)時間等；

(4)換產(chǎn)后原材料的運輸時間、準(zhǔn)備時間，ADU的開機自檢等算入換產(chǎn)時間內(nèi)；

(5)相同種類產(chǎn)品的加工工藝不會發(fā)生改變。

1.3 符號定義

基于該問題的特征與假設(shè)，提出以下符號定義：

π為訂單序列，其中π={π(0),π(1),…,π(n)}；

n為訂單總數(shù)；

i為優(yōu)化后的訂單序列編號，i=1,2,…,n；

j為優(yōu)化前的訂單序列編號，j=1,2,…,n；

Si,π為訂單序列π中第i個訂單的開始時間；

Ci,π為訂單序列π中第i個訂單的完成時間；

Ti,π為訂單序列π中第i個訂單后的換產(chǎn)時間；

Di,π為訂單序列π中第i個訂單的交期時間；

Ri,π為訂單序列π中第i個訂單完成時距離交期的剩余時間；

Ni,π為訂單序列π中第i個訂單的待加工工件數(shù)量；

Bi,π為訂單序列π中第i個訂單的設(shè)備節(jié)拍；

NPj為訂單j的待加工工件數(shù)量；

BPj為訂單j的節(jié)拍時間；

DPj為訂單j的交期時間；

Pi,π為訂單序列π中第i個訂單的產(chǎn)品類別；

Pj為訂單j的產(chǎn)品類別；

Cost為總成本；

CT為時間成本；

CS為庫存成本；

βT為時間轉(zhuǎn)換為成本的換算系數(shù)；

βS為庫存轉(zhuǎn)換為成本的換算系數(shù)；

Ki,π為訂單序列π中第i個訂單后的換產(chǎn)變更度；

KAi,π為訂單序列π中第i個訂單后的設(shè)備增減變更度；

KMi,π為訂單序列π中第i個訂單后的設(shè)備移位變更度；

τ為換產(chǎn)變更度轉(zhuǎn)換為換產(chǎn)時間的換算系數(shù)；

T0為換產(chǎn)基礎(chǔ)時間；

αA為設(shè)備增減變更度對換產(chǎn)變更度的影響因子；

αM為設(shè)備移位變更度對換產(chǎn)變更度的影響因子；

Xi,j為決策變量，當(dāng)訂單j被安排在訂單序列π中第i個順序加工時Xi,j=1，否則為Xi,j=0。

1.4 高頻換產(chǎn)手機裝配線數(shù)學(xué)模型

基于上述假設(shè)及定義，給出考慮交期及庫存成本的高頻換產(chǎn)手機裝配生產(chǎn)線的數(shù)學(xué)模型：

min(CT+CS)。

(1)

s.t.

CT=βTCn,π,

(2)

(3)

Ti,π=τKi,π+T0,

(4)

Ki,π=αAKAi,π+αMKMi,π,

(5)

Ri,π=Di,π-Ci,π,

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

Ri,π≥0。

(15)

其中：式(1)為目標(biāo)函數(shù)，即最小化由時間成本與庫存成本兩部分組成的總成本。式(2)～式(15)為約束條件，其中式(2)為時間成本表達式，等于時間成本轉(zhuǎn)換系數(shù)乘以訂單完成總時間；式(3)為庫存成本表達式，等于時間成本轉(zhuǎn)換系數(shù)乘以訂單完成時距離交期的剩余時間與訂單加工件數(shù)量之和；式(4)為換產(chǎn)時間表達式，等于換產(chǎn)基礎(chǔ)時間加上換算系數(shù)乘以換產(chǎn)變更度；式(5)為換產(chǎn)變更度表達式，等于設(shè)備增減變更度與設(shè)備移位變更度不同權(quán)重之和；式(6)表示訂單完成時距離交期的剩余時間等于該訂單的交期時間減去完成時間；式(7)為訂單i的完成時間表達式，由此訂單前的加工時間之和與換產(chǎn)時間之和疊加而成，由于研究對象為流水線裝配作業(yè)，且訂單內(nèi)代裝配工件較多(≥2 000)，將一個訂單的完成時間簡化為生產(chǎn)節(jié)拍×工件數(shù)量，其誤差率≥0.5%，可以接受，因此訂單的加工時間由該訂單所生產(chǎn)的產(chǎn)品類別的節(jié)拍時間與待裝配工件數(shù)量所決定；式(8)～式(9)分別為訂單i的加工瓶頸時間與待加工工件數(shù)量的表達式，等于決策變量乘以訂單j；式(10)～式(11)分別為設(shè)備增減變更度與設(shè)備移位變更度表達式，分別由函數(shù)fA(x,y)與fM(x,y)輸出得到，其自變量為序列π的第i個順序加工訂單對應(yīng)的訂單的產(chǎn)品類別與第i+1個順序加工訂單對應(yīng)的訂單的產(chǎn)品類別；式(12)表示決策變量Xi,j為0-1變量，當(dāng)且僅當(dāng)訂單j被安排在訂單i時，該值為1，其余時候為0；式(13)～式(14)分別保證訂單i與訂單j只會出現(xiàn)一次；式(15)保證了各訂單的交期時間需大于其計劃完成時間，確保訂單可在交期前完成，避免產(chǎn)品出荷延期。

與傳統(tǒng)OSOP模型相比，該模型具有以下兩個主要特點：①針對手機裝配作業(yè)具有品種多、批量小及交期緊迫的特點，不同產(chǎn)品之間的換產(chǎn)時間存在差異，有必要考慮該特征對結(jié)果的影響，該模型針對該特殊情境，設(shè)置不同換產(chǎn)變更度以表現(xiàn)出該特殊情境的特點；②針對手機產(chǎn)品具有高價值及價保周期短的特點，由于存在庫存成本及窄交期時間窗的限制，排除了為盡量避免換產(chǎn)過程而過早提前完成訂單的調(diào)度方案。這將給問題的求解帶來以下兩個難點：①動態(tài)的換產(chǎn)時間增加了模型的復(fù)雜度，提升了訂單調(diào)度的難度；②窄交期時間窗大大壓縮了可行解在解空間中的比例，導(dǎo)致求解OSOP常用的進化算法難以獲取合適的初始解且容易陷入局部最優(yōu)解。

2 算法設(shè)計與實現(xiàn)

考慮時間成本與庫存成本的高頻換產(chǎn)裝配線訂單調(diào)度問題是一類NP-Hard問題，其總樣本數(shù)為訂單數(shù)的階乘，隨著訂單規(guī)模的增大，其計算復(fù)雜度也隨之急劇增大。針對訂單規(guī)模較小的數(shù)據(jù)，尚可使用簡單枚舉以獲得最優(yōu)解，但訂單規(guī)模過小的場合，其研究價值并不大，因此需要提出一種更為高效精準(zhǔn)的算法以代替枚舉法。針對訂單規(guī)模較大的場合，不可能通過枚舉獲得最優(yōu)解，目前常用的方法有分支定界法(Branch and Bound, B&B)[20]、遺傳算法(Genetic Algorithm, GA)[21]以及粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法。下面分別應(yīng)用B&B、GA與PSO算法3種算法對本文提出的高頻換產(chǎn)手機裝配線訂單調(diào)度優(yōu)化模型進行求解。

2.1 基于交期可行域的分支定界算法

B&B求解的基本思想是枚舉可行域中的可行解，如圖2所示為基于交期可行域的多叉樹B&B算法流程，以及其解空間樹剪枝擴展的示意圖。

其具體求解過程如下：

步驟1生成根節(jié)點。

假定一個根節(jié)點A，初始化Node(cc,rt,id)=Node(0,rt,0)，其中：cc為當(dāng)前成本;rt為交期判斷標(biāo)志位，rt=1表示該節(jié)點符合交期要求，可進行擴展分支，rt=0則表示該節(jié)點不符合交期要求，不可進行擴展分支，進行剪枝操作;id為搜索層數(shù)。

步驟2擴展節(jié)點。

擴展id=0的節(jié)點A，一次生成n個子代，每個子代的解分別為X1,1=[1,0,0,…,0]，X1,2=[0,1,0,…,0]，X1,3=[0,0,1,…,0]…計算全部子代的Node(cc,rt,id)。

步驟3剪枝。

子代停止對rt=0的節(jié)點的擴展(剪枝)，僅對rt=1的節(jié)點進行擴展，重復(fù)步驟2，直到每一層擴展完畢。如圖2中D節(jié)點的rt=0，因此不對其進行擴展；又如圖2中B節(jié)點理應(yīng)有3個子節(jié)點，但因為式(13)限制，不可能存在多個訂單安排在同一位置的情況，所以不計算其Node參數(shù)，可直接對其進行剪枝。

步驟4獲取最優(yōu)解。

重復(fù)步驟4直到id=n，初始化bestC為無限大，當(dāng)有節(jié)點的cc

為驗證基于可行域的多叉樹B&B算法的準(zhǔn)確性，對不同訂單數(shù)的案例分別通過枚舉算法與該算法進行求解，如表1所示，可以發(fā)現(xiàn)，在小規(guī)模訂單情況下，B&B算法得到的最優(yōu)解都與枚舉算法得到的最優(yōu)解相同，且當(dāng)訂單數(shù)上升時，B&B算法耗時明顯優(yōu)于枚舉算法，并在相同硬件配置下支持運算更大訂單數(shù)的案例。由此可以推出，本文所提算法可有效求解高頻換產(chǎn)手機裝配線模型，其求得的最優(yōu)解即為模型的精確最優(yōu)解。

表1 遍歷算法與B&B算法結(jié)果與耗時對比

2.2 改進型初代自旋遺傳算法

GA的基本思想是通過隨機過程獲取初始種群，通過計算種群中不同個體的適應(yīng)度，選擇出種群中相對較優(yōu)的個體作為父代，將其較優(yōu)的基因保留下來，并通過交叉、變異等操作獲取子代，以避免陷入局部最優(yōu)的情況。

根據(jù)本研究場景的特點，應(yīng)用數(shù)據(jù)集的原始訂單序列號作為GA的編碼方式。

因數(shù)學(xué)模型目標(biāo)函數(shù)為(CT+CS)的最小值，則該算法的適應(yīng)度函數(shù)應(yīng)為目標(biāo)函數(shù)的倒數(shù)，如式(16)所示：

(16)

其算法步驟如下：

步驟1獲取初始種群。

隨機獲得原始訂單序列號gaSize個，最大迭代次數(shù)gaGen，輪盤賭大小tournamentSize，交叉概率PC，變異概率PM。

步驟2獲取可行解集。

計算初始種群的結(jié)果，記錄可行解的基因與適應(yīng)度值，若無可行解，則重復(fù)步驟1直到有可行解。

步驟3遺傳過程。

選擇：在可行解中通過輪盤賭選擇個體；

交叉：隨機選擇不同片段對父代個體染色體進行交叉操作；

變異：隨機選擇不同點位對交叉過程形成的子代進行變異操作。

步驟4迭代計算。

遺傳過程獲得的子代形成新種群，并重復(fù)步驟2和步驟3，直到獲得的解的適應(yīng)度值不再發(fā)生變化。

本文研究了3種GA，分別記為GA-Ⅰ、GA-Ⅱ及GA-Ⅲ。GA-Ⅰ為標(biāo)準(zhǔn)的GA算法流程；GA-Ⅱ與GA-Ⅰ相比，增加了對初始種群無可行解集的判空邏輯，若初始種群無可行解集，則自旋繼續(xù)生成新的初始種群，直到初始種群含有可行解集，從而避免初始種群可行解集為空的情況出現(xiàn)，以達到大幅降低初始種群大小的目的；GA-Ⅲ相對于給定迭代次數(shù)的GA-Ⅱ，優(yōu)化了迭代次數(shù)的設(shè)定，其優(yōu)勢在于對迭代數(shù)進行了優(yōu)化控制，通過判斷當(dāng)前解是否已經(jīng)達到最優(yōu)/局部最優(yōu)解，實現(xiàn)了最大迭代數(shù)的動態(tài)調(diào)整，優(yōu)化了算法效率，降低了陷入局部最優(yōu)解的可能性。

2.3 改進型初代自旋粒子群算法

PSO算法是一種進化算法，最早由KENNEDY等[22]于1995年提出，其基本思想是通過群體中不同個體間的協(xié)同合作找到最優(yōu)解。粒子具有位移與速度兩個屬性，其中速度受個體歷史最優(yōu)解(Individual Best, IB)與群體歷史最優(yōu)解(Global Best, GB)共同影響，而影響的大小也受隨機數(shù)影響，使之具有群體智慧的同時，也保有一定的全局搜索能力。

根據(jù)本研究場景的特點，應(yīng)用數(shù)據(jù)集的原始訂單序列號作為PSO算法的編碼方式。數(shù)學(xué)模型目標(biāo)函數(shù)為(CT+CS)的最小值，因此該算法的適應(yīng)度函數(shù)應(yīng)為目標(biāo)函數(shù)的倒數(shù)，如式(16)所示。

其算法步驟如下：

步驟1獲取初始種群。

設(shè)定粒子群規(guī)模為psoSize，最大迭代次數(shù)psoGen，學(xué)習(xí)因子c1、c2，慣性因子ω。

步驟2獲取可行解集。

計算初始種群的結(jié)果，記錄可行解的基因與適應(yīng)度值，若無可行解，則重復(fù)步驟1直到有可行解。

步驟3迭代更新速度與位移。

各粒子的IB與GB迭代更新其自身的速度vpso與位移xpso，如式(17)和式(18)所示，其中ibest為IB，gbest為GB，直到完成psoGen次迭代:

vpso=ωvpso+c1r1(ibest-xpso)+c2r2(gbest-xpso),

(17)

xpso=xpso+vpso。

(18)

本文研究了2種PSO算法，分別記為PSO-Ⅰ與PSO-Ⅱ。PSO-Ⅰ為傳統(tǒng)的粒子群算法；PSO-Ⅱ為改進型初代自旋粒子群算法，與GA-Ⅱ相同，增加了對初始種群可行解集的判空邏輯，可大幅降低粒子群規(guī)模。

2.4 算法性能對比

本文選用GA-Ⅰ、GA-Ⅱ、GA-Ⅲ、PSO-Ⅰ、PSO-Ⅱ以及B&B算法分別對4個訂單規(guī)模為12的數(shù)據(jù)集重復(fù)進行10次求解實驗，其中數(shù)據(jù)集2、3位對比不同算法之間在準(zhǔn)確度以及效率上的優(yōu)勢。GA與PSO相關(guān)參數(shù)設(shè)置如表2和表3所示，通過MATLAB運行算法程序，在6-cores 3.6 GHz CPU，32 G RAM的運行環(huán)境下(未使用多線程)，實驗結(jié)果平均值對比如表4所示。

表2 GA-Ⅰ、GA-Ⅱ與GA-Ⅲ相關(guān)參數(shù)設(shè)置

表3 PSO-Ⅰ與PSO-Ⅱ相關(guān)參數(shù)設(shè)置

表4 算法性能對比

對模型進行對比實驗后，發(fā)現(xiàn)GA-Ⅰ與PSO-Ⅰ 40次實驗均無法得到結(jié)果。主要因為初始種群數(shù)量過小，若僅生成一次初始種群，其中有可行解的概率過低；但若初始種群數(shù)量大，算法耗時會急劇上升。針對該缺陷，提出改進型遺傳算法GA-Ⅱ、GA-Ⅲ與改進型粒子群算法PSO-Ⅱ，優(yōu)化了初始種群的生成，即如果沒有可行解就重新生成一組初始種群。優(yōu)化后的GA-Ⅱ、GA-Ⅲ、PSO-Ⅱ均可得到結(jié)果，其中GA-Ⅱ與GA-Ⅲ結(jié)果與計算時間相近，PSO-Ⅱ優(yōu)于GA系算法，但準(zhǔn)確度與效率都不如B&B，原因如下：

(1)GA-Ⅱ、GA-Ⅲ在初始種群的形成、父代染色體的交叉、變異都有相對無序的隨機性操作，導(dǎo)致算法在多次迭代的過程中，并不能目標(biāo)明確地靠近全局最優(yōu)解。

(2)PSO-Ⅱ在學(xué)習(xí)因子較大的情況下，容易由于速度過高而越過最優(yōu)解，而學(xué)習(xí)因子較小時，又容易陷入局部最優(yōu)解。

(3)在初始種群形成時，由于不耽誤交期的可行解在全部解中占比較小，需要擴大初始種群大小(對于GA-Ⅰ、PSO-Ⅰ)，或多次重復(fù)獲取初始種群(對于GA-Ⅱ、GA-Ⅲ及PSO-Ⅱ)，才能基本保證初始種群中具有可行解，且當(dāng)問題規(guī)模進一步擴大時，解空間將呈階乘趨勢迅速增大，進一步壓縮可行解的比例，這將會嚴重限制該算法對于大規(guī)模訂單情形下的處理性能。

而B&B在處理該場景時，可通過產(chǎn)品交期緊迫的特性，對不可行解進行大量剪枝，從而大大縮短算法的運行時間，提高算法的效率，使大規(guī)模訂單情況的求解成為可能。因此，從優(yōu)化結(jié)果和性能上看，GA-Ⅱ、GA-Ⅱ、GA-Ⅲ均不適于求解本優(yōu)化模型，故本文將采用B&B對高頻換產(chǎn)手機裝配線的訂單調(diào)度問題進行求解。

3 案例分析

3.1 案例輸入數(shù)據(jù)

某手機裝配企業(yè)(簡稱A廠)通過自動化設(shè)備裝配4種不同型號的手機，分別記為Type1，Type2，Type3，Type4，其工藝路線兩兩不同，如表5所示，其中A～K表示不同的ADU。

表5 工藝路線信息

由表5可知，4種型號的手機裝配所需設(shè)備的類型、順序不盡相同，導(dǎo)致不同換產(chǎn)對之間的換產(chǎn)變更度不同，本文將換產(chǎn)變更度分為增減變更度和移位變更度兩部分進行研究。增減變更度指的是換產(chǎn)對之間ADU種類的增減總數(shù)，譬如Type1與Type2之間只差了一個H設(shè)備，則該換產(chǎn)對之間的增減變更度為1；移位變更度指的是換產(chǎn)對之間ADU的位置移動步數(shù)，譬如Type3與Type4之間F、G、H設(shè)備之間的順序不相同，其移動步數(shù)為3，則該換產(chǎn)對之間的移位變更度為3。不同型號之間的增減變更度以及移位變更度如表6所示。

表6 不同產(chǎn)品型號間的增減變更度KA與移位變更度KM

由于裝配線應(yīng)用的是高度自動化的ADU，因此其節(jié)拍數(shù)據(jù)能夠輕松獲得，如表7所示為4種型號產(chǎn)品的節(jié)拍時間。

表7 各型號產(chǎn)品節(jié)拍時間

從A廠收到的訂單中，選取3個不同時間段按交期時間Di從小到大排列的14條訂單數(shù)據(jù)，如表8所示。

表8 訂單數(shù)據(jù)

續(xù)表8

輸入以上數(shù)據(jù)并分別設(shè)置系數(shù)，其中換產(chǎn)時間換算系數(shù)τ=1 800，基礎(chǔ)換產(chǎn)時間T0=600，增減變更度與移位變更度影響因子分別為αA=1，αM=2，時間成本與庫存成本換算系數(shù)分別為βT=2，βS=2×10-5。

3.2 優(yōu)化結(jié)果分析

基于以上輸入數(shù)據(jù)，執(zhí)行在MATLAB編寫的算法程序，在6-cores 3.6 GHz CPU，32 G RAM的運行環(huán)境下，得到如表9所示結(jié)果，優(yōu)化前后甘特圖對比如圖3所示，圖中Proc為加工狀態(tài)，Trans為換產(chǎn)重構(gòu)狀態(tài)。

表9 調(diào)度優(yōu)化結(jié)果

觀察圖3中3組數(shù)據(jù)優(yōu)化前后的甘特圖對比，可以發(fā)現(xiàn)經(jīng)優(yōu)化后，同種型號的訂單趨于聚集到一起，傾向于連續(xù)加工同種型號，且不同型號訂單的前后連接也會傾向于換產(chǎn)變更度較低的訂單對。這是由于訂單加工時間不變，影響訂單總完成時間的主要因素為換產(chǎn)時間，而換產(chǎn)時間又取決于換產(chǎn)變更度，即換產(chǎn)前后訂單的型號差別。本算法正是以尋找總完成時間最短的訂單調(diào)度方案為主要目標(biāo)，以尋找最小庫存成本訂單調(diào)度方案為次要目標(biāo)，由此可見該優(yōu)化算法的有效性。

另外，將按照Di從小到大依次排列的14條訂單數(shù)據(jù)的原始序列放入模型求解，將所得結(jié)果與優(yōu)化結(jié)果進行對比，如表10所示。

表10 使用優(yōu)化算法前后性能對比

通過觀察3組訂單數(shù)據(jù)優(yōu)化前后性能的對比，可以發(fā)現(xiàn)經(jīng)優(yōu)化后，因縮短了訂單總完成時間，使得生產(chǎn)成本下降。實驗結(jié)果表明，該優(yōu)化算法可以有效降低多品種、小批量、交期緊迫的高頻換產(chǎn)手機裝配線的生產(chǎn)成本，縮短交付周期，更好地迎合市場的需求，減小企業(yè)資金流壓力。

3.3 敏感度分析

本文針對高頻換產(chǎn)手機裝配線的求解算法的輸入?yún)?shù)進行了敏感度分析，以測試不同訂單狀態(tài)下該算法的求解性能。

3.3.1 交期時間

理論上，交期時間Di對求解耗時有較大影響，由于本研究提出的算法是基于B&B進行求解，而其中剪枝數(shù)量將對B&B求解過程的復(fù)雜度有較大的影響。本研究針對的高頻換產(chǎn)手機裝配線具有交期緊迫這一特性，這會限制訂單在一定時間內(nèi)完成，超出時間的情況會被剪枝處理，加快運行速度。為研究交期時間Di對求解耗時的具體影響，下面將基于訂單數(shù)據(jù)b進行研究，分別對數(shù)據(jù)b中的訂單交期時間Di放寬10 h、20 h、50 h，對比算法運行時間及優(yōu)化效果。如表11所示為不同交期時間對求解結(jié)果與耗時的影響。

表11 不同交期時間對結(jié)果與耗時的影響

實驗結(jié)果表明，Di越大，條件約束越弱，運行時間越長，高頻換產(chǎn)訂單調(diào)度相對初始狀態(tài)位置變更越多，優(yōu)化效率也會隨之增大。根據(jù)這一結(jié)論，容易推導(dǎo)出一種解決因計算量過大而無法求出最優(yōu)解算例的方法：對于計算量過大的數(shù)據(jù)集，可以適當(dāng)減小Di的值。該操作將有效減少計算時間，也因為約束條件變強，使得訂單完成時間Ci更嚴格小于Di，可以使實際裝配換產(chǎn)過程中擁有更高的容錯率。

3.3.2 訂單數(shù)量

訂單數(shù)量直接影響計算量大小，是訂單排序問題的重要影響因素。為研究訂單數(shù)量n對求解耗時的具體影響，下面將基于訂單數(shù)據(jù)a進行研究，分別對數(shù)據(jù)a中的訂單數(shù)量n進行調(diào)整，對比算法運行時間及優(yōu)化效果。如表12為不同訂單數(shù)量對求解結(jié)果與耗時的影響。

表12 不同訂單數(shù)量對結(jié)果與耗時的影響

實驗結(jié)果表明，隨著n的增大，算法耗時急劇上升。根據(jù)這個結(jié)論，容易推導(dǎo)出一種解決因n過大而無法求出最優(yōu)解算例的方法：將n控制在14、15左右。如果遇到訂單數(shù)量n超過這個值的情況，可將其分為14、15左右的若干個算例。雖然訂單數(shù)量n越小，求解耗時越短，但是訂單數(shù)量n過小又會導(dǎo)致訂單重構(gòu)空間過小，最終導(dǎo)致優(yōu)化效率下降。

4 結(jié)束語

合理的訂單調(diào)度方案，對于手機裝配生產(chǎn)企業(yè)提升自身的競爭力具有重要意義。本文考慮生產(chǎn)線重構(gòu)約束及產(chǎn)品交期約束，針對其OSOP進行了如下工作：①抽象了手機裝配生產(chǎn)線模型，并對其OSOP進行了描述；②以最小化生產(chǎn)時間及庫存成本為目標(biāo)，建立了手機裝配OSOP數(shù)學(xué)模型；③基于各種算法比較，選取了數(shù)學(xué)模型的求解算法；④通過對實際案例的求解與結(jié)果分析，驗證了本OSOP求解算法的有效性及適用性，并對相關(guān)參數(shù)進行了敏感度分析。

本文的主要創(chuàng)新與貢獻如下：①基于手機裝配作業(yè)品種多、批量小及交期緊的特點，提出了一種考慮產(chǎn)品交期與產(chǎn)線重構(gòu)雙重約束的OSOP建模方法，拓展了傳統(tǒng)OSOP的應(yīng)用范圍；②基于該優(yōu)化問題規(guī)模大、可行解密度小的特點，提出了一種基于交期可行域的高效率多叉樹B&B算法，豐富了非線性0-1整數(shù)規(guī)劃問題求解方法。

作為本文研究的延續(xù)，今后將在以下幾方面對手機裝配作業(yè)OSOP進一步研究：①將研究拓展至多條手機裝配生產(chǎn)線或多車間環(huán)境，研究其訂單調(diào)度優(yōu)化問題；②考慮隨機需求、設(shè)備故障等因素的隨機環(huán)境下，手機裝配訂單調(diào)度優(yōu)化問題建模與求解；③進一步探索更高效、更大規(guī)模的優(yōu)化模型求解算法。