基于遺傳算法的兩階段多目標(biāo)卷包生產(chǎn)調(diào)度優(yōu)化

王勁松，張 敏，楊 明，萬(wàn)年彬，羅 冬，皮俊濤，楊丁鳳

（1.襄陽(yáng)卷煙廠，湖北 襄陽(yáng) 441000；2.華中科技大學(xué) 管理學(xué)院，湖北 武漢 430074）

0 引言

中國(guó)是世界上最大的卷煙生產(chǎn)國(guó)與消費(fèi)國(guó)，卷煙消費(fèi)量占世界煙草消費(fèi)總量的約30%，同時(shí)煙草是國(guó)家和地方財(cái)稅的重要來(lái)源。市場(chǎng)競(jìng)爭(zhēng)日益激烈，生產(chǎn)計(jì)劃管理受市場(chǎng)影響越來(lái)越大，多品種小批量的需求逐漸增多，而卷包排產(chǎn)與上游制絲計(jì)劃、濾棒生產(chǎn)計(jì)劃、下游封裝計(jì)劃相互影響，相互制約，煙廠生產(chǎn)排產(chǎn)的復(fù)雜性大大增加，卷包自動(dòng)排產(chǎn)及卷包優(yōu)化排產(chǎn)得到越來(lái)越多煙廠的關(guān)注，如何按訂單組織生產(chǎn)成為煙廠當(dāng)下的迫切需求[1-3]。

卷煙生產(chǎn)計(jì)劃的分層優(yōu)化框架將冗長(zhǎng)復(fù)雜的生產(chǎn)過(guò)程分塊，為生產(chǎn)排程優(yōu)化提供了清晰的思路與范圍。王軍，等[4]將卷煙生產(chǎn)過(guò)程分為上層總生產(chǎn)計(jì)劃層、中間卷包分組計(jì)劃層、下層制絲批次計(jì)劃層。嚴(yán)蕾[5]研究分析了某卷煙廠卷包車(chē)間的交接班工作。王勁松，等[6]考慮卷煙生產(chǎn)的全過(guò)程，設(shè)計(jì)了包括卷包車(chē)間自動(dòng)排產(chǎn)、制絲車(chē)間自動(dòng)排產(chǎn)、濾棒生產(chǎn)計(jì)劃優(yōu)化、輔料組盤(pán)計(jì)劃優(yōu)化、原料香糖料配送計(jì)劃優(yōu)化共六個(gè)功能模塊。

生產(chǎn)排程問(wèn)題屬于NP-hard問(wèn)題，很難尋求到問(wèn)題的最優(yōu)解[7]。陳莊，等[8-9]分析了卷煙生產(chǎn)線的工藝流程，提出了有關(guān)的合理假設(shè)，構(gòu)建了卷煙生產(chǎn)線優(yōu)化調(diào)度模型；謝五峰，等[10]基于SIMATICIT（西門(mén)子平臺(tái)）的軟件架構(gòu)和規(guī)則算法建立了卷包排產(chǎn)子系統(tǒng)；郝雨[11]用層次化建模方法分別構(gòu)建了卷包和制絲的調(diào)度模型。王愛(ài)民，等[12]、丁雷，等[13]以資源動(dòng)態(tài)組合為核心對(duì)卷包作業(yè)動(dòng)態(tài)調(diào)度技術(shù)進(jìn)行了研究。姚麗麗，等[14]分析了排產(chǎn)中工藝路徑的規(guī)則，提出了嵌入規(guī)則的遺傳算法。金靜文[15]設(shè)計(jì)了一種基于首批作業(yè)計(jì)劃的二重啟發(fā)式算法，對(duì)卷包車(chē)間柔性資源動(dòng)態(tài)組合生產(chǎn)進(jìn)行了研究；王偉玲，等[16]建立了多目標(biāo)混合整數(shù)規(guī)劃模型，采用NSGA-II 算法對(duì)多目標(biāo)進(jìn)行求解。李丹，等[17]采用遺傳算法對(duì)卷煙換牌排產(chǎn)進(jìn)行了優(yōu)化設(shè)計(jì)。劉西堯，等[18]提出按喂絲機(jī)排產(chǎn)的多種群混合遺傳算法。周秋艷，等[19]提出了一種以“等待時(shí)間最短”為主的生產(chǎn)排程智能優(yōu)化算法。陳應(yīng)飛，等[20]應(yīng)用了嵌入粒子群算法和模擬退火遺傳算法。

