張歡歡 李繼庚 洪蒙納 滿(mǎn) 奕

（華南理工大學(xué)制漿造紙工程重點(diǎn)實(shí)驗(yàn)室，廣東廣州，510640）

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

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

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

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

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

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

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

1.2 參數(shù)定義

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

1.3 成本分析

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

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

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

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

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

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

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

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

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

目標(biāo)函數(shù)為：

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

2 模型的求解與驗(yàn)證

2.1 NSGA-II算法

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

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

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

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

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

圖1 NSGA-II算法流程圖

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

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

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

2.3 結(jié)果與分析

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

圖2 NSGA-II進(jìn)化50次的最大完工時(shí)間迭代圖

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

圖4 NSGA-II運(yùn)行7次解的二維散點(diǎn)圖

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

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

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

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

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

3 結(jié) 論

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