服裝企業(yè)包裝訂單分配排序優(yōu)化模型及其快速非支配遺傳算法求解

潘佳豪， 周其洪， 岑均豪， 李姝佳， 周申華

(1. 東華大學(xué) 機(jī)械工程學(xué)院， 上海 201620； 2. 東華大學(xué) 數(shù)字化紡織服裝技術(shù)教育部工程研究中心， 上海 201620； 3. 廣州盛原成自動化科技有限公司， 廣東 廣州 511400)

在制造業(yè)全球化程度不斷加深，工業(yè)化以及信息化不斷進(jìn)步的背景下，從生產(chǎn)到出貨的各個環(huán)節(jié)的細(xì)節(jié)入手，提高效率，縮短產(chǎn)品交付期將成為企業(yè)提高競爭力的有效手段。我國紡織服裝行業(yè)經(jīng)過近年來的發(fā)展，硬件自動化已趨成熟，部分企業(yè)正在向智能化邁進(jìn)；但在軟件方面，許多紡織服裝制造企業(yè)的制造管理系統(tǒng)(MES)尚不成熟，計劃和成本控制對象細(xì)化程度不足，與企業(yè)資源計劃系統(tǒng)(ERP)的集成以及數(shù)據(jù)互聯(lián)存在一定的問題[1]。

當(dāng)前的市場環(huán)境下，客戶需求逐漸多樣化，對于款式更迭導(dǎo)致生產(chǎn)內(nèi)容常變的服裝生產(chǎn)企業(yè)更是如此。當(dāng)下的服裝生產(chǎn)企業(yè)采用訂單式生產(chǎn)模式(MTO)，其運(yùn)營模式具有多品種、多急單插單等特點(diǎn)[2]。訂單包裝是服裝產(chǎn)品出貨前的最后步驟，需結(jié)合訂單與庫存情況安排包裝順序，提取對應(yīng)產(chǎn)品組合并送至包裝線打包，在規(guī)定時間內(nèi)完成出貨?？蛻羝髽I(yè)的包裝需求組合多樣，當(dāng)一定時間內(nèi)多個訂單同時到達(dá)時，訂單組成狀況較為復(fù)雜。針對客戶的需求整理訂單、分配包裝任務(wù)、優(yōu)化訂單排序就顯得尤為重要。

并行機(jī)分配與訂單排序問題涉及到任務(wù)分配、平衡、優(yōu)化排序等多個方面，是一類NP-hard問題。在訂單分批、分配、排序的思路方面，一般采用根據(jù)目標(biāo)和約束條件建立混合整數(shù)規(guī)劃模型(MILP)的方法建立合理的數(shù)學(xué)模型，以解決目標(biāo)多種多樣的分配調(diào)度問題[3]；基于精益生產(chǎn)(JIT)裝配模式的思想可用于對大批量多品種訂單次序進(jìn)行優(yōu)化，提高訂單分揀的效率[4]。

在算法方面，遺傳算法(GA)及其改進(jìn)后的非支配遺傳算法(NSGA-Ⅱ)[5-7]、果蠅優(yōu)化算法[8]、多目標(biāo)進(jìn)化算法[9]、貪婪算法[10]等較常用的智能優(yōu)化算法在解決以縮短交期或平衡排序為目標(biāo)的訂單排序動態(tài)優(yōu)化問題方面得到了較多的應(yīng)用；于此同時，新的算法也在不斷提出。固定變量列表算法(FVLA)用于解決不能忽略與序列相關(guān)的設(shè)置時間的顧客訂單調(diào)度問題，具有優(yōu)秀的求解質(zhì)量[11]；在杜鵑搜索算法(CSA算法)基礎(chǔ)上改進(jìn)的算法(ICSA)用于求解并行機(jī)最大完成時間問題，相對于多種常用算法都具有更優(yōu)的求解性能[12]；在樽海鞘群優(yōu)化算法(SSA算法)基礎(chǔ)上改進(jìn)的(SSAFA)算法用于求解以最小化最大完工時間的帶啟動時間非相關(guān)并行機(jī)調(diào)度問題(UPMSP)，在不同規(guī)模大小的算例求解上均有較好的性能[13]。從已有研究來看，將服裝包裝線訂單分配與排序問題轉(zhuǎn)換為相近的并行機(jī)調(diào)度問題，再應(yīng)用收斂性好的智能優(yōu)化算法進(jìn)行排序求解是解決問題的關(guān)鍵思路。