目前，國(guó)內(nèi)關(guān)于卷包生產(chǎn)調(diào)度的研究多是固定的鏈路連接關(guān)系，即卷接機(jī)與喂絲機(jī)的連接是排產(chǎn)前人工確定的，且排產(chǎn)過(guò)程中不可更換，導(dǎo)致排產(chǎn)結(jié)果很難滿足實(shí)際生產(chǎn)；或是先選中一種鏈路關(guān)系，再判斷時(shí)間段內(nèi)是否可用，不可用再更換下一種鏈路關(guān)系，這種算法不夠靈活，因?yàn)殒溌愤x擇規(guī)則多、難度大，且排產(chǎn)容易出現(xiàn)卷接機(jī)等待喂絲機(jī)（或封裝機(jī)）的情況，導(dǎo)致卷接機(jī)在本該工作的時(shí)間段待機(jī)，訂單不能按時(shí)交付。因此，現(xiàn)有的卷包生產(chǎn)調(diào)度優(yōu)化算法很難在實(shí)踐中直接應(yīng)用。

本文結(jié)合襄陽(yáng)卷煙廠的實(shí)際生產(chǎn)情況，首先安排卷接機(jī)的生產(chǎn)訂單，保證卷接機(jī)在正常工作時(shí)間內(nèi)不停機(jī)，再根據(jù)柔性連接關(guān)系確定卷接機(jī)與上游喂絲機(jī)、發(fā)射機(jī)，下游封裝機(jī)每時(shí)段內(nèi)的連接路徑，逐步實(shí)現(xiàn)面向計(jì)劃和實(shí)際生產(chǎn)的卷包生產(chǎn)優(yōu)化調(diào)度。

1 問(wèn)題描述

卷煙卷包生產(chǎn)具體生產(chǎn)線工藝流程如圖1所示。卷接機(jī)接收到喂絲機(jī)或人工供應(yīng)的煙絲和發(fā)射機(jī)發(fā)射的濾棒后進(jìn)行卷接，卷接結(jié)束由包裝機(jī)包裝成條盒后進(jìn)入封裝機(jī)封裝成箱，最后入庫(kù)。

煙廠收到中煙下達(dá)的生產(chǎn)調(diào)度令，生產(chǎn)調(diào)度人員將調(diào)度令分解成訂單（大牌號(hào)拆分為多個(gè)小訂單），綜合卷包車(chē)間的設(shè)備、工作日歷、庫(kù)存等信息編制卷包生產(chǎn)計(jì)劃。此過(guò)程可抽象描述為：

假設(shè)某煙廠可生產(chǎn)G個(gè)規(guī)格共B個(gè)牌號(hào)的卷煙，擁有m臺(tái)卷接機(jī)，w臺(tái)喂絲機(jī)，f臺(tái)濾棒發(fā)射機(jī)，z臺(tái)封裝機(jī)，其中牌號(hào)與卷接機(jī)、喂絲機(jī)與卷接機(jī)、發(fā)射機(jī)與卷接機(jī)、卷接機(jī)與封裝機(jī)之間的柔性連接關(guān)系已知，每個(gè)規(guī)格下的卷煙所用卷接機(jī)、封裝機(jī)相互獨(dú)立，卷接機(jī)j對(duì)牌號(hào)b的卷接速率為vjb，卷接機(jī)從牌號(hào)a換牌

圖1 卷包工藝流程圖

圖2 卷包計(jì)劃甘特圖

