柴劍彬, 劉 赫, 貝曉強(qiáng)

(1.北京大學(xué) 光華管理學(xué)院，北京 100871; 2.中國(guó)科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院,北京 100190; 3.中國(guó)科學(xué)院大學(xué)，北京 100049; 4.清華大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100084)

0 引言

在我國(guó)，煙草行業(yè)的年稅收在國(guó)家總稅收中占有很大比重，是國(guó)家利稅主要貢獻(xiàn)者之一。煙草行業(yè)受政策性影響很大，因而國(guó)家對(duì)其實(shí)施統(tǒng)一領(lǐng)導(dǎo)、垂直管理的運(yùn)行體制。但是由于市場(chǎng)經(jīng)濟(jì)的發(fā)展所趨以及國(guó)內(nèi)市場(chǎng)國(guó)際化的迫切需要，行業(yè)之間的競(jìng)爭(zhēng)也日益激烈。對(duì)于卷煙生產(chǎn)企業(yè)來(lái)說，優(yōu)化其生產(chǎn)流程對(duì)提高企業(yè)的生產(chǎn)效率和產(chǎn)能利用率，提高卷煙質(zhì)量，降低生產(chǎn)成本，提高企業(yè)經(jīng)濟(jì)效益具有十分重要的意義。但目前國(guó)內(nèi)很多大中型卷煙企業(yè)在編制有關(guān)生產(chǎn)計(jì)劃時(shí)依然在依靠經(jīng)驗(yàn)進(jìn)行排產(chǎn)，難以保證決策的及時(shí)性和準(zhǔn)確性；即使是已有的排產(chǎn)軟件，也多是利用一些簡(jiǎn)單的排產(chǎn)算法，很難有效解決排產(chǎn)問題普遍存在的復(fù)雜性問題，因此有必要對(duì)卷煙企業(yè)的生產(chǎn)計(jì)劃問題進(jìn)行深入研究。本文的研究正是來(lái)源于國(guó)內(nèi)某卷煙企業(yè)所遇到的生產(chǎn)計(jì)劃和調(diào)度集成問題。

卷煙從包裝環(huán)節(jié)到封箱環(huán)節(jié)的生產(chǎn)過程中普遍遇到的一類排產(chǎn)問題是生產(chǎn)計(jì)劃與調(diào)度集成問題。由于包裝至封箱環(huán)節(jié)的生產(chǎn)過程將直接決定庫(kù)存成品是否能夠滿足市場(chǎng)需求，因此這一段生產(chǎn)過程是卷煙企業(yè)整個(gè)排產(chǎn)計(jì)劃的核心。針對(duì)生產(chǎn)計(jì)劃與調(diào)度集成問題的排產(chǎn)過程是一個(gè)復(fù)雜的決策過程，其復(fù)雜性主要表現(xiàn)為對(duì)象復(fù)雜性、任務(wù)復(fù)雜性、目標(biāo)多樣性和關(guān)聯(lián)復(fù)雜性[1]。生產(chǎn)批量計(jì)劃問題主要研究生產(chǎn)企業(yè)同一時(shí)間不同任務(wù)之間及同一任務(wù)不同時(shí)間的組合計(jì)劃，按照生產(chǎn)能力劃分, 包括有能力約束和無(wú)能力約束批量問題[2,3]。目前，批量計(jì)劃問題中研究最為廣泛的問題是能力約束批量計(jì)劃問題(CLSP，the capacitated lot sizing problem)，即研究在滿足生產(chǎn)能力約束和生產(chǎn)單元容量限制的情況下使許多相似或相同的加工任務(wù)件組合在同一加工單元中，從而降低調(diào)整費(fèi)用，降低成本，提高總體經(jīng)濟(jì)效益。Karimi等[2]對(duì)批量計(jì)劃問題研究進(jìn)展及算法應(yīng)用進(jìn)行了綜述，Bitran等[4]證明了一類批量計(jì)劃問題的NP-hard性。作業(yè)排序問題(Scheduling Problem)也稱為作業(yè)調(diào)度問題，按照工件在機(jī)器上的流動(dòng)形式，一般分為：?jiǎn)螜C(jī)車間(Single machine)、同型并行機(jī)車間(Identical Machine in Parallel)、作業(yè)車間(Job Shop)、流水車間(Flow Shop)、開放車間(Open Shop)等幾種形式[5]。作業(yè)排序問題作為生產(chǎn)作業(yè)計(jì)劃的主要研究問題，目前已經(jīng)得到廣泛研究[6～12]。柔性流水車間作業(yè)排序問題(Flexible Flow Shop Scheduling Problem，F(xiàn)FSP)是生產(chǎn)作業(yè)計(jì)劃中廣泛存在的問題，是流水車間問題的一種拓展，廣泛存在于化工制造、鋼鐵鑄造、食品加工、塑料塑造等領(lǐng)域，逐漸成為研究的熱點(diǎn)[13～19]。而對(duì)于生產(chǎn)批量計(jì)劃和作業(yè)排序的集成問題，建立單個(gè)模型來(lái)描述整個(gè)集成化的計(jì)劃問題并考慮所有層次的約束是求解該類問題的有效方法，但主要困難在于模型求解的復(fù)雜度很高[20]?；诖耍F(xiàn)有對(duì)于生產(chǎn)批量計(jì)劃和作業(yè)排序的集成問題的研究，作業(yè)排序?qū)用驷槍?duì)復(fù)雜的Job Shop和Flow Shop問題如柔性流水車間作業(yè)排序問題的研究很少[21]。Meyr[22]研究了能力約束生產(chǎn)批量計(jì)劃問題和雙機(jī)臺(tái)并行作業(yè)排序集成問題，考慮無(wú)缺貨情況下不同種類的需求如何滿足，建立了整數(shù)規(guī)劃模型并結(jié)合局部搜索元策略閾值接受法和模擬退火算法求解；安玉偉等[23]研究了單機(jī)器同步混批裝配線組成的兩階段生產(chǎn)系統(tǒng)的作業(yè)排序問題和能力約束生產(chǎn)批量計(jì)劃問題的集成問題，采用一種基于混合優(yōu)化方法的分支定界法進(jìn)行求解；Ramezanian等[24]研究了多產(chǎn)品多階段能力約束生產(chǎn)批量計(jì)劃問題和流水車間集成問題，采用了兩種基于混合整數(shù)規(guī)劃的滾動(dòng)時(shí)域啟發(fā)式算法求解模型；Wolosewicz等[25]研究了一類用連接圖表示的復(fù)雜作業(yè)調(diào)度問題和能力約束生產(chǎn)批量計(jì)劃問題，并采用拉格朗日松弛法求解。針對(duì)批量計(jì)劃與柔性流水車間作業(yè)排序問題，目前尚無(wú)較為成熟的模型和算法。

