基于制絲生產單元的智能調度模型研究與應用

李 凡，李 斌，衛建斌

（紅云紅河集團紅河卷煙廠，云南 紅河州 652399）

0 引言

隨著工業 4.0的變革，信息化技術對現代工廠的發展產生了巨大的影響，智能工廠概念的提出，使得物聯網、大數據、邊緣計算、人工智能等先進技術逐步引入到工廠的管理、辦公、甚至生產自動化之中，從而以技術手段實現規范企業管理、提升工作效率的目標[1]。

以卷煙行業為例，目前卷煙制造行業根據“按照訂單組織生產”的特點，對卷煙生產的柔性制造[2]以及智能生產調度提出了更高的要求。卷煙制造過程分為制絲生產及卷包生產，制絲生產為典型的流程型制造，與離散工業相比，不如離散工業那樣產品可以單件計數，制造過程易于數字化；制絲的生產過程涉及物理、化學反應，部分原料成分、設備狀態及工藝參數難以實時獲取，且生產過程是連續的，中間任一環工序出現問題，則會影響整條生產線的生產效率，從而形成了測量難、建模難、優化決策困難等問題。

因此，針對生產訂單多規格、小批量的特點，結合制絲線生產能力，合理組織生產，調度訂單生產順序，從而節約生產過程成本，節約生產時間，是提高生產效率的目標。然而，目前的生產計劃制定大多依靠專家進行人工調度，采用經驗方法，可經驗的積累需要時間，而在市場化經濟的今天，時間就是金錢，制絲調度問題實際上是一個較為復雜的實際問題，需要考慮產線的生產能力、緩沖、設備情況等各種狀態，對此問題，[3]提出，將生產調度問題以層次劃分，細化問題規模，逐步求解，目前針對卷煙生產調度，研究人員通過提取問題特點，將其與流水線調度經典問題結合起來，徐永虎等人[4]提出了一種柔性制絲線排產算法，分析煙草排產工藝流程和約束規則設計架構模型；[5]提出了一種面向分組加工的煙草生產調度模型，以仿真模型優化排產調度設計；[6]設計出一種基于生產時間的二重有線分配啟發式算法，這些算法大部分從整個生產過程入手，統一看待整條制絲線、卷包線的生產計劃問題，分析粒度大部分只到大的生產單元，在實際生產過程中，關鍵生產單元的優化對于整條生產線的生產影響是明顯的，因此基于生產單元內部的調度問題也需要進行考慮。

因此本文針對制絲煙片預處理生產單元的訂單調度問題，結合實際特點構建調度模型，將現實生產狀況映射到流程型流水線調度模型之中，利用模擬退火算法優化的遺傳算法求解訂單執行及調度順序，再利用實際算例進行驗證，為制絲預處理段的調度優化提供解決思路。

1 問題分析

近年以來，隨著客戶的需求逐步向中小批量、個性化改變，產品生產周期縮短，交貨時間提前等問題使得傳統的大批量生產模式受到了新的挑戰。單元生產模式[7]作為精益生產的一種方式，目前正廣泛應用于制絲生產過程中。其主要特點是產品族概念的提出，將不同品種的產品按照特點劃分為產品族，針對產品族的工藝特點從而進行高效的設備布局，再按照柔性設備與單元自治的組織分工模式，從而實現生產運作的高效、快速和靈活等目標。

卷煙生產的要點在于深化分組處理，充分發揮原料使用價值，從而改善產品質量[8]，以生產單元為單位的生產能夠有效地提高卷煙生產的效率。在制絲過程中，煙片預處理階段不僅涉及到原煙的入庫、流程化處理，還涉及到配葉貯葉過程，有原料的輸入，也有煙片半成品的輸出。根據目前卷煙生產工藝規范，主要分為備料、開箱和計量、切片、松散回潮、煙片預配、篩分和加料以及配葉貯葉共7個階段，如圖 1所示。在實際的制絲車間中，它是制絲流程的一個起點，屬于關鍵生產單元，因此針對煙片預處理階段的調度優化，對于整個制絲生產的效率都有一定提升。

圖1 煙片預處理段工藝流程Fig.1 Process flow of pre-treatment section of cigarette