某月煙廠收到P個(gè)訂單，訂單信息包括對(duì)應(yīng)的牌號(hào)、生產(chǎn)數(shù)量、交貨期、最早開(kāi)始時(shí)間，當(dāng)月卷接機(jī)的工作日歷已知，訂單優(yōu)先級(jí)已知。調(diào)度人員需要決策每臺(tái)卷接機(jī)每天應(yīng)生產(chǎn)的訂單、訂單的生產(chǎn)順序與數(shù)量以及卷接機(jī)所連接的喂絲機(jī)、濾棒發(fā)射機(jī)、封裝機(jī)，其中鏈路關(guān)系在生產(chǎn)過(guò)程中可能會(huì)發(fā)生改變，使得生產(chǎn)計(jì)劃既滿足卷接設(shè)備不停機(jī)、齊開(kāi)齊停等約束，也能達(dá)到設(shè)定的目標(biāo)（逾期訂單最少、換牌次數(shù)最少等）。最終得到如圖2所示的卷包生產(chǎn)計(jì)劃，其中a圖為卷接機(jī)的生產(chǎn)計(jì)劃，主要包括機(jī)組與訂單的對(duì)應(yīng)關(guān)系，生產(chǎn)順序與生產(chǎn)起止時(shí)間，不同機(jī)組上的同一個(gè)訂單同時(shí)生產(chǎn)同時(shí)停止；b圖為喂絲機(jī)安排計(jì)劃，主要顯示生產(chǎn)過(guò)程中的喂絲機(jī)連接情況，不同的機(jī)組生產(chǎn)同一個(gè)訂單，但在不同時(shí)間段使用的喂絲機(jī)可能不同（濾棒發(fā)射機(jī)、封裝機(jī)圖類(lèi)似）。

2 優(yōu)化建模

2.1 卷包生產(chǎn)調(diào)度的假設(shè)及原則

結(jié)合煙廠的調(diào)研結(jié)果，卷包作業(yè)排產(chǎn)過(guò)程中需要遵循以下假設(shè)與原則：（1）假設(shè)原輔料供應(yīng)能力為無(wú)窮大。（2）假設(shè)所有卷接機(jī)能按照既定的工作日歷正常工作。假設(shè)保證了每一個(gè)訂單一定能在其最早開(kāi)始時(shí)間開(kāi)始生產(chǎn)，且生產(chǎn)設(shè)備在工作日歷的可用時(shí)間段內(nèi)是連續(xù)生產(chǎn)的。出現(xiàn)違反假設(shè)的情況，則需要對(duì)卷包調(diào)度計(jì)劃進(jìn)行重調(diào)度。（3）訂單連續(xù)生產(chǎn)原則：一般情況下，訂單的生產(chǎn)不能中斷，同一訂單必須連續(xù)生產(chǎn)。（4）訂單優(yōu)先級(jí)生產(chǎn)原則：訂單優(yōu)先級(jí)是由人工根據(jù)重要程度對(duì)訂單進(jìn)行的排序，排產(chǎn)中按照訂單優(yōu)先級(jí)逐一安排各訂單的生產(chǎn)。（5）機(jī)臺(tái)齊停原則：執(zhí)行同一訂單的多臺(tái)卷接機(jī)需要滿足齊停規(guī)則，以便于卷包車(chē)間同時(shí)換牌，減少生產(chǎn)混亂，也有利于喂絲機(jī)同時(shí)向?qū)?yīng)卷接機(jī)供應(yīng)煙絲，便于制絲車(chē)間按照煙絲批次下達(dá)制絲作業(yè)計(jì)劃。（6）機(jī)臺(tái)優(yōu)選組合原則：根據(jù)煙草企業(yè)手工排產(chǎn)經(jīng)驗(yàn)總結(jié)，提前設(shè)置機(jī)臺(tái)資源的優(yōu)選組合配置，比如：固定某些機(jī)臺(tái)用于生產(chǎn)某一牌號(hào)，某些牌號(hào)優(yōu)先選擇某喂絲機(jī)供絲。（7）考慮瓶頸資源能力原則：在排產(chǎn)中，主要考慮瓶頸資源卷接機(jī)組的生產(chǎn)能力約束，針對(duì)瓶頸資源建立模型進(jìn)行求解，先得出卷接機(jī)組上的生產(chǎn)作業(yè)計(jì)劃，再根據(jù)設(shè)備鏈路關(guān)系，得出工藝路徑上非瓶頸資源的生產(chǎn)作業(yè)計(jì)劃。

2.2 卷包生產(chǎn)調(diào)度的約束