就本文研究的問題來(lái)說，目前國(guó)內(nèi)外有關(guān)卷煙生產(chǎn)批量計(jì)劃和調(diào)度集成問題的研究幾乎沒有。已有的研究卷煙生產(chǎn)排程問題的文獻(xiàn)中，Nicholls[26]以最小化生產(chǎn)過程中運(yùn)行的機(jī)器臺(tái)數(shù)為目標(biāo)，考慮了在制品、產(chǎn)品轉(zhuǎn)運(yùn)需求以及和生產(chǎn)序列相關(guān)的機(jī)臺(tái)生產(chǎn)約束降低的影響，建立了規(guī)劃模型并給出一種簡(jiǎn)單的啟發(fā)算法幫助排產(chǎn)決策；Pattloch等[27]以卷煙生產(chǎn)中品牌轉(zhuǎn)換次數(shù)最小作為優(yōu)化目標(biāo)，建立了整數(shù)規(guī)劃模型，證明了該問題的NP-hard性，并針對(duì)單機(jī)臺(tái)和多機(jī)臺(tái)問題分別給出給出一種啟發(fā)式算法；王愛民等[28]針對(duì)煙草卷包排產(chǎn)方案優(yōu)化制定、周訂單滾動(dòng)追加，以及面向訂單執(zhí)行時(shí)間和數(shù)量變化的計(jì)劃與實(shí)際同步調(diào)整等問題，提出了煙草卷包作業(yè)動(dòng)態(tài)調(diào)度技術(shù)，并通過實(shí)例驗(yàn)證了該算法的有效性；徐屹秦等[29]提出了符合卷煙生產(chǎn)特點(diǎn)的生產(chǎn)計(jì)劃與調(diào)度系統(tǒng), 并闡述了生產(chǎn)計(jì)劃與調(diào)度系統(tǒng)的體系結(jié)構(gòu)、功能模塊、系統(tǒng)工作流程，設(shè)計(jì)了基于規(guī)則的調(diào)度算法；金劍等[30]構(gòu)建了卷煙排產(chǎn)分層遞階優(yōu)化流程，分別建立了帶約束限制的卷煙多點(diǎn)生產(chǎn)任務(wù)分配和生產(chǎn)點(diǎn)詳細(xì)排產(chǎn)數(shù)學(xué)模型，并對(duì)兩個(gè)模型分別設(shè)計(jì)了改進(jìn)的遺傳優(yōu)化算法，通過卷煙生產(chǎn)排產(chǎn)實(shí)例，驗(yàn)證了算法的有效性。這些研究都只針對(duì)卷煙的生產(chǎn)計(jì)劃問題或作業(yè)調(diào)度問題，而未將兩者集成考慮，或缺乏對(duì)實(shí)際生產(chǎn)中的能力約束條件的考慮，或基于整體流程優(yōu)化，而較少針對(duì)具體某個(gè)生產(chǎn)單元研究批量計(jì)劃和作業(yè)排序問題，但這恰恰是生產(chǎn)計(jì)劃得以貫徹執(zhí)行的基礎(chǔ)。對(duì)于卷煙排產(chǎn)優(yōu)化的目標(biāo)，除了優(yōu)化生產(chǎn)時(shí)間和品牌轉(zhuǎn)換次數(shù)，還要求生產(chǎn)卷煙的品質(zhì)盡可能高，這在以往的研究中幾乎未被提及。因此研究卷煙企業(yè)的生產(chǎn)批量計(jì)劃和調(diào)度集成問題具有重要的工程意義。

基于上述研究現(xiàn)狀，本文根據(jù)卷煙生產(chǎn)特點(diǎn)，研究了卷煙生產(chǎn)過程中從卷包環(huán)節(jié)至封箱環(huán)節(jié)的能力約束生產(chǎn)批量計(jì)劃和柔性流水車間調(diào)度集成問題。在第1節(jié)中描述了煙草的生產(chǎn)工藝流程；第2節(jié)中建立了卷煙生產(chǎn)整數(shù)規(guī)劃模型；在第3節(jié)采用遺傳算法對(duì)上述整數(shù)規(guī)劃模型進(jìn)行求解；第4節(jié)選取了某卷煙企業(yè)的真實(shí)數(shù)據(jù)，通過實(shí)例說明該模型的應(yīng)用及求解過程，驗(yàn)證了算法的有效性和穩(wěn)定性；在第5節(jié)中對(duì)本文的研究工作進(jìn)行了總結(jié)和展望。

1 問題描述

卷煙生產(chǎn)與一般工業(yè)生產(chǎn)的過程既有聯(lián)系，又有其自身特殊工藝的特點(diǎn)，在對(duì)卷煙排程進(jìn)行優(yōu)化建模之前，應(yīng)對(duì)卷煙生產(chǎn)過程有基本的了解。由于卷煙企業(yè)的實(shí)際生產(chǎn)過程較為復(fù)雜，為研究方便，這里將卷煙生產(chǎn)線抽象為圖1所示。本文主要研究卷煙從包裝環(huán)節(jié)到封箱環(huán)節(jié)的生產(chǎn)過程中遇到的生產(chǎn)計(jì)劃與調(diào)度集成問題。

圖1 卷煙生產(chǎn)流程圖

