基于NSGA-II算法的柔性流水車間優(yōu)化調(diào)度模型的構(gòu)建與應(yīng)用

張歡歡 李繼庚 洪蒙納 滿 奕

（華南理工大學制漿造紙工程重點實驗室，廣東廣州，510640）

車間調(diào)度問題可分為單機調(diào)度問題、流水車間調(diào)度問題以及作業(yè)車間調(diào)度問題［1］。在工業(yè)生產(chǎn)領(lǐng)域中，流水車間調(diào)度問題是一個通用的問題模型［2］。柔性流水車間與實際生產(chǎn)的過程最為接近，因此對其進行研究具有重要意義。柔性流水車間的優(yōu)化調(diào)度問題中，多以求解單目標問題為主，大部分目標為最小化最大完工時間［3-5］等。然而在實際生產(chǎn)中，生產(chǎn)調(diào)度人員考慮更多的是多個目標，一般情況下，這些目標之間往往互相沖突。

由于調(diào)度問題的復(fù)雜性，目前還沒有一種通用的方法可適用于各種類型的調(diào)度問題［6］?，F(xiàn)有的求解方法大致可以歸納為以下3種：傳統(tǒng)的運籌學方法、啟發(fā)式規(guī)則方法以及智能優(yōu)化算法。傳統(tǒng)的運籌學方法一般只適用于小規(guī)模調(diào)度問題。啟發(fā)式規(guī)則方法是通過設(shè)計好一定的規(guī)則，然后將其應(yīng)用到調(diào)度過程中，從而產(chǎn)生相應(yīng)的生產(chǎn)調(diào)度方案。其具有簡單、易實現(xiàn)的特點，但在求解大規(guī)模調(diào)度問題時效率較低且無法實現(xiàn)多個目標的同時優(yōu)化。而智能優(yōu)化算法求解過程一般是先隨機生成多個調(diào)度方案，然后通過所需要優(yōu)化的目標函數(shù)以及約束條件逐漸對生成的解進行迭代優(yōu)化。因此，智能優(yōu)化算法對所求問題的依賴程度不高，可以應(yīng)用于解決各類優(yōu)化問題［7-8］。其中，快速非支配遺傳算法（NSGA-II）非常適合處理存在多個相互沖突目標、搜索空間規(guī)模大且復(fù)雜度高的優(yōu)化問題，NSGA-II 已成為近幾年最受歡迎的多目標進化算法之一［9］。

生活用紙企業(yè)的生產(chǎn)調(diào)度問題可以簡化為一種特殊的兩階段柔性流水車間調(diào)度問題。然而，不同于普通的兩階段柔性流水車間，生活用紙企業(yè)的特殊性體現(xiàn)在，前后兩段加工過程具有一定依賴性，但后加工無需等待前加工完全完成生產(chǎn)任務(wù)后再開始加工［10］。這導(dǎo)致了傳統(tǒng)的兩階段柔性流水車間模型不適用于生活用紙企業(yè)的生產(chǎn)調(diào)度問題。由于不同產(chǎn)品在生產(chǎn)過程中，造紙階段和包裝階段均存在多個設(shè)備或多條生產(chǎn)線可供選擇，因此通過優(yōu)化排產(chǎn)能夠?qū)崿F(xiàn)縮短完工時間、減少切換次數(shù)等目標。對生活用紙企業(yè)而言，由于其產(chǎn)品具有快速消費品的特點，產(chǎn)品種類規(guī)格繁多［10］，受市場影響較大，生產(chǎn)計劃變動頻繁，產(chǎn)品切換不僅使其生產(chǎn)過程能耗上升、物耗加大，也為需要穩(wěn)定生產(chǎn)的造紙階段帶來了巨大的挑戰(zhàn)［11］。造紙生產(chǎn)過程的能源消耗量約占單位產(chǎn)品總能耗的15%～20%［12］。因此，優(yōu)化生產(chǎn)調(diào)度以實現(xiàn)機器利用率最高、降低生產(chǎn)總能耗，對生活用紙企業(yè)極為重要［13］。目前，生活用紙企業(yè)更多是依靠排產(chǎn)人員的經(jīng)驗制作排產(chǎn)任務(wù)單，排產(chǎn)效率低下。

為實現(xiàn)高效優(yōu)化排產(chǎn)，降低生產(chǎn)成本、提升生產(chǎn)效率，本研究以生活用紙企業(yè)為研究對象，設(shè)計了一個具有機器約束、運輸約束、切換約束、交貨期約束的柔性流水車間作業(yè)調(diào)度模型。該模型在考慮優(yōu)化最大完工時間的同時，通過安排合理的生產(chǎn)調(diào)度優(yōu)化生產(chǎn)成本。為促進這一問題的解決，本研究將NSGA-II算法用于求解建立的生產(chǎn)調(diào)度模型，并通過一家生活用紙企業(yè)的實際生產(chǎn)案例驗證模型的可行性。

1 兩階段柔性流水車間調(diào)度建模

1.1 兩階段柔性流水車間調(diào)度問題描述