卷包生產(chǎn)調(diào)度的瓶頸資源為卷接機(jī)，本文以卷接機(jī)為核心建立模型。卷包生產(chǎn)調(diào)度需滿足多方面的約束：（1）訂單交貨期約束。（2）訂單最早開(kāi)始時(shí)間約束。訂單的原輔料需要備貨時(shí)間，訂單只有在原輔料到位后才能開(kāi)始生產(chǎn)。（3）訂單生產(chǎn)數(shù)量約束。當(dāng)月訂單的生產(chǎn)數(shù)量總和應(yīng)不小于訂單需求量。（4）設(shè)備產(chǎn)能約束。卷包調(diào)度的結(jié)果顯示以“天”為粒度，每天的產(chǎn)量不能大于設(shè)備的最大產(chǎn)能。（5）柔性連接關(guān)系約束。牌號(hào)與卷接機(jī)、喂絲機(jī)與卷接機(jī)之間是多對(duì)多的柔性連接關(guān)系，但在某個(gè)時(shí)刻只能選擇一個(gè)牌號(hào)生產(chǎn)，一臺(tái)喂絲機(jī)供絲。（6）換牌時(shí)間約束。卷接機(jī)上會(huì)安排多個(gè)生產(chǎn)訂單，訂單按序生產(chǎn)，前一個(gè)訂單到下一個(gè)訂單需要切換時(shí)間，切換時(shí)間不能小于換牌時(shí)間。（7）工作日歷約束。每臺(tái)卷接機(jī)的日保養(yǎng)時(shí)間、接班保養(yǎng)時(shí)間、輪保時(shí)間、放假時(shí)間等不同，導(dǎo)致每臺(tái)卷接機(jī)的可用時(shí)間不同，排產(chǎn)中必須考慮這些時(shí)間，排產(chǎn)結(jié)果才能與實(shí)際相符。

2.3 卷包生產(chǎn)調(diào)度的目標(biāo)

卷包生產(chǎn)是一個(gè)多部門(mén)協(xié)同的生產(chǎn)過(guò)程，需要滿足多個(gè)目標(biāo)。本文主要考慮以下目標(biāo)：逾期訂單數(shù)量最少，最大完工時(shí)間最小，換牌次數(shù)最少，人工喂絲最少，卷接機(jī)完工時(shí)間方差最小。目標(biāo)的重要性依次降低，即逾期訂單數(shù)量最少的計(jì)劃可能不止一個(gè)，在這些計(jì)劃中，進(jìn)一步找到最大完工時(shí)間最小的計(jì)劃，再找到換牌次數(shù)最小的訂單，依次優(yōu)化目標(biāo)。其中逾期訂單數(shù)量最少是一級(jí)目標(biāo)，用式（1）表示，若訂單結(jié)束時(shí)間Ei大于訂單交貨期Di，則標(biāo)記此訂單逾期。最大完工時(shí)間最小為二級(jí)目標(biāo)，用式（2）表示。其余目標(biāo)為再次一級(jí)目標(biāo)，用式（3）-式（5）表示，其中Cj表示卷接機(jī)j上的換牌次數(shù)，W表示人工喂絲的煙支數(shù)量，σ表示卷接機(jī)完工時(shí)間的方差。通過(guò)權(quán)重來(lái)區(qū)分目標(biāo)的重要程度，用式（6）表示，在此式的基礎(chǔ)上進(jìn)行輪盤(pán)賭選擇計(jì)算。本文中權(quán)重依次為0.40，0.30，0.15，0.10，0.05。

3 算法設(shè)計(jì)

本文提出一種兩階段遺傳算法，其基本思路是：（1）僅考慮牌號(hào)與卷接機(jī)的柔性關(guān)系，確定每臺(tái)卷接機(jī)上生產(chǎn)的牌號(hào)，從而確定其生產(chǎn)的訂單，再根據(jù)訂單優(yōu)先生產(chǎn)順序，形成卷接機(jī)生產(chǎn)計(jì)劃；（2）對(duì)于階段一的生產(chǎn)計(jì)劃，得到每一臺(tái)卷接機(jī)的生產(chǎn)時(shí)間線，再結(jié)合卷接機(jī)與喂絲機(jī)、封裝機(jī)、發(fā)射機(jī)的柔性關(guān)系及優(yōu)化規(guī)則確定每個(gè)時(shí)刻的鏈路關(guān)系。

這種兩階段遺傳算法將卷接計(jì)劃與鏈路關(guān)系計(jì)劃分開(kāi)，充分考慮了柔性連接關(guān)系，保證了卷接機(jī)連續(xù)生產(chǎn)，得到的結(jié)果更符合實(shí)際生產(chǎn)情況。