本文針對紡織服裝生產(chǎn)企業(yè)包裝出貨過程的優(yōu)化需求，為解決包裝車間中包裝訂單在包裝線上分配以及排序問題，對服裝產(chǎn)品訂單包裝出貨過程中的問題特點(diǎn)與約束條件進(jìn)行分析并建立相應(yīng)的調(diào)度優(yōu)化模型，運(yùn)用NSGA-Ⅲ算法對其進(jìn)行優(yōu)化求解，以實(shí)現(xiàn)包裝車間包裝線工作平衡和出貨時間優(yōu)化。

1 服裝企業(yè)包裝訂單排序優(yōu)化模型

1.1 紡織服裝生產(chǎn)企業(yè)訂單包裝排產(chǎn)現(xiàn)狀

紡織服裝生產(chǎn)企業(yè)采取面向訂單為主，輔以部分面向庫存(MTS)的生產(chǎn)方式進(jìn)行產(chǎn)品的生產(chǎn)，發(fā)貨時根據(jù)客戶訂單需求對相應(yīng)數(shù)量種類組合的產(chǎn)品進(jìn)行出庫、裝箱并發(fā)貨?？紤]到一定時間內(nèi)到來的訂單交貨期不盡相同，當(dāng)前企業(yè)常用交貨期優(yōu)先(EDD優(yōu)先)規(guī)則對包裝訂單進(jìn)行分配，即在接收到一系列包裝出庫訂單時，首先采用EDD順序?qū)υ摻M訂單進(jìn)行預(yù)先排序，然后從交貨期最早的訂單開始分配包裝線，直到所有包裝線均有一個訂單在處理；當(dāng)有包裝線完成包裝時，將未分配的EDD順序最前訂單分配到該空閑包裝線，依次類推，直到該組訂單全部完成。此分配與排序方式帶有部分貪婪算法的性質(zhì)，在一定程度上可保證交期，但無法盡可能縮短總處理時間，且部分訂單可能出現(xiàn)物流無法彌補(bǔ)的長拖期時間。

1.2 服裝企業(yè)訂單包裝出貨過程問題描述

對于服裝企業(yè)的包裝車間，一般存在多條包裝線可用，在一個時間段中的多條包裝訂單將按照一定策略被分配到可用的包裝線上進(jìn)行包裝。此類訂單分配與排序問題特點(diǎn)如下：n個訂單分屬于g個客戶，需要分配到m條包裝線上完成包裝，每個訂單可在任意1條包裝線上進(jìn)行包裝。就企業(yè)當(dāng)前生產(chǎn)實(shí)際情況而言，還需要滿足以下約束條件：1)為便于包裝時單個訂單多個條目的后續(xù)整理，每個訂單的所有包裝條目需要在1條包裝線上完成，不允許拆分；2)任意1條包裝線同一時刻只能對1個訂單進(jìn)行包裝；3)由于不同客戶的條碼識別方式不同，當(dāng)同一條包裝線上相鄰的2個訂單分屬不同客戶時，中間需要機(jī)器調(diào)整時間；4)每條包裝線的運(yùn)行速度基本相同。本文將以最小化最大完工時間以及最小化訂單總拖期為目標(biāo)，對短時間內(nèi)到來的多條包裝訂單分配相應(yīng)的包裝線，確定每條包裝線上訂單的包裝順序。

1.3 問題假設(shè)與參數(shù)定義

從問題實(shí)際情況和抽象化數(shù)學(xué)模型的需求出發(fā)，模型的假設(shè)條件如下：

1)一個訂單在包裝進(jìn)行時不中斷，且不允許分割到多條包裝線上處理；

2)由于不同客戶的條碼識別方式有差異，訂單按客戶的不同劃分類別，對于不同類別訂單，包裝線需要對應(yīng)類別的機(jī)器調(diào)整時間，且當(dāng)前時間段內(nèi)每條包裝線上安排的第1個訂單默認(rèn)需要調(diào)整時間；