在生產(chǎn)批量計(jì)劃層面上，將計(jì)劃周期均分為T個(gè)時(shí)段，每個(gè)時(shí)段內(nèi)對(duì)K種品牌的卷煙均有不同但確定的需求量，這些需求是由國(guó)務(wù)院計(jì)劃部門下達(dá)，并根據(jù)上級(jí)煙草部門分配制定的，因此在本文中我們假設(shè)所有卷煙的總需求是確定的。單位時(shí)間內(nèi)包裝機(jī)和封箱機(jī)的生產(chǎn)能力是有限的，因此需要合理安排每種卷煙在各個(gè)時(shí)段的生產(chǎn)量以滿足市場(chǎng)需求。每個(gè)時(shí)段的生產(chǎn)時(shí)間是固定的，生產(chǎn)不允許加班。由于市場(chǎng)需求量大，因此在工作期間機(jī)器都需要滿負(fù)荷生產(chǎn)，且對(duì)于需求量大的產(chǎn)品應(yīng)提前生產(chǎn)，但超過需求部分需要入庫(kù)并支付庫(kù)存費(fèi)用。由于包裝機(jī)和封箱機(jī)的準(zhǔn)備成本(setup cost)很大，因此在生產(chǎn)過程中不允許中途停機(jī)，應(yīng)保證連續(xù)生產(chǎn)直到滿足周期內(nèi)的所有需求。

在作業(yè)層面上，卷煙從包裝機(jī)到封箱機(jī)的加工過程中，不同品牌的卷煙連續(xù)在兩道工序(卷包和封箱)上以相同的順序加工，所有卷煙的工藝路線相同；兩道工序中均存在多臺(tái)并行機(jī)器，卷煙開始加工后在兩道工序之間無(wú)等待直至加工完成。上述問題是一個(gè)典型的柔性流水車間調(diào)度問題(Flexible Flow Shop Scheduling Problem，F(xiàn)FSP)，它是傳統(tǒng)流水車間調(diào)度問題的推廣，即允許在工件加工的過程中有并行機(jī)器。已經(jīng)證明，兩個(gè)階段中只有一個(gè)階段存在并行機(jī)器的FFSP問題屬于NP-hard問題[31]。但是，卷煙生產(chǎn)的調(diào)度問題又具有自己的特點(diǎn)，其中最重要的特點(diǎn)是：1)每種品牌的卷煙在任一工序可由多臺(tái)機(jī)器加工，而具體加工的機(jī)臺(tái)數(shù)目是未知的，這就意味著雖然要加工的卷煙品牌數(shù)目是已知的，但每種品牌在每臺(tái)包裝機(jī)和封箱機(jī)上加工的時(shí)間是不確定的；2)封箱機(jī)的生產(chǎn)能力遠(yuǎn)超過包裝機(jī)，因此包裝機(jī)的加工時(shí)間均嚴(yán)格大于封箱機(jī)加工時(shí)間，包裝機(jī)加工時(shí)間是絕對(duì)瓶頸。另外，卷煙加工過程中受某些因素限制，某些封箱機(jī)只能和指定的包裝機(jī)連接，某些卷煙品牌只能由指定的包裝機(jī)生產(chǎn)，且不同包裝機(jī)生產(chǎn)的卷煙質(zhì)量不同。這些都比傳統(tǒng)的柔性流水車間生產(chǎn)調(diào)度問題更加復(fù)雜。

綜上所述，根據(jù)卷煙企業(yè)生產(chǎn)特點(diǎn)，本文研究的問題具有如下特征：

(1)卷煙企業(yè)面臨的需求在計(jì)劃期內(nèi)是確定的；

(2)所有機(jī)臺(tái)在生產(chǎn)的每個(gè)時(shí)段都以恒定速率滿負(fù)荷生產(chǎn)，不考慮機(jī)器故障，不允許中途停機(jī)；

(3)每臺(tái)包裝機(jī)每個(gè)時(shí)段只能生產(chǎn)一種品牌的卷煙，但一種卷煙品牌可同時(shí)被多臺(tái)包裝機(jī)生產(chǎn)；

(4)各種品牌的卷煙生產(chǎn)優(yōu)先級(jí)相同；

(5)兩種卷煙品牌轉(zhuǎn)換的生產(chǎn)線調(diào)整時(shí)間(setup time)相對(duì)較短，可忽略不計(jì)；

(6)每臺(tái)包裝機(jī)只能生產(chǎn)指定的卷煙品牌，且不同包裝機(jī)生產(chǎn)的卷煙質(zhì)量不同；

(7)每臺(tái)包裝機(jī)只能與指定的封箱機(jī)連接；

(8)同一時(shí)間內(nèi)，一臺(tái)包裝機(jī)只能連接一臺(tái)封箱機(jī)，而一臺(tái)封箱機(jī)可連接多臺(tái)包裝機(jī)；

(9)封箱機(jī)的生產(chǎn)能力遠(yuǎn)超過包裝機(jī)，卷煙開始加工后在兩道工序之間無(wú)等待；

(10)某些卷煙品牌剛進(jìn)入市場(chǎng)不久，對(duì)其需求預(yù)測(cè)不準(zhǔn)，月初即投入生產(chǎn)。

卷煙生產(chǎn)企業(yè)面臨的問題是：應(yīng)如何制定卷煙在包裝機(jī)和封裝機(jī)上的生產(chǎn)計(jì)劃，才能使得企業(yè)在上述生產(chǎn)規(guī)則和能力約束下，滿足市場(chǎng)需求，并優(yōu)化生產(chǎn)流程。

2 數(shù)學(xué)建模

設(shè)卷煙企業(yè)有M臺(tái)包裝機(jī)、N臺(tái)封箱機(jī)負(fù)責(zé)生產(chǎn)K種品牌的卷煙，生產(chǎn)的周期為T。第i臺(tái)包裝機(jī)單位時(shí)間內(nèi)可生產(chǎn)第k種品牌卷煙的產(chǎn)能是qik，第k種品牌在第t個(gè)時(shí)間的需求量為Dkt，庫(kù)存成本為ck。對(duì)于包裝機(jī)和封箱機(jī)的連接，第i臺(tái)包裝機(jī)可連接的封箱機(jī)的集合為Ωi，第j臺(tái)封箱機(jī)可連接的包裝機(jī)的集合為Φj，可連接包裝機(jī)的最大上限為dj。每臺(tái)包裝機(jī)的生產(chǎn)時(shí)間為Ci，生產(chǎn)的最大完工時(shí)間為Cmax。不同包裝機(jī)生產(chǎn)的卷煙質(zhì)量不同，第k種品牌卷煙在第i臺(tái)包裝機(jī)上生產(chǎn)的質(zhì)量系數(shù)為ρik，ρik為0則表示品牌k不能在包裝機(jī)i上生產(chǎn)。有些卷煙品牌由于新進(jìn)入市場(chǎng)，需求難以預(yù)測(cè)，這些品牌集合為Θ。