3.1 機(jī)臺(tái)分組

將鏈路關(guān)系完全相同、可生產(chǎn)牌號(hào)完全相同的卷接機(jī)分為一個(gè)機(jī)組。同一時(shí)間一臺(tái)喂絲機(jī)只能供應(yīng)一種煙絲，所以與同一喂絲機(jī)相連的卷接機(jī)最好生產(chǎn)同樣的牌號(hào)，否則同一時(shí)間生產(chǎn)牌號(hào)過(guò)多，容易出現(xiàn)增加人工上絲、部分煙絲過(guò)期、部分卷接機(jī)等待喂絲機(jī)、換牌人員調(diào)度混亂等問(wèn)題。每個(gè)機(jī)組內(nèi)卷接機(jī)安排的訂單以及訂單生產(chǎn)順序相同，但因工作日歷的差別可能會(huì)導(dǎo)致每臺(tái)卷接機(jī)具體生產(chǎn)數(shù)量不同。

3.2 第一階段編碼

一個(gè)有效的染色體的一個(gè)基因位表示一個(gè)機(jī)組上生產(chǎn)的訂單編號(hào)。以6個(gè)機(jī)組、7個(gè)訂單為例，如圖3所示。

圖3 第一階段染色體編碼方式

一個(gè)染色體有6個(gè)基因位（機(jī)組個(gè)數(shù)），表示機(jī)組1生產(chǎn)訂單6,7，機(jī)組2生產(chǎn)訂單5,6,7，機(jī)組3生產(chǎn)訂單5,6,7，機(jī)組4生產(chǎn)訂單3,4,7，機(jī)組5生產(chǎn)訂單2，機(jī)組6生產(chǎn)訂單1,2。一條染色體必須包含所有訂單{1,2,3,4,5,6,7}。

3.3 齊停算法

齊停算法主要用于第一階段的染色體解碼過(guò)程中。一個(gè)訂單由多臺(tái)卷接機(jī)進(jìn)行生產(chǎn)時(shí)，要求這些卷接機(jī)同時(shí)釋放，但由于訂單與機(jī)組的組合不同，卷接機(jī)的工作日歷不同，造成生產(chǎn)同一訂單的卷接機(jī)不能同時(shí)釋放。采用對(duì)工作日歷的可用時(shí)間段逐一推進(jìn)的方法，計(jì)算出具體的齊停時(shí)間點(diǎn)，具體操作如下：

Step1:找到生產(chǎn)此訂單的所有卷接機(jī)，羅列出這些卷接機(jī)的所有可用時(shí)間段，并按照時(shí)間段從小到大排列，建立可用時(shí)間集R={(time1,1,time1,2),(time2,1,time2,2),…,(timen,1,timen,2)} 。 (time1,1,time1,2) 表示第一個(gè)可用時(shí)間段的起止時(shí)間點(diǎn)，在時(shí)間段time1,1～time1,2內(nèi)，卷接機(jī)正常工作，而在時(shí)間段time1,2～time2,1內(nèi)，卷接機(jī)停機(jī)。

Step2:初始化i=1,計(jì)算時(shí)間段（timei,1,timei,2)的產(chǎn)量，再計(jì)算出訂單累計(jì)產(chǎn)量，與需求量比較，若累計(jì)產(chǎn)量高于訂單需求量，則進(jìn)入步驟3，否則表示訂單不能在此時(shí)間段內(nèi)結(jié)束生產(chǎn)，將時(shí)間段往下推一個(gè)，令i=i+1。

Step3:訂單能在時(shí)間段（timei,1,timei,2)內(nèi)結(jié)束生產(chǎn)，因此需要計(jì)算出具體齊停的時(shí)間點(diǎn)，令st=timei,1,通過(guò)公式計(jì)算訂單b的具體結(jié)束時(shí)間點(diǎn)，其中rest_m表示訂單在st時(shí)刻的剩余產(chǎn)量。

3.4 第二階段編碼