兩階段柔性流水車間調(diào)度問題的特點如下：n個工件要進行2個階段的加工，每個加工階段有m個并行機。在每個加工階段至少有2 個或2 個以上的并行機器可供使用。對于生活用紙生產(chǎn)企業(yè)而言，要求滿足以下約束條件：①所有任務(wù)都必須先在第一階段（前加工）加工，然后再到第二階段（后加工）加工；②每個任務(wù)在每個階段只能選擇該階段的1臺設(shè)備或1條生產(chǎn)線進行加工；③每臺設(shè)備或每條生產(chǎn)線在任意時刻只能加工1個任務(wù)；④每個任務(wù)在不同設(shè)備或生產(chǎn)線的加工時間，可能相同，也可能不同；⑤第一階段和第二階段之間存在一個緩沖時間。本研究為每個加工任務(wù)選擇機器或生產(chǎn)線，確定每臺設(shè)備或每條生產(chǎn)線上加工的任務(wù)以及任務(wù)的加工順序，優(yōu)化目標是成本和最大完工時間最小化。

1.2 參數(shù)定義

為方便模型的建立，列出模型的相關(guān)參數(shù)，如表1所示。其中第一階段表示造紙階段，第二階段表示包裝階段。

1.3 成本分析

本研究的成本主要包括加工成本、運輸成本、切換成本以及拖期成本。

（1）加工成本（PC）為所有設(shè)備或生產(chǎn)線對任務(wù)進行加工過程中產(chǎn)生的能源消耗，主要指進行生產(chǎn)加工時各設(shè)備或生產(chǎn)線的電力或蒸汽消耗。

（2）運輸成本（TC）為將造紙階段生產(chǎn)出來的原紙運送到包裝階段進行加工過程中產(chǎn)生的成本，主要是指小車、吊車等運輸工具執(zhí)行運輸功能時產(chǎn)生的能耗，以用電成本度量。

（3）切換成本（SC）為當前一個加工任務(wù)與后一個加工任務(wù)的產(chǎn)品類型不一致時，設(shè)備重新調(diào)參數(shù)過程中產(chǎn)生的電力費用。

表1 模型相關(guān)參數(shù)表

（4）拖期成本（DC）為當任務(wù)的完工時間比交貨期晚時，所需要額外支付的違約金費用。

（5）總成本（Cost）為加工成本、運輸成本、切換成本以及拖期成本之和。

1.4 以成本和最大完工時間最小化為目標的生產(chǎn)調(diào)度模型

本研究將成本最小化作為車間調(diào)度的優(yōu)化目標之一，同時將任務(wù)的最大完工時間作為另一個優(yōu)化目標，從而不僅實現(xiàn)成本的優(yōu)化，也進一步實現(xiàn)能效優(yōu)化。具體的生產(chǎn)調(diào)度模型如下所示。

目標函數(shù)為：

其中，式（6）表示目標函數(shù)。式（7）表示任務(wù)i在第一階段只能被其中任意一臺機器加工，并且必須加工1次。式（8）表示任務(wù)i在第二階段只能被其中任意一臺機器加工，并且必須加工1 次。式（9）表示一臺機器j只能加工一個任務(wù)i。式（10）表示任務(wù)i的完工時間。式（11）表示在2個階段之間必須存在一個時間間隔，這個時間間隔與任務(wù)量大小、第一與第二階段機器的加工速度有關(guān)。

2 模型的求解與驗證

2.1 NSGA-II算法

NSGA-II 算法是Deb 在非支配排序遺傳算法的基礎(chǔ)上提出的［14］。它非常適合用于處理搜索空間規(guī)模大且復(fù)雜度高的多目標優(yōu)化問題。本研究有2個目標函數(shù)，屬于多目標優(yōu)化問題。NSGA-II 混算法的流程如圖1所示，其基本過程可以簡述如下：首先，需要對數(shù)據(jù)進行預(yù)處理并導(dǎo)入到MATLAB中，計算出模型所需要的基礎(chǔ)數(shù)據(jù)；其次，設(shè)置算法參數(shù)、對種群進行初始化并計算適應(yīng)度值；最后，執(zhí)行選擇操作、交叉操作以及變異操作，并將結(jié)果保存輸出。

2.2 數(shù)據(jù)來源和模型參數(shù)設(shè)置

采集廣東省某生活用紙企業(yè)歷史生產(chǎn)計劃表中的178個任務(wù)數(shù)據(jù)，其中任務(wù)類型有20種。該生活用紙企業(yè)前加工階段有6 條生產(chǎn)線，后加工階段有7 條生產(chǎn)線。為了最小化加工成本、運輸成本、切換成本、延期成本，實現(xiàn)快速排產(chǎn)和滿足客戶對產(chǎn)品的時間需求，需要對任務(wù)的最大完工時間、切換次數(shù)以及成本進行優(yōu)化。