在實際生產中，由于特殊工藝需求，在生產過程中存在許多規則與約束，煙片預處理階段的調度目標是獲得成本最低的批次生產安排，在生產過程中，生產成本與生產時間密切相關，在保證產品質量的前提下，應盡量提高設備利用率，減少設備等待，從而使得總生產時間最短，受到如下幾方面的約束：

（1）牌號加工優先級約束

針對生產訂單的差異，不同牌號的卷煙都具有對應的葉組配方，并依照訂單批次進行生產，不同牌號進行批次切換時成本不同，由高端批次向低端批次切換時，由于不需要生產線的清潔，因此成本較低；反之成本較高。

（2）設備加工能力約束

在按照工序生產時，針對一批物料，不同設備具有固定加工能力，加工時間固定。

（3）緩存約束

在工序生產過程中，一部分工序之間存在固定容量的儲柜可以進行緩存，且保持FIFO（先進先出）原則。

（4）加工路徑約束

對于制絲生產，不同批次具有固定的加工路徑和加工設備，保持先進先出原則。

煙片預處理段具有以下特點：

（1）各個批次的原煙依次通過每一道工序，且順序相同；

（2）不同批次的原煙加工時間已知；

（3）每臺設備在每個時刻只加工一批原煙；

（4）每批原煙只在每臺設備中加工一次。

由上可知，煙片預處理段的調度充分滿足典型的批量受限的有限緩沖區流水車間調度問題（Flow-Shop Scheduling Problem, FSSP）特點，這是一個經典的 NP（Non-deterministic Polynomial）問題，難以直接求解。

2 基于生產單元的制絲預處理生產調度模型

2.1 模型設計

以 FSSP的角度分析煙葉預處理段生產調度過程，可將其抽象為數學描述：

在m臺設備上需要加工n個訂單，每個訂單都有m道工序，每個訂單的工序相同，且各個訂單在m臺設備中加工時間已知。每個設備同一時刻只能加工一個訂單，則調度目標為根據條件設置合理的n個訂單的加工順序，從而使某些調度指標達到最優。

根據實際制絲生產單元提取必要屬性進行抽象，從而獲得生產單元模型M和訂單模型N，以表示第 i道工序與 i-1道工序之間存在的緩沖區大小，表示第 i道工序的工藝制造能力；對于訂單而言，s表示訂單所需的不同物料種類數目，表示第 i個訂單的優先級，實際表示生產訂單牌號，高級的牌號優先級高于低級。

①生產單元模型M：

基于訂單和生產單元的模型，設計以物料輸入、倉儲輸出、最大流程時間、有效作業率等屬性組合成的評估模型 E，檢驗訂單調度序列是否能夠更好地滿足排產調度情況，決策者可以根據實際生產需要選擇合適評估屬性。

③評估模型E

物料輸入：In

倉儲庫存：Out

其中，In指的是訂單所需物料輸入：

Out指訂單生產完成后生成的半成品所需的倉儲空間：

對于有效作業率ξ，其計算公式為：

2.2 算法設計

對于制絲過程煙片預處理生產單元的模型抽象如 x.x所述，求解該模型即是找到一個合理的訂單加工序列 π={π(1),π(2),π(3),…,π(n)}，使得訂單總生產時間最小化，節約生產成本，因此目標函數為：

流水線調度問題的核心在于如何更快更方便地找到那個相對最優解，目前并不存在一個絕對有效的算法，能夠在多項式時間內求出這個最優解，經過多年研究，業界對于這類調度問題已經具有一定研究經驗，現在的研究可分為精確方法以及近似方法兩類。

精確方法包括線性規劃[9]、分支定界方法[10]等，其目的為保證得到全局最優解，其限制在于只能用于解決較小規模的流水線調度問題，求解過程耗時較長，效率低，但能夠保證解的準確性。

而近似方法是相對于精確方法無法求解的情況下，尋找相對最優解的算法，隨著流水線調度問題日趨復雜，精確方法求解效率低下的情況下，近似方法能夠在較少的耗時中求解能夠接受的近似解，求解時間短，效率較高，如何提高近似解的準確性和求解效率是目前的重要研究方向。近似方法主要包含構造方法、局部搜索、人工智能、系統仿真[11]四類。目前較常見的為人工智能算法，針對緩沖區是否有限的問題，文獻[12-15]提出了混合蝙蝠算法、微粒群算法求解流水線調度問題求解緩沖區有限的情況，文獻[16]考慮了緩沖區為0，即阻塞流水車間的調度問題。