3)訂單上線包裝前的準(zhǔn)備工作可與機(jī)器調(diào)整同時進(jìn)行，在包裝1個訂單其中1個條目的同時可以進(jìn)行其他條目的準(zhǔn)備工作，從而忽略單個訂單之內(nèi)準(zhǔn)備相關(guān)的時間；

4)訂單分配方案確定后，不考慮緊急訂單的插單。

1.4 包裝訂單分配排序數(shù)學(xué)模型

基于以上參數(shù)，同時考慮包裝線機(jī)器分配及機(jī)器調(diào)整時間，本文以最小化最大完工時間、最小化訂單總拖期為優(yōu)化目標(biāo)，針對包裝訂單分配排序問題建立數(shù)學(xué)模型。

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

F1=min(Cmax)

(1)

(2)

其中，式(1)表示第1個優(yōu)化目標(biāo)為最小化最大完成時間；式(2)表示第2個優(yōu)化目標(biāo)是最小化被安排的所有訂單總拖期。

2)數(shù)學(xué)關(guān)系和約束條件。為對訂單數(shù)據(jù)進(jìn)行簡化處理，需要確定1條訂單的整體處理時間，訂單j的包裝處理時間計算式：

pj=ajta+bjtb

(3)

機(jī)器調(diào)整決策約束：

(4)

(5)

訂單安排不重復(fù)約束：

(6)

(7)

(8)

(9)

其中：式(8)與式(9)表明2個決策變量均為0～1決策變量。

包裝線i上第h位置包裝的訂單對應(yīng)的機(jī)器調(diào)整時間、處理時間和完成時間：

(10)

(11)

C(h)i=C(h-1)i+S(h)i+P(h)i

(12)

C(0)i=0

(13)

完成時間、交貨期、延誤變量、拖期時間的數(shù)學(xué)關(guān)系：

(14)

C(h)i-d(h)i≤LU(h)i

(15)

T(h)i=U(h)i(C(h)i-d(h)i)

(16)

最大完成時間和總拖期時間：

Cmax=max(C(h)i)

(17)

(18)

2 基于NSGA-Ⅲ算法的模型求解

2.1 NSGA-Ⅲ算法

NSGA-Ⅲ算法是在NSGA-Ⅱ算法基礎(chǔ)上改進(jìn)的多目標(biāo)優(yōu)化算法，是基于參考點(diǎn)非支配排序方法的進(jìn)化多目標(biāo)優(yōu)化算法[14]，其強(qiáng)調(diào)非主導(dǎo)但接近一組提供的參考點(diǎn)的總體成員，在多目標(biāo)測試問題上能得出較好的結(jié)果。本文中使用的NSGA-Ⅲ算法流程如圖1所示。

圖1 NSGA-Ⅲ算法流程圖Fig.1 NSGA-Ⅲ algorithm flow chart

2.2 個體編碼與解碼方法

從訂單分配排序模型中需要兼顧訂單順序與機(jī)器次序的角度出發(fā)，本文使用隨機(jī)正數(shù)序列與自然數(shù)映射的方法進(jìn)行個體編碼,如圖2所示。將順序排列大小為n的訂單序列與同樣大小但順序隨機(jī)的正數(shù)序列{rn}一一對應(yīng)，此正數(shù)序列{rn}即為單一個體的編碼。與此編碼方法相應(yīng)的一維排序方面的解碼方法，即是對編碼的正數(shù)序列{rn}按照大小順序重新排序，則與其相對應(yīng)的訂單序列也將得到對應(yīng)調(diào)整，從而得到一組訂單排序序列。為得到伴隨包裝線分配的訂單序列，還需要結(jié)合輪盤賭選擇法對上述一維排序訂單序列進(jìn)行再處理，方法如下。

圖2 個體編碼與排序解碼Fig.2 Individual encoding and sort decoding

1)記順序排序后的正數(shù)序列為{rrn}，對?1≤j

(19)

(20)

2)將區(qū)間[0,1]按照包裝線數(shù)量均分為m個區(qū)間，每條包裝線對應(yīng)的選擇取值li為

(21)

當(dāng)訂單對應(yīng)的累積概率q(j)∈(li-1,li]時，訂單j即被分配到包裝線i上，由此可對每個訂單進(jìn)行相應(yīng)分配，得到可行的分配與排序方案。