由第一階段的編碼及齊停算法，得到了卷接機(jī)的生產(chǎn)計(jì)劃，以6個(gè)卷接機(jī)機(jī)組，7個(gè)訂單為例，結(jié)果如圖2(a)所示。整個(gè)時(shí)間線被切割成5個(gè)小時(shí)間段，每個(gè)時(shí)間段內(nèi)的鏈路關(guān)系互相獨(dú)立。在時(shí)間段1中的鏈路關(guān)系生產(chǎn)結(jié)束后釋放，在時(shí)間段2重新組合，時(shí)間段2結(jié)束后再釋放，時(shí)間段3重新組合，以此類(lèi)推。這一階段編碼共有5個(gè)基因位，即一列表示一個(gè)基因位，每個(gè)基因位表示所有卷接機(jī)組在時(shí)間段內(nèi)對(duì)應(yīng)連接的喂絲機(jī)，如圖2(b)所示。

第二階段的編碼優(yōu)化：圖2(b)中每一列表示某時(shí)間段內(nèi)已安排的鏈路關(guān)系，鏈路關(guān)系優(yōu)化的一個(gè)重要指標(biāo)為切換次數(shù)最少，所以在生成下一列鏈路時(shí)，先判斷之前的鏈路是否依舊可用，若可用則直接沿用上一列的鏈路，若不可用則重新生成。

3.5 算法流程

3.5.1 種群初始化。種群規(guī)模為pu，初始種群由兩部分構(gòu)成：一部分根據(jù)機(jī)臺(tái)優(yōu)選組合原則產(chǎn)生，即總結(jié)手工排產(chǎn)經(jīng)驗(yàn)，將認(rèn)為可能不錯(cuò)的組合作為部分輸入；另一部分則根據(jù)卷接機(jī)與牌號(hào)的柔性連接關(guān)系隨機(jī)組合生成。

3.5.2 嵌入第二階段遺傳算法。對(duì)種群中的每一個(gè)個(gè)體，安排每一個(gè)時(shí)間段的喂絲機(jī)、封裝機(jī)、發(fā)射機(jī)。將鏈路關(guān)系獨(dú)立安排，使得處理難度降低。安排鏈路關(guān)系需滿足的約束有：（1）設(shè)備之間的柔性連接關(guān)系。（2）某時(shí)刻卷接機(jī)只能與一臺(tái)喂絲機(jī)相連、一臺(tái)發(fā)射機(jī)相連、一臺(tái)封裝機(jī)相連。（3）喂絲機(jī)連接數(shù)量上限約束。某時(shí)刻一臺(tái)喂絲機(jī)最多能同時(shí)給有限數(shù)量的卷接機(jī)供絲，發(fā)射機(jī)與封裝機(jī)同理。優(yōu)化目標(biāo)：（1）人工喂絲最少；（2）半自動(dòng)喂絲最少；（3）切換次數(shù)最少。3.5.3 選擇（多目標(biāo)的處理）。采用最優(yōu)個(gè)體和輪盤(pán)賭混合的方式進(jìn)行選擇。本文考慮了5個(gè)目標(biāo)：逾期訂單數(shù)量最少，最大完工時(shí)間最小，換牌次數(shù)最少，人工喂絲最少，卷接機(jī)停止時(shí)間方差最小。根據(jù)目標(biāo)值排序，當(dāng)?shù)谝荒繕?biāo)最優(yōu)時(shí)，找第二目標(biāo)最優(yōu)，再找第三目標(biāo)最優(yōu)，以此類(lèi)推。將種群中排前10%的個(gè)體直接復(fù)制到下一代的種群中，這樣很好的保留了上一代的優(yōu)秀個(gè)體，也在一定程度上加快了收斂速度。

剩余90%的個(gè)體采用輪盤(pán)賭的方式進(jìn)行選擇。卷包生產(chǎn)調(diào)度問(wèn)題屬于多目標(biāo)復(fù)雜問(wèn)題，一般可直接根據(jù)權(quán)重計(jì)算出每個(gè)個(gè)體的綜合目標(biāo)值，由于5個(gè)目標(biāo)值之間數(shù)值差距太大，即使極端化設(shè)置權(quán)重，也很難消除數(shù)量級(jí)之間的差距，所以本文先在種群中對(duì)每個(gè)目標(biāo)值進(jìn)行比較，將目標(biāo)值歸一化后再加權(quán)計(jì)算，作為輪盤(pán)賭選擇的基礎(chǔ)，見(jiàn)式（8）。