定義以下決策變量：第k種品牌在第t個(gè)時(shí)段的庫(kù)存數(shù)量Ikt；二元變量Xikt，Zijt，Yjkt，Sit。Xikt=1表示第i臺(tái)包裝機(jī)在第t個(gè)時(shí)段排產(chǎn)第k種品牌的卷煙，否則為0；Yjkt=1表示第j臺(tái)封箱機(jī)在第t個(gè)時(shí)段封裝第k種品牌的卷煙，否則為0；Zijt=1表示在第t個(gè)時(shí)段第j臺(tái)封箱機(jī)與第i臺(tái)包裝機(jī)相連，否則為0；Sit=1表示在第t個(gè)時(shí)段包裝機(jī)i要更換生產(chǎn)的卷煙品牌，否則為0。

對(duì)于卷煙企業(yè)的生產(chǎn)計(jì)劃制定，生產(chǎn)優(yōu)化要達(dá)到的目標(biāo)有四個(gè)：首先是最小化生產(chǎn)時(shí)間，因?yàn)闄C(jī)臺(tái)運(yùn)轉(zhuǎn)的維護(hù)成本極大；其次是最小化同一生產(chǎn)線上更換生產(chǎn)卷煙品牌的次數(shù)，因?yàn)樵跈C(jī)臺(tái)上轉(zhuǎn)換生產(chǎn)不同品牌的卷煙的轉(zhuǎn)換成本也很大，但要小于機(jī)臺(tái)運(yùn)轉(zhuǎn)成本；第三，應(yīng)合理安排包裝機(jī)生產(chǎn)的卷煙品牌以提高卷煙的品質(zhì)；最后，需要盡可能減小卷煙成品的庫(kù)存成本，對(duì)于具有高架倉(cāng)儲(chǔ)的卷煙企業(yè)來(lái)說，這項(xiàng)成本一般小于前三項(xiàng)的重要性。

排產(chǎn)問題中研究多個(gè)目標(biāo)的問題稱為多目標(biāo)排產(chǎn)問題，多目標(biāo)排產(chǎn)問題也是一類多目標(biāo)決策問題，它的關(guān)鍵問題在于由于多個(gè)目標(biāo)之間常常是互相沖突的，一般不存在使多個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)的“絕對(duì)”最優(yōu)解。多目標(biāo)排產(chǎn)問題的求解方法可以分為三類[32]：第一類是尋找約束解或多重解，其中約束解是根據(jù)問題的實(shí)際情況，將目標(biāo)函數(shù)按照重要程度排成次序，之后將次要的目標(biāo)函數(shù)作為約束條件；多重解是在求得前一個(gè)目標(biāo)函數(shù)最優(yōu)解的基礎(chǔ)上求后一個(gè)目標(biāo)函數(shù)的最優(yōu)解，并把最后一個(gè)目標(biāo)函數(shù)的最優(yōu)解作為多目標(biāo)規(guī)劃問題的最優(yōu)解，這樣得到的解稱為多重解；第二類是尋找pareto最優(yōu)解或稱非支配解，即對(duì)于這樣的解，不可能使得在任何目標(biāo)函數(shù)上的改進(jìn)不損害至少一個(gè)其他目標(biāo)函數(shù)；第三類是通過構(gòu)造權(quán)函數(shù)的方法把多目標(biāo)排序轉(zhuǎn)化為單目標(biāo)排序，這種方法得到的多目標(biāo)排序的解稱為權(quán)函數(shù)解。

對(duì)于上述問題，卷煙企業(yè)一般很難獲取具體的運(yùn)營(yíng)成本，僅能簡(jiǎn)單憑借投入的人力物力判斷其相對(duì)大小。因此設(shè)上述四個(gè)目標(biāo)分別為z1，z2，z3，z4，其權(quán)重分別為P1，P2，P3，P4，令P1?P2?P3?P4。采用線性加權(quán)法，將多目標(biāo)排序問題轉(zhuǎn)換為單目標(biāo)問題[33]，利用如下的權(quán)重確定方法，使得優(yōu)先滿足第一目標(biāo)，當(dāng)?shù)谝荒繕?biāo)值相同時(shí)再比較第二目標(biāo)，以此類推。權(quán)重的設(shè)置可采用如下方法:

在每個(gè)目標(biāo)的判據(jù)空間中定義兩個(gè)極限點(diǎn): 最大極限點(diǎn)z+和最小極限點(diǎn)z-：

(1)

(2)

其中M為包裝機(jī)數(shù)量，K為生產(chǎn)品牌總數(shù)量，T為最大生產(chǎn)時(shí)長(zhǎng)，ρik×qik代表第i個(gè)包裝機(jī)單位時(shí)間生產(chǎn)的產(chǎn)品質(zhì)量，ck×Ikt代表第k個(gè)品牌在t時(shí)間的累計(jì)庫(kù)存。最后，我們對(duì)于權(quán)重進(jìn)行歸一化處理，使得各目標(biāo)權(quán)重和為1:

(3)

這樣可以滿足前述的目標(biāo)偏好要求。

綜上所述，建立整數(shù)規(guī)劃模型如下:

minz=ω1z1+ω2z2+ω3z3+ω4z4

(4)

s.t.z1=Cmax

(5)

(6)

(7)

(8)

(9)

Cmax≥Ci,?i

(10)

(11)

Sit≥Xik,t+1-Xikt,?i,j,t

(12)

(13)

(14)

Xikt-Yjkt≤1-Zijt,?i,j,k,t

(15)

Xikt-Yjkt≥Zijt-1,?i,j,k,t

(16)

YN+1,kt=0,?k,t

(17)

(18)

(19)

(20)

Xikt≤ρik,?i,k,t

(21)

Xikt,Yjkt,Zijt,Sit∈{0,1},?i,j,k,t

(22)

Ikt≥0,Cmax≥0,Ci≥0;Ikt,Cmax,Ci為整數(shù),?i,k,t

(23)