2.3 交叉策略

結(jié)合上述隨機(jī)正數(shù)序列編碼方式的特點(diǎn)考慮，本文采用單點(diǎn)的部分匹配交叉方式(PMX)進(jìn)行染色體的交叉操作。交叉操作的過程示例如圖3所示。圖中提供了兩父代個體的訂單序號(第1行)與其對應(yīng)的隨機(jī)數(shù)編碼序列(第2行)。假設(shè)訂單數(shù)量n=8，兩父代染色體在第3個位置起發(fā)生交叉。由于編碼的隨機(jī)性，從圖中可看出，僅單點(diǎn)交叉即可產(chǎn)生與父代有顯著差異的子代個體，另外，由于交叉點(diǎn)位置選取的隨機(jī)性，交叉點(diǎn)越接近染色體兩端，子代個體與父代個體之間的差異就越小，因此在對所有參與交叉的父代個體隨機(jī)選擇交叉位置的情況下，交叉操作將產(chǎn)生與父代接近程度不同的子代。

圖3 單點(diǎn)PMX交叉操作示例及交叉效果Fig.3 Example and effects of single-point PMX crossover

2.4 變異策略

本文采取針對個體編碼的基因值進(jìn)行均勻變異的方法，基于變異概率選擇一定數(shù)量的父代個體變異生成子代個體。變異的操作方法如圖4所示。1)隨機(jī)選擇個體編碼序列{rn}的1個基因值；2)隨機(jī)生成位于[rmin-δ,rmax+δ]區(qū)間內(nèi)的1個新實(shí)數(shù)，以此替換原先的基因值。其中：rmin、rmax分別為染色體編碼序列的最小值、最大值，δ為一個小量，此處取δ=0.01(rmax-rmin)，用于保證變異后的基因值有概率在重排后位于重排序列的兩端。

圖4 變異操作示例Fig.4 Example of mutation

3 實(shí)例求解驗證

3.1 數(shù)據(jù)來源與部分模型參數(shù)設(shè)置

本文收集浙江一個圍巾生產(chǎn)企業(yè)數(shù)據(jù)庫中部分待包裝訂單數(shù)據(jù)，訂單種類(客戶種類)分為3種(1*、2*、3*)。該企業(yè)包裝車間目前有2條包裝線，各包裝線上機(jī)器的配置相同，3種類型訂單對應(yīng)的機(jī)器調(diào)整時間Sg=[0.6 0.5 0.4](單位：h)，包裝線上單條圍巾的平均裝箱時間ta=8 s，包裝過程平均換箱時間tb=15 s。選取一定時間內(nèi)到達(dá)的15個包裝訂單，根據(jù)式(3)，利用數(shù)據(jù)表中的裝箱數(shù)量與圍巾包裝數(shù)量并結(jié)合ta、tb，計算出各訂單的包裝處理時間。各訂單對應(yīng)類型、數(shù)量、交貨期、包裝處理時間等數(shù)據(jù)如表1所示。其中部分訂單包含裝箱數(shù)不同的多種裝箱類型，此處假設(shè)系統(tǒng)在讀取單條訂單數(shù)據(jù)時可自動處理多種裝箱類型的變化，將改變造成的時間影響限定為一個較小值，保證訂單處理時間仍可按照式(3)近似處理。

表1 模型驗證算例數(shù)據(jù)Tab.1 Data of model validation examples

將此15個訂單數(shù)據(jù)按照現(xiàn)階段企業(yè)常用的EDD優(yōu)先規(guī)則進(jìn)行分配排序，得到的方案、完成時間、拖期情況如表2所示?？煽闯?，EDD優(yōu)先規(guī)則排序能夠盡可能滿足大部分訂單的交期需求，但2號訂單有11.393 5 h的較長拖期，14號訂單也有3.919 7 h的拖期，較長的拖期將對后續(xù)物流發(fā)貨造成影響，導(dǎo)致客戶收貨推遲。

表2 EDD優(yōu)先規(guī)則分配排序方案Tab.2 Assignment sorting scheme according to EDD rule

3.2 優(yōu)化參數(shù)設(shè)置與結(jié)果分析