3.5.4 交叉。采用單點(diǎn)交叉的方式進(jìn)行交叉。交叉過(guò)程如下：

Step1:計(jì)數(shù)器g=0，作為交叉的父本father和母本mother；

Step2:判斷是否進(jìn)行交叉。產(chǎn)生一個(gè)隨機(jī)數(shù)r，如果r ≤Pc（交叉概率），進(jìn)行Step3，否則父本和母本直接進(jìn)入下一代種群中，ch ild1=fa th er, ch ild2=mo th er；

Step3:生成一個(gè)機(jī)組數(shù)量JQ以?xún)?nèi)的整數(shù)隨機(jī)數(shù)rr(1 ≤rr ≤JQ)，將隨機(jī)數(shù)及隨機(jī)數(shù)以后的機(jī)組上生產(chǎn)的訂單進(jìn)行交叉，得到兩個(gè)子代；

Step4:分別判斷ch ild1、ch ild2是否包含本月所要生產(chǎn)的所有訂單，如果包含，則是可行解，寫(xiě)進(jìn)新的種群，g=g+2，否則進(jìn)入Step5；

Step5:子代中不包含所有訂單，找到未包含訂單，對(duì)這些訂單逐一進(jìn)行安排，對(duì)子代進(jìn)行修正，然后寫(xiě)進(jìn)新種群，g=g+2；

Step6:直到新種群中的個(gè)體數(shù)等于種群規(guī)模時(shí)停止，即g=pu。

3.5.5 變異。采用單點(diǎn)變異的方式進(jìn)行變異。變異過(guò)程如下：

Step1：計(jì)數(shù)器g=0，從種群中選擇一個(gè)個(gè)體，作為變異的父本father；

Step2：判斷是否進(jìn)行變異。產(chǎn)生一個(gè)隨機(jī)數(shù)r，如果r ≤Pm（變異概率），進(jìn)入Step3，否則父本不變異，直接進(jìn)入下一代種群中，ch ild1=fa th er；

Step3：生成一個(gè)機(jī)組數(shù)量JQ以?xún)?nèi)的整數(shù)隨機(jī)數(shù)rr(1 ≤rr ≤JQ)，重新選擇隨機(jī)數(shù)對(duì)應(yīng)的機(jī)組上生產(chǎn)的訂單，得到ch ild1；

Step4：判斷是否包含本月所要生產(chǎn)的所有訂單，如果包含，則是可行解，寫(xiě)進(jìn)新的種群，計(jì)數(shù)器g=g+1，否則對(duì)不合格個(gè)體進(jìn)行修正；

Step5：直到種群中的個(gè)體數(shù)都變異完成后停止。

4 數(shù)據(jù)分析

本文采用MATLAB.R2017a編程實(shí)現(xiàn)。階段一遺傳算法參數(shù)設(shè)置如下：種群規(guī)模為100，迭代停止條件為G=200，交叉概率為0.8，變異概率為0.05；階段二的參數(shù)設(shè)置為：種群規(guī)模為40，迭代停止條件為G=100或時(shí)間超過(guò)2s，交叉概率為0.8，變異概率為0.02。

以襄陽(yáng)卷煙廠某月真實(shí)的訂單情況及設(shè)備數(shù)據(jù)進(jìn)行模擬，設(shè)備的柔性連接關(guān)系見(jiàn)表1，卷接機(jī)都可連現(xiàn)有的5臺(tái)濾棒發(fā)射機(jī)。輸入的訂單見(jiàn)表2，共有3個(gè)規(guī)格16個(gè)牌號(hào)18個(gè)訂單，07205、07218兩個(gè)牌號(hào)為外購(gòu)煙絲，優(yōu)先使用半自動(dòng)喂絲機(jī)W7供絲；此訂單信息表中僅07229、07237、52213、61204需要使用濾棒發(fā)射機(jī)。15#-23#、12#、14#共11臺(tái)卷接機(jī)采用早班、中班兩班制組織生產(chǎn)，3#-11#卷接機(jī)采用早、中、晚三班制組織生產(chǎn)，16日～20日放假，每班次為8h，為與工作日歷相匹配，設(shè)置一天的開(kāi)始時(shí)間為早上8:00。再結(jié)合煙廠具體的卷包生產(chǎn)速率等具體信息，得到的卷包計(jì)劃見(jiàn)表3，表中顯示了分組信息與明確的鏈路關(guān)系、訂單牌號(hào)信息；生產(chǎn)計(jì)劃甘特圖如圖4所示。