其中(4)為模型目標(biāo)函數(shù)，(5)～(8)分別為最小化卷煙日生產(chǎn)時(shí)間、最小化品牌轉(zhuǎn)換次數(shù)、最大化卷煙生產(chǎn)質(zhì)量、最小化庫(kù)存成本的子目標(biāo)；約束(9)表示一臺(tái)包裝機(jī)在單位時(shí)間內(nèi)最多生產(chǎn)一種品牌的卷煙；(10)(11)表示系統(tǒng)的生產(chǎn)時(shí)間由工作時(shí)間最長(zhǎng)的包裝機(jī)決定；約束(12)表示換牌次數(shù)由當(dāng)前時(shí)間和下一時(shí)間機(jī)臺(tái)是否生產(chǎn)品牌的差異決定；約束(13)表示每臺(tái)包裝機(jī)只能且必須連接一臺(tái)封箱機(jī)；約束(14)表示一臺(tái)封箱機(jī)可連接的包裝機(jī)不能超過其上限；約束(15)(16)表示生產(chǎn)的連續(xù)性，即每臺(tái)包裝機(jī)和與其相連的封裝機(jī)生產(chǎn)狀態(tài)必須相同；約束(17)是為了保證生產(chǎn)的連續(xù)性，當(dāng)某些包裝機(jī)不生產(chǎn)時(shí)，與其連接的封箱機(jī)可能還在生產(chǎn)，這可能違反生產(chǎn)連續(xù)性約束(18)(19)，即出現(xiàn)了不生產(chǎn)的包裝機(jī)但沒有不生產(chǎn)的封箱機(jī)與之相連，由于每臺(tái)包裝機(jī)都必須和一臺(tái)封箱機(jī)相連，因此設(shè)置一個(gè)虛擬的不生產(chǎn)封箱機(jī)，讓它連接不生產(chǎn)的包裝機(jī)；約束(18)表示一臺(tái)封箱機(jī)在單位時(shí)間內(nèi)最多生產(chǎn)一種品牌的卷煙；約束(19)表示庫(kù)存平衡，為了確保模型在需求預(yù)期不準(zhǔn)確的情形下仍然存在可行解，我們?cè)O(shè)置了一個(gè)虛擬的包裝機(jī)，此包裝機(jī)不需要與封箱機(jī)相連接。在具體問題中，可以設(shè)置虛擬包裝機(jī)的產(chǎn)能qM+1,k正比于需求的不確定性，當(dāng)需求不確定越高時(shí)，虛擬包裝機(jī)的產(chǎn)能越大，這樣保證模型始終存在可行解，對(duì)于缺貨成本，則可以通過ρM+1,k來(lái)刻畫，即認(rèn)為品牌的缺貨成本越高，虛擬包裝機(jī)所生產(chǎn)的商品質(zhì)量越低。通過設(shè)置較高的虛擬包裝機(jī)產(chǎn)能，模型可以用于應(yīng)對(duì)需求的不確定性，并將缺貨成本考慮在最終的目標(biāo)函數(shù)之中；約束(20)表示某些品牌的卷煙由于市場(chǎng)需求無(wú)法準(zhǔn)確估計(jì)因此期初應(yīng)安排生產(chǎn)；約束(21)表示某些包裝機(jī)只能生產(chǎn)指定品牌的卷煙；約束(22)表示所有的決策變量均為二元變量；約束(23)是變量的取值約束。

3 遺傳算法

由于前述的一般性模型具有NP-hard性，隨著排產(chǎn)的卷煙品牌和每道工序上機(jī)器數(shù)量的增加，該模型的規(guī)模便非常龐大，求解將變得十分困難。遺傳算法(GA)由于具有同時(shí)在多點(diǎn)進(jìn)行搜索，有可能獲得全局最優(yōu)解等等優(yōu)良特點(diǎn)[34]，對(duì)于結(jié)構(gòu)復(fù)雜的組合優(yōu)化問題有很好的效果，被廣泛應(yīng)用到工程領(lǐng)域解決生產(chǎn)計(jì)劃與詳細(xì)排產(chǎn)問題，產(chǎn)生唯一可行或多個(gè)可選可行方案。因此利用遺傳算法解決上述排產(chǎn)優(yōu)化問題，是求解卷煙企業(yè)優(yōu)化排產(chǎn)問題的一個(gè)較優(yōu)選擇。

遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索算法[34]，它從一組隨機(jī)產(chǎn)生的初始種群開始搜索過程，種群由染色體組成。染色體不斷經(jīng)過交叉和變異過程進(jìn)化，在每一代中用適應(yīng)值來(lái)評(píng)價(jià)染色體的優(yōu)劣，在新一代形成過程中，根據(jù)適應(yīng)值的大小選擇部分后代，適應(yīng)值較高的染色體被選中的概率較高。經(jīng)過若干代之后，算法滿足一定條件時(shí)收斂于最好的染色體，這樣就可能得到原問題的最優(yōu)解或次優(yōu)解。

本文的優(yōu)化問題約束比較復(fù)雜，采用遺傳算法求解此類具有多個(gè)不連通可行域，且解空間離散的復(fù)雜組合優(yōu)化問題時(shí)，對(duì)于不可行解的處理通常有以下三種：懲罰策略、修復(fù)策略以及改進(jìn)遺傳算子策略[20]。本文采用改進(jìn)遺傳算子和修復(fù)策略相結(jié)合的方法：生成初始種群時(shí)，根據(jù)約束特點(diǎn)，改進(jìn)遺傳算子，使初始個(gè)體滿足約束；在進(jìn)化過程中，合理設(shè)計(jì)遺傳操作并對(duì)遺傳操作后的后代進(jìn)行修復(fù)，使遺傳操作后子代個(gè)體仍滿足約束。

3.1 編碼方式

遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體，這一轉(zhuǎn)換操作稱為編碼。由于模型中存在諸多約束，顯然簡(jiǎn)單的二進(jìn)制編碼無(wú)法奏效，且本文的主要決策變量為三維變量，這時(shí)采用一維編碼很難表示，且交叉操作很不直觀，因此本文采用二維編碼方式。在本文的模型中，若給定Xikt，則嚴(yán)格遵守模型中式(5)～(23)約束條件的Zijt，Yjkt，Sit可按一定方法求得。