本文采用MatLab R2016a編譯軟件編寫與執(zhí)行NSGA-Ⅲ算法程序，NSGA-Ⅲ的各項參數(shù)設(shè)置如下：種群大小NP=100，交叉概率Pc=0.9，變異概率Pm=0.1，參考點(diǎn)劃分?jǐn)?shù)為10，NSGA-Ⅲ的最大迭代次數(shù)為150。對上述算例運(yùn)行1次NSGA-Ⅲ，得到的最大完成時間和總拖期進(jìn)化情況分別如圖5所示。

其中種群最優(yōu)時間表長度在算法執(zhí)行初期快速收斂，種群最小總拖期也在50代之前即趨于穩(wěn)定，為更直觀地顯示2項目標(biāo)函數(shù)的綜合進(jìn)化情況，此處設(shè)定以下函數(shù)作為個體的綜合適應(yīng)度函數(shù)：

(22)

圖6為本次優(yōu)化運(yùn)行過程相應(yīng)的綜合適應(yīng)度進(jìn)化情況?？煽闯鲈撍惴ㄔ谇捌诳焖偈諗?，且直到第80代都有優(yōu)化解涌現(xiàn)，第80代后種群達(dá)到相對最優(yōu)。

圖6 綜合適應(yīng)度迭代圖Fig.6 Integrated fitness iteration diagram

經(jīng)150代進(jìn)化與選擇后，最終輸出的最優(yōu)前沿種群2目標(biāo)函數(shù)值集中于1條線(Pareto前沿)上的多個點(diǎn)，如圖7所示。表3示出幾種對應(yīng)的分配排序方案與拖期情況。

圖7 優(yōu)化后種群兩目標(biāo)函數(shù)值分布Fig.7 Values distribution of two objective functions of optimized population

表3 優(yōu)化后結(jié)果對應(yīng)方案Tab.3 Schemes corresponding to optimized results

與按EDD規(guī)則分配排序相比，根據(jù)本文數(shù)學(xué)規(guī)劃模型輸出的結(jié)果在縮短了最大完工時間的同時有效地控制了拖期，幾種優(yōu)化方案的平均最大完工時間相較于按EDD規(guī)則的方案縮短了4.7%，且所有解的拖期均小于4 h。由于模型中所指訂單的交貨期實(shí)質(zhì)上是訂單應(yīng)當(dāng)發(fā)貨的時間，對于延誤時間在數(shù)小時內(nèi)的情況可在物流上設(shè)法彌補(bǔ)，盡可能保證客戶收貨時間在客戶要求范圍內(nèi)，因此NSGA-Ⅲ求解出的方案均為可行方案，實(shí)際選擇時可根據(jù)物流等條件進(jìn)行抉擇。

4 結(jié)束語

本文針對服裝企業(yè)訂單包裝出貨過程中的包裝任務(wù)分配與排序問題進(jìn)行了研究，建立了以最小化最大完成時間和最小化訂單總拖期時間為目標(biāo)、考慮機(jī)器分配及調(diào)整時間的包裝訂單分配排序數(shù)學(xué)模型，并采用基于參考點(diǎn)的快速非支配遺傳算法(NSGA-Ⅲ)求解出優(yōu)化的訂單分配排序方案。將該模型與求解方法應(yīng)用于相關(guān)企業(yè)具體案例的分配排序方案求解，驗證了該方法相較于當(dāng)前企業(yè)常用的EDD規(guī)則分配排序法能夠給出在最大完成時間和訂單拖期情況2個方面都更具優(yōu)越性的方案。

該模型可通過調(diào)整設(shè)備數(shù)量、設(shè)備速度、求解訂單數(shù)量，用于解決不同包裝車間規(guī)模的紡織服裝生產(chǎn)企業(yè)的包裝出貨訂單分配排序問題，而且可通過完善與企業(yè)ERP系統(tǒng)、數(shù)據(jù)庫的數(shù)據(jù)獲取過程，取得更準(zhǔn)確的計算數(shù)據(jù)，集成到企業(yè)MES系統(tǒng)中，減少企業(yè)在排產(chǎn)、庫存、物流等方面的管理成本，提高生產(chǎn)效率。

FZXB