表1 煙廠卷接機(jī)柔性連接關(guān)系表

時(shí)間段（09 5:49,14 23:15）內(nèi)，8-10#卷接機(jī)與3#卷接機(jī)交換喂絲機(jī)，是因?yàn)橛唵?和訂單2為外購(gòu)煙絲，需使用半自動(dòng)喂絲機(jī)W7供絲，訂單1和訂單2生產(chǎn)完畢再切換為原來(lái)的搭配，如圖4中陰影所示；在時(shí)間段（25 14:21,29 15:57）內(nèi)，3#卷接機(jī)從W7 切換為W2喂絲機(jī)供絲，與8～10#卷接機(jī)一起使用W2喂絲機(jī)生產(chǎn)訂單10，減少了半自動(dòng)喂絲機(jī)W7的使用時(shí)間，為后續(xù)可能到來(lái)的加急訂單留出空間。訂單14與訂單15進(jìn)行生產(chǎn)時(shí)，原本可用的喂絲機(jī)、封裝機(jī)、發(fā)射機(jī)皆被訂單13（牌號(hào)61204）占用，已沒(méi)有可用的鏈路，所以這兩個(gè)小訂單皆由人工輔助進(jìn)行生產(chǎn)，見(jiàn)表3。

圖4 卷包車(chē)間生產(chǎn)計(jì)劃甘特圖

表2 煙廠某月生產(chǎn)訂單信息表

表3 卷包作業(yè)生產(chǎn)計(jì)劃結(jié)果表

此排產(chǎn)結(jié)果獲得了煙廠生產(chǎn)調(diào)度科的認(rèn)可。在調(diào)度結(jié)果中，逾期訂單數(shù)為0，在當(dāng)月29 日完成所有生產(chǎn)任務(wù)，較交貨期提前2天；換牌次數(shù)較人工所排計(jì)劃減少；84規(guī)格和90規(guī)格的卷接設(shè)備同時(shí)停機(jī)，封裝機(jī)和發(fā)射機(jī)無(wú)中途切換，卷接機(jī)無(wú)停機(jī)情況。

利用上述實(shí)際數(shù)據(jù)進(jìn)行算法測(cè)試的結(jié)果表明：（1）保證了各個(gè)牌號(hào)的產(chǎn)品能夠按期交貨；（2）符合牌號(hào)—卷接機(jī)、喂絲機(jī)—卷接機(jī)的鏈路關(guān)系；（3）滿足設(shè)備連續(xù)生產(chǎn)，按照工作日歷時(shí)間正常工作，不待料停機(jī)；（4）滿足生產(chǎn)同一訂單的卷接設(shè)備同時(shí)停機(jī)；（5）滿足同規(guī)格的卷接設(shè)備同時(shí)停機(jī)；（6）滿足換牌次數(shù)最?。唬?）對(duì)鏈路關(guān)系進(jìn)行優(yōu)化。此外，進(jìn)一步利用多個(gè)月的實(shí)際數(shù)據(jù)進(jìn)行測(cè)試，也驗(yàn)證了本文所設(shè)計(jì)算法的有效性。

5 結(jié)語(yǔ)

卷包計(jì)劃是煙廠展開(kāi)有序、協(xié)調(diào)、高效生產(chǎn)工作的核心。本文對(duì)卷包生產(chǎn)進(jìn)行了調(diào)研，分析了卷包排產(chǎn)需要滿足的原則與約束，構(gòu)建了以卷接機(jī)為核心的多目標(biāo)優(yōu)化模型，針對(duì)多種柔性連接關(guān)系，提出了兩階段遺傳算法，將卷接機(jī)生產(chǎn)計(jì)劃和鏈路關(guān)系優(yōu)化分開(kāi)，對(duì)逾期訂單數(shù)、最大完成時(shí)間、換牌次數(shù)、人工喂絲進(jìn)行了優(yōu)化。本文的算法已成功用于卷煙生產(chǎn)企業(yè)，調(diào)度結(jié)果獲得了煙廠調(diào)度人員的認(rèn)可，取得了良好的應(yīng)用效果。