因此在滿足約束條件的前提下，為盡量減少算法復(fù)雜度，本文采取對(duì)Xikt編碼，之后按照約束條件計(jì)算其余決策變量的方法來(lái)處理該模型求解。具體編碼方式為將算法中種群的第h個(gè)染色體Gh表示為一個(gè)M×T的矩陣，矩陣中的每個(gè)元素為第i臺(tái)包裝機(jī)在第t個(gè)時(shí)間單位生產(chǎn)的卷煙牌號(hào)Kit，即

(24)

給定Xikt，生成Zijt的方法為：設(shè)染色體中Gh每列數(shù)字k出現(xiàn)的次數(shù)(即生產(chǎn)k品牌卷煙的包裝機(jī)總數(shù))為Bk，可生產(chǎn)k品牌卷煙的包裝機(jī)集合為Ψk。對(duì)于任意包裝機(jī)i∈Ψk，其能連接的封箱機(jī)集合為Ωi；對(duì)于任意封箱機(jī)j∈Ωi，其所能連接的最大包裝機(jī)數(shù)目為dj。將Bk和dj排序，按照順序依次分配封箱機(jī)給包裝機(jī)。如果Bk>dj,則計(jì)算Bk-dj, 將差值結(jié)果排序后繼續(xù)分配，直到Bk≤dj。如Bk或dj中有兩項(xiàng)相同，則隨機(jī)安排兩者的順序。對(duì)于無(wú)品牌生產(chǎn)的包裝機(jī)，分配虛擬封箱機(jī)與其連接。

例如：有8臺(tái)包裝機(jī)M1～M8，可連接3臺(tái)封箱機(jī)N1～N3，每臺(tái)封箱機(jī)最多連接4臺(tái)包裝機(jī)。染色體的某一列(即某一單位時(shí)間的排產(chǎn)計(jì)劃)為[1 1 1 1 1 2 2 2]T，表示包裝機(jī)M1～M5生產(chǎn)卷煙品牌1，包裝機(jī)M6～M8生產(chǎn)卷煙品牌2，此時(shí)B1=5，B2=3，對(duì)應(yīng)地d1=d2=d3=4，但B1>d1，計(jì)算得B1-d1=1

給定Xikt，Zijt后，Yjkt可由約束(15)(16)確定。

3.2 初始種群

種群初始化的方法可采用在編碼矩陣中隨機(jī)產(chǎn)生卷煙品牌的方法，但本文中所述模型約束很多，為了保證初始解可行性，采用如下的初始化策略：

之后根據(jù)封箱機(jī)的約束檢查Xikt是否可行，具體方法為：檢查每列中不同的數(shù)字k的個(gè)數(shù)，即包裝機(jī)所生產(chǎn)的卷煙品牌的數(shù)目，記為TB；這些包裝機(jī)可連接的封箱機(jī)總數(shù)記為TN，若TB≤TN，則Xikt可行；否則初始解不可行，需要重新生成。

3.3 適應(yīng)度函數(shù)

在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群體中的概率。適應(yīng)度函數(shù)非常關(guān)鍵，它是評(píng)價(jià)個(gè)體優(yōu)劣的唯一指標(biāo)，直接影響到遺傳算法的收斂速度，因此建立合適的適應(yīng)度函數(shù)是非常重要的。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。對(duì)于模型的目標(biāo)函數(shù)，可取適應(yīng)度函數(shù)為C/(z1ω1+z2ω2+z3ω3+z4ω4)，其中C為一調(diào)節(jié)系數(shù)，使得適應(yīng)度不會(huì)過小。這樣目標(biāo)值最小時(shí)適應(yīng)度函數(shù)最大，保證了適應(yīng)度函數(shù)為正，且便于排序和選擇概率的計(jì)算。

3.4 選擇方式

本文采用的選擇策略結(jié)合輪盤賭策略與精英保留策略，首先按照輪盤賭方式執(zhí)行遺傳算法的選擇功能，之后將當(dāng)前解群體中適應(yīng)度最高的個(gè)體替換掉當(dāng)前群體中的最差個(gè)體。這樣有效保證遺傳算法終止時(shí)得到的結(jié)果一定是歷代出現(xiàn)過的適應(yīng)度最高的個(gè)體,同時(shí)避免了算法陷入局部最優(yōu)解。

3.5 自適應(yīng)交叉運(yùn)算

設(shè)計(jì)交叉算子是遺傳算法中最關(guān)鍵的步驟，它決定了遺傳算法的全局搜索能力,也是逐步產(chǎn)生最優(yōu)解最重要的遺傳算子，常用的交叉算法有雙親雙子法、變化交配法、多交配法等方法等[7]。在生產(chǎn)調(diào)度問題中應(yīng)用遺傳算法最重要的就是讓子代能夠繼承父代的優(yōu)良特性，根據(jù)本文的問題，為盡量保證交叉后子代仍滿足需求約束，采用隨機(jī)互換父代染色體矩陣中某一列的方法，如圖2所示。

圖2 自適應(yīng)交叉過程

本文的交叉概率采用Srinvivas等[36]提出的自適應(yīng)遺傳算法確定交叉概率，交叉概率能夠隨著適應(yīng)度大小而改變。適應(yīng)度值高于群體平均適應(yīng)度值的個(gè)體的交叉概率較低，得以進(jìn)入下一代；而低于平均適應(yīng)度值的個(gè)體則具有較高的交叉概率，使該個(gè)體被淘汰掉。交叉概率為

(25)

其中f′為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值，其中fmax為群體中最大的適應(yīng)度值，favg為群體的平均適應(yīng)度值；f為要變異個(gè)體的適應(yīng)度值。

最后參照種群初始化的方法，根據(jù)封箱機(jī)的約束檢查交叉之后的Xikt是否可行，若不可行則從種群中排除該個(gè)體，再隨機(jī)生成一個(gè)新的可行染色體。

3.6 自適應(yīng)變異運(yùn)算

變異算子能夠從很大程度上提高群體的多樣性，跳出局部最優(yōu)解，也是遺傳算法重要的算子之一。為了在保證種群多樣性的同時(shí)保留父代優(yōu)良的基因，保證遺傳算法的收斂性，與自適應(yīng)交叉概率類似，本文的變異概率采用Srinvivas等[36]提出的自適應(yīng)遺傳算法確定變異概率，變異概率為

(26)

具體變異方法為：在現(xiàn)有種群中以變異概率Pm隨機(jī)選擇一個(gè)染色體，隨機(jī)選擇染色體的兩列互換位置，通過調(diào)整不同品牌卷煙的生產(chǎn)計(jì)劃，促進(jìn)最優(yōu)解的產(chǎn)生。