針對煙片預處理段的實際情況，我選擇以模擬退火算法[17]優化的遺傳算法[18]求解。遺傳算法是一種基于自然選擇與遺傳機制的元啟發式搜索算法，將問題求解的過程轉換為解空間的“染色體”迭代的過程，如圖2所示。具體實現步驟如下：

（1）參數編碼：使用無符號二進制整數對訂單任務進行編碼，設置種群大小S，迭代次數En。

（2）初始群體：由于生產實際情況可知，換牌頻繁則會影響生產效率，初始群體必然存在一定約束，因此選擇生產量最大牌號作為初始群體之一。

（3）適應度函數：在此可將目標函數（最大完工時間）作為適應度函數的參數：

（4）遺傳算子計算

選擇：首先通過輪盤賭選擇方法執行遺傳算法的初步選擇，然后將當前群體中適應度最高的個體完整地復制到下一代群體中。

交叉：設置交叉概率 θ ∈ [ 0,1]，根據交叉概率隨機選擇成對染色體按照單點交叉方式兩兩交叉。

變異：設置變異概率 η ∈ [ 0,1]，以基本位變異的方法按照變異概率隨機選取變異染色體進行計算，形成新的一代種群。

（5）模擬退火優化：針對遺傳算法編碼占用儲存空間大、容易陷入局部最優解、爬山能力差等問題，利用模擬退火算法進行優化，計算變異前后兩個種群的總適應度大小 Efit1、 Efit2，若 Efit1< Efit2，則接受變異結果，確定變異后的種群為新一代種群；若 Efit1> Efit2，則考慮以概率p(dE)接受變異結果，且概率隨時間而降低，概率計算方法如下：

圖2 模擬退火算法優化的遺傳算法求解流程Fig.2 The process of simulated annealing algorithm of genetic algorithm optimization

3 算例驗證

為驗證提出的調度模型能夠通過模擬退火算法改進的遺傳算法求出最優解，選取紅河卷煙廠實際生產流程中葉片預處理段生產單元作為設計參考，算法運行環境為Windows 10, intel i7處理器，內存16G，python 2.7。

葉片預處理生產單元模型可描述為下圖所示，它包括7個工序，其中松散回潮到煙片預備階段中存在一個緩沖區，映射到實際上為一個固定容量的儲柜，用于葉配工作，在此假設緩沖區僅能夠存儲同一批訂單的物料。

假設某日制絲訂單預處理段生產情況如下表所示，生產ABCD四種牌號的煙，一共10個訂單，各個訂單所需原煙質量如表中所示。

表1 實際訂單批次信息Tab.1 Actual order batch information

表2 不同規模訂單算法執行結果Tab.2 Results of algorithm in different size of orders

對于訂單中的數據，設置遺傳算法的初始種群規模為 100，交叉概率為 0.95，變異概率為 0.05，迭代代數為100，退火模擬算法的參數k為1，計算的迭代曲線如圖3所示，計算獲得結果見表2第一行，再與正常執行的調度順序相比，其總生產時間共減少了75分鐘，可以證明調度算法的優越性。

圖3 迭代曲線Fig.3 Iterative curve

考慮到訂單批次增長的情況，再以20、30、40、50、60為規模，模擬調度情況，獲得表2中數據，可以發現，該算法能夠適應訂單規模的增長情況，輔助調度員獲得最優訂單調度方案。

4 結論

本文針對紅河煙廠的實際生產情況進行研究，對煙草制絲生產流程中的關鍵生產單元——煙片預處理生產單元的調度排產進行研究，將其抽象成為求解流程型有限緩沖區的流水線調度問題，通過模擬退火算法優化的遺傳算法求解最優解，最后通過模擬不同規模的訂單調度過程，驗證了經過調度后的結果更優，驗證了模型的實用性。未來的研究方向在于將該抽象模型應用到不同的生產單元中，對訂單調度過程進行抽象和優化。