任務(wù)加工時間根據(jù)任務(wù)量大小以及機器的實際運行速度計算得到，每條生產(chǎn)線的速度范圍如表2 所示。本研究中，機器設(shè)置時間均采用在實際范圍內(nèi)隨機產(chǎn)生的方式，切換時間服從［10 min，60 min］均勻分布。每條生產(chǎn)線的單位時間切換成本如表3 所示。運輸成本與生產(chǎn)線的距離有關(guān)，單位產(chǎn)品的運輸成本如表4 所示。表4 中的數(shù)字為原紙的單位運輸成本，如（1#，1#，4）表示1 t原紙從造紙階段的1號生產(chǎn)線運送到包裝階段的1號生產(chǎn)線的單位運輸成本為4 元。延期成本由延期時間與延期懲罰因子βi計算得到，延期時間和任務(wù)的完工時間以及交貨時間相關(guān)。對于延期懲罰因子βi，令延期懲罰因子βi在［0.002，0.006］ 之間任取一個數(shù)值［15］。

表2 每條生產(chǎn)線的速度范圍

圖1 NSGA-II算法流程圖

表3 每條生產(chǎn)線的單位時間切換成本

表4 單位產(chǎn)品運輸成本 元/t

NSGA-II 的參數(shù)設(shè)置如下：種群大小為100，交叉概率為0.9，變異概率為0.1，NSGA-II的最大迭代次數(shù)為50。此外，本研究中采用的電單價為0.7元/kWh。

2.3 結(jié)果與分析

圖2和圖3是運行1次NSGA-II得到的解的最大完工時間迭代圖和生產(chǎn)成本迭代圖。從圖2 和圖3 可以看到，NSGA-II 尋找最優(yōu)解的能力較優(yōu)，且算法的收斂速度快。圖4為NSGA-II運行7次解的二維散點圖。從圖4 可以看到，NSGA-II 求得的解分布均勻，即解的均勻性良好。

圖2 NSGA-II進化50次的最大完工時間迭代圖

圖3 NSGA-II進化50次的生產(chǎn)成本迭代圖

圖4 NSGA-II運行7次解的二維散點圖

本研究對運行2次獲得的解求取平均值，結(jié)果如表5所示。從表5可以得到，NSGA-II求得的調(diào)度方案的最大完工時間比人工排產(chǎn)方案縮短了1683 min，總生產(chǎn)成本比人工排產(chǎn)方案降低了226557元。表6展示了由NSGA-II和人工排產(chǎn)方案得到的加工成本、切換成本、運輸成本以及延期成本。從表6可以看到，與人工排產(chǎn)方案相比，模型NSGA-II求得的排產(chǎn)方案中加工成本以及延期成本明顯減少。因此，NSGA-II 求得的排產(chǎn)方案明顯優(yōu)于人工排產(chǎn)方案。也進一步說明了，本研究使用的NSGA-II 算法的有效性。NSGA-II解優(yōu)于人工排產(chǎn)方案的占比圖如圖5 所示。從圖5 可以得到，與人工排產(chǎn)方案相比，NSGA-II 得到的排產(chǎn)結(jié)果縮短了約6.5%的最大完工時間，降低了約4.7%的總生產(chǎn)成本。

表5 NSGA-II和人工排產(chǎn)求得的解

表6 NSGA-II和人工排產(chǎn)得到的加工、切換、運輸以及延期成本表

圖5 NSGA-II解優(yōu)于人工排產(chǎn)方案的占比圖

數(shù)據(jù)的準確性會直接影響排產(chǎn)結(jié)果。因而在實際應(yīng)用中，可以借助企業(yè)已有的一些系統(tǒng)（ERP、MES等）來獲取更加準確及時的排產(chǎn)基礎(chǔ)數(shù)據(jù)信息。例如，前加工和后加工階段設(shè)備的運行速度不是一成不變的，因而每次調(diào)用排產(chǎn)模型時，設(shè)備速度的取值就可以采用從MES系統(tǒng)中獲取的當前值，以便于更加準確地計算出生產(chǎn)任務(wù)的最大完工時間，從而提高排產(chǎn)模型的準確性與實用性。

3 結(jié) 論

本研究對生活用紙企業(yè)的高效優(yōu)化排產(chǎn)問題進行了描述，建立了以生產(chǎn)成本和最大完工時間最小化為優(yōu)化目標的兩階段柔性流水車間調(diào)度優(yōu)化模型。用快速非支配遺傳算法（NSGA-II）求解出最優(yōu)生產(chǎn)計劃方案。該模型可應(yīng)用于不同設(shè)備數(shù)量和設(shè)備規(guī)格的生活用紙企業(yè)，可靈活調(diào)整訂單數(shù)量，設(shè)備功率、速度以及數(shù)量等，更符合生活用紙企業(yè)生產(chǎn)過程中的實際需求。通過該模型求得的排產(chǎn)方案能明顯地縮短任務(wù)的最大完工時間，節(jié)省生產(chǎn)成本和人力資源，為企業(yè)帶來了明顯的效益。此外，該模型的工業(yè)實現(xiàn)還需要包括與其他系統(tǒng)的接口、數(shù)據(jù)庫設(shè)計，也需要完善如數(shù)據(jù)的集成、圖形化用戶界面、報表集成等功能。