變異后參照初始化和交叉操作的方法，采用順時(shí)段庫(kù)存平衡法進(jìn)行修復(fù)并檢查封箱機(jī)約束,若修復(fù)失敗，或修復(fù)后的染色體不能滿足封箱機(jī)約束，則從種群中排除該個(gè)體，再隨機(jī)生成一個(gè)新的可行染色體。

3.7 算法終止條件

采用張鐵男等[37]提出的終止判斷條件：為保證計(jì)算結(jié)果精度，給定極小常數(shù)ε，當(dāng)種群中某代與上一代適應(yīng)度函數(shù)的均值差與上一代適應(yīng)度函數(shù)均值比值的絕對(duì)值小于ε，或算法迭代次數(shù)到達(dá)指定值時(shí)認(rèn)為算法達(dá)到收斂條件，終止算法。

4 算例分析

本文的算例在在Intel Core i7、CPU主頻3.40GHz、8GB內(nèi)存的Windows 10操作系統(tǒng)下使用MatlabR2015a測(cè)試，以某卷煙企業(yè)月平均生產(chǎn)數(shù)據(jù)作為實(shí)例分析。卷煙企業(yè)的計(jì)劃生產(chǎn)周期為一個(gè)月，企業(yè)需要決定每日的排產(chǎn)方案，在滿足市場(chǎng)需求的前提下優(yōu)化生產(chǎn)流程。根據(jù)上級(jí)部門下達(dá)的總生產(chǎn)計(jì)劃，結(jié)合市場(chǎng)部門以往卷煙的銷售經(jīng)驗(yàn)，該企業(yè)總結(jié)出了不同品牌卷煙的時(shí)段需求比例以及每月月初的庫(kù)存比例以作為生產(chǎn)的依據(jù)，日需求量根據(jù)周需求量進(jìn)行平均。卷煙企業(yè)生產(chǎn)設(shè)備包括14臺(tái)不同種類的包裝機(jī)，5臺(tái)封箱機(jī)，共需生產(chǎn)7種品牌的卷煙。表1列出了上述卷煙生產(chǎn)信息。其中牌號(hào)7為新投入市場(chǎng)的品牌，其市場(chǎng)需求不確定，因此需要優(yōu)先生產(chǎn)。該品牌的月需求總量是根據(jù)相似品牌的歷史需求與市場(chǎng)調(diào)研結(jié)果給出的保守估計(jì)，以保證滿足市場(chǎng)需求。

表1 各個(gè)品牌卷煙周需求和月度總需求及初始庫(kù)存量

由于同一卷煙品牌在不同機(jī)臺(tái)上生產(chǎn)的品質(zhì)是不一樣的，因此不同卷煙品牌在不同機(jī)臺(tái)上生產(chǎn)會(huì)有不同的質(zhì)量系數(shù)。表2為該卷煙企業(yè)根據(jù)自己的生產(chǎn)經(jīng)驗(yàn)總結(jié)出了不同卷煙在不同包裝機(jī)生產(chǎn)的質(zhì)量系數(shù)，質(zhì)量系數(shù)越低表示包裝機(jī)生產(chǎn)的卷煙質(zhì)量越好，質(zhì)量系數(shù)為0表示包裝機(jī)不能生產(chǎn)該品牌的卷煙。該企業(yè)的生產(chǎn)機(jī)臺(tái)安排為：包裝機(jī)A1～A6對(duì)應(yīng)兩臺(tái)GDX2型封箱機(jī)，B1～B6對(duì)應(yīng)兩臺(tái)FK型封裝機(jī)，A7和C8對(duì)應(yīng)一臺(tái)GDX2型封箱機(jī)，每臺(tái)封箱機(jī)最多可連接4臺(tái)包裝機(jī)。

表2 不同卷煙在不同包裝機(jī)生產(chǎn)的質(zhì)量系數(shù)

關(guān)于排產(chǎn)方式：該卷煙企業(yè)一般在每月月底根據(jù)上級(jí)公司發(fā)布的下月生產(chǎn)指標(biāo)(品牌，數(shù)量)和市場(chǎng)需求情況，制定下月的生產(chǎn)計(jì)劃、進(jìn)行排產(chǎn)；在次月的中旬組織生產(chǎn)調(diào)度會(huì)，總結(jié)、調(diào)整本月的生產(chǎn)計(jì)劃，并發(fā)布下月的生產(chǎn)預(yù)測(cè)(預(yù)計(jì)劃)，以準(zhǔn)備生產(chǎn)原料。

關(guān)于約束條件：除上述模型提到的條件之外，該卷煙企業(yè)還有自己特有的約束條件。第一，該卷煙企業(yè)要求所有機(jī)器同時(shí)停止，方便工企業(yè)進(jìn)行管理。第二，該企業(yè)為保證滿足市場(chǎng)需求，每月月初的在制品量(庫(kù)存)一般保持穩(wěn)定，因此月末的庫(kù)存量應(yīng)與月初的庫(kù)存量水平相差不大。

關(guān)于目標(biāo)函數(shù)：由于該卷煙企業(yè)庫(kù)存成本很小，而且不同包裝機(jī)生產(chǎn)的卷煙質(zhì)量基本相差不大，因此卷煙企業(yè)的主要優(yōu)化目標(biāo)是最小化生產(chǎn)時(shí)間和換牌次數(shù)。

針對(duì)上述生產(chǎn)特點(diǎn)，建立整數(shù)規(guī)劃模型后，采用遺傳算法，對(duì)包裝機(jī)排產(chǎn)模型進(jìn)行求解。經(jīng)過對(duì)本研究算法各參數(shù)的預(yù)實(shí)驗(yàn)，本文選取參數(shù)設(shè)置如表3所示，其中#pop表示種群數(shù)量，實(shí)驗(yàn)進(jìn)行20次，最大進(jìn)化代數(shù)為1000。預(yù)實(shí)驗(yàn)還發(fā)現(xiàn)，初始種群的選取對(duì)算法的收斂時(shí)間影響很大。對(duì)于本算例而言，在初始種群中除隨機(jī)產(chǎn)生和啟發(fā)式方法產(chǎn)生的初始解外，還加入了卷煙企業(yè)憑經(jīng)驗(yàn)排產(chǎn)的方案，以加速算法收斂。

