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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2)由于不同客戶的條碼識別方式有差異，訂單按客戶的不同劃分類別，對于不同類別訂單，包裝線需要對應類別的機器調整時間，且當前時間段內每條包裝線上安排的第1個訂單默認需要調整時間；

3)訂單上線包裝前的準備工作可與機器調整同時進行，在包裝1個訂單其中1個條目的同時可以進行其他條目的準備工作，從而忽略單個訂單之內準備相關的時間；

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

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

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

1)目標函數(shù):

F1=min(Cmax)

(1)

(2)

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

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

pj=ajta+bjtb

(3)

機器調整決策約束：

(4)

(5)

訂單安排不重復約束：

(6)

(7)

(8)

(9)

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

包裝線i上第h位置包裝的訂單對應的機器調整時間、處理時間和完成時間：

(10)

(11)

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

(12)

C(0)i=0

(13)

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

(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-Ⅱ算法基礎上改進的多目標優(yōu)化算法，是基于參考點非支配排序方法的進化多目標優(yōu)化算法[14]，其強調非主導但接近一組提供的參考點的總體成員，在多目標測試問題上能得出較好的結果。本文中使用的NSGA-Ⅲ算法流程如圖1所示。

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

2.2 個體編碼與解碼方法

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

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

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

(19)

(20)

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

(21)

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

2.3 交叉策略

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

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

2.4 變異策略

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

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

3 實例求解驗證

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

本文收集浙江一個圍巾生產(chǎn)企業(yè)數(shù)據(jù)庫中部分待包裝訂單數(shù)據(jù)，訂單種類(客戶種類)分為3種(1*、2*、3*)。該企業(yè)包裝車間目前有2條包裝線，各包裝線上機器的配置相同，3種類型訂單對應的機器調整時間Sg=[0.6 0.5 0.4](單位：h)，包裝線上單條圍巾的平均裝箱時間ta=8 s，包裝過程平均換箱時間tb=15 s。選取一定時間內到達的15個包裝訂單，根據(jù)式(3)，利用數(shù)據(jù)表中的裝箱數(shù)量與圍巾包裝數(shù)量并結合ta、tb，計算出各訂單的包裝處理時間。各訂單對應類型、數(shù)量、交貨期、包裝處理時間等數(shù)據(jù)如表1所示。其中部分訂單包含裝箱數(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ī)則進行分配排序，得到的方案、完成時間、拖期情況如表2所示?？煽闯?，EDD優(yōu)先規(guī)則排序能夠盡可能滿足大部分訂單的交期需求，但2號訂單有11.393 5 h的較長拖期，14號訂單也有3.919 7 h的拖期，較長的拖期將對后續(xù)物流發(fā)貨造成影響，導致客戶收貨推遲。

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

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

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

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

(22)

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

圖6 綜合適應度迭代圖Fig.6 Integrated fitness iteration diagram

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

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

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

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

4 結束語

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

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

FZXB