表3 遺傳算法參數(shù)設(shè)置

20次優(yōu)化的最小生產(chǎn)時(shí)間均為29天，與卷煙企業(yè)憑經(jīng)驗(yàn)排產(chǎn)的結(jié)果相一致，而最優(yōu)換牌次數(shù)則有所不同。表4展示了最優(yōu)換牌次數(shù)的優(yōu)化結(jié)果，標(biāo)準(zhǔn)差在1次之內(nèi)，證明了本研究算法的有效性和穩(wěn)定性。

圖3 遺傳算法收斂過程曲線

優(yōu)化后得到的生產(chǎn)排程結(jié)果，生產(chǎn)天數(shù)為29天，換牌次數(shù)為8次，最優(yōu)生產(chǎn)天數(shù)與卷煙企業(yè)經(jīng)驗(yàn)排產(chǎn)的結(jié)果相一致，而換牌次數(shù)則得到了顯著降低，圖3展示了最優(yōu)換牌次數(shù)的遺傳進(jìn)化曲線，優(yōu)化后的包裝機(jī)生產(chǎn)安排如圖4所示。

圖4 遺傳算法優(yōu)化排產(chǎn)結(jié)果

在滿足市場(chǎng)需求的條件下，本文的算法優(yōu)化了換牌次數(shù)，證明了算法的可行性，并得到了卷煙企業(yè)排產(chǎn)人員的認(rèn)可。目前，該算法已作為某卷煙企業(yè)排產(chǎn)人員的排產(chǎn)參考，應(yīng)用于生產(chǎn)決策中。該算法可以快速高效地制定卷煙生產(chǎn)排程計(jì)劃，為卷煙企業(yè)計(jì)劃人員制定生產(chǎn)計(jì)劃提供決策支持，有效降低因卷煙品牌轉(zhuǎn)換造成的大量轉(zhuǎn)換成本，優(yōu)化生產(chǎn)流程。

為了進(jìn)一步測(cè)試本文的求解算法(稱為Improved Genetic Algorithm，IGA算法)的優(yōu)化性能，本文分別采用了標(biāo)準(zhǔn)遺傳算法(Standard Genetic algorithm, SGA)、模擬退火算法(Simulated annealing, SA)和優(yōu)化求解軟件ILOGCPLEX 12.6進(jìn)行對(duì)比實(shí)驗(yàn)。每種算法都獨(dú)立運(yùn)行20次。具體算法設(shè)置為：SGA算法隨機(jī)產(chǎn)生初始種群并去掉不滿足約束解，交叉和變異方式除概率固定外其余與IGA算法相同，采用輪盤賭和精英保留策略選擇新一代個(gè)體。GA的算法參數(shù)設(shè)置為:種群規(guī)模為100,交叉概率0.95,變異概率0.05。GA的算法停止規(guī)則與IGA相同。SA算法隨機(jī)產(chǎn)生初始個(gè)體,采用與本文IGA算法中變異相似的交換方式(Swap)產(chǎn)生鄰域個(gè)體,按照Metropolis抽樣過程產(chǎn)生新個(gè)體。SA算法中的參數(shù)值為:初始溫度為100,終止溫度為0.001,退火速率為0.9995。

測(cè)試結(jié)果如表5所示。Cmax表示最優(yōu)的最大化生產(chǎn)時(shí)間，本算例中不同算法獨(dú)立運(yùn)行20次均得到相同的最大化生產(chǎn)時(shí)間29天。TS表示最優(yōu)換牌次數(shù)，BVE(TS)表示20次仿真獲得的最優(yōu)換牌次數(shù)，AVE(TS)表示20次仿真獲得的平均換牌次數(shù)，STD(TS)表示20次仿真結(jié)果的標(biāo)準(zhǔn)差。

表5 算法性能比較

可以看出，對(duì)于本文中的案例，IGA算法相對(duì)于SGA和SA算法得到的結(jié)果具有更小的平均值和標(biāo)準(zhǔn)差(ILOG CPLEX采用確定性算法，因此結(jié)果標(biāo)準(zhǔn)差為0)，這說明IGA算法不僅有較高的精度, 而且具有較高的魯棒性,結(jié)果受隨機(jī)因素的影響較小。從時(shí)間性能方面來(lái)說，IGA算法相對(duì)于其他算法消耗的時(shí)間更長(zhǎng)，但這一方面受算法終止條件的影響，同時(shí)也避免了算法過早陷入局部最優(yōu)解。

5 結(jié)論

卷煙包裝至封箱環(huán)節(jié)的生產(chǎn)過程將直接決定庫(kù)存成品是否能夠滿足市場(chǎng)需求，是卷煙企業(yè)排產(chǎn)計(jì)劃的核心；該過程中的批量計(jì)劃和作業(yè)排序問題，是卷煙企業(yè)生產(chǎn)計(jì)劃得以貫徹執(zhí)行的基礎(chǔ)。因此對(duì)卷煙企業(yè)生產(chǎn)批量計(jì)劃和調(diào)度集成問題的研究具有重要的工程意義。本文對(duì)卷煙生產(chǎn)過程中的生產(chǎn)計(jì)劃和柔性流水車間調(diào)度集成問題進(jìn)行了優(yōu)化，以減少生產(chǎn)時(shí)間，降低換牌次數(shù)及庫(kù)存成本、提高卷煙生產(chǎn)質(zhì)量作為排程優(yōu)化的目標(biāo)。建立了基于卷煙企業(yè)生產(chǎn)約束條件的整數(shù)規(guī)劃模型，并利用遺傳算法對(duì)模型進(jìn)行求解，通過合理設(shè)計(jì)遺傳算子避免了不可行解的出現(xiàn)。利用某卷煙企業(yè)的生產(chǎn)數(shù)據(jù)給出了具體排程結(jié)果，并與該企業(yè)之前經(jīng)驗(yàn)排產(chǎn)方案進(jìn)行對(duì)比，發(fā)現(xiàn)優(yōu)化排程模型和算法在減少換牌次數(shù)，提高生產(chǎn)的連續(xù)性方面具有明顯優(yōu)勢(shì)，證明了模型的有效性和穩(wěn)定性。