吳辰超，凌衛(wèi)青，戴毅茹

（同濟(jì)大學(xué)CIMS研究中心，上海 201804）

0 引言

隨著能源問(wèn)題的日益加劇，企業(yè)迫切需要提高生產(chǎn)效率和資源利用率，達(dá)到交貨期短、生產(chǎn)能耗小的生產(chǎn)要求，因此車(chē)間作業(yè)調(diào)度問(wèn)題的研究顯得尤為重要。本文以某重型裝備企業(yè)生產(chǎn)流程作為模型，結(jié)合中心開(kāi)發(fā)的企業(yè)生產(chǎn)與能耗耦合建模仿真軟件對(duì)優(yōu)化調(diào)度結(jié)果進(jìn)行仿真。應(yīng)用遺傳算法，在機(jī)器準(zhǔn)備時(shí)間、加工時(shí)間、單位時(shí)間能源消耗等初始參數(shù)不變的情況下，通過(guò)改變生產(chǎn)的投料順序，達(dá)到總生產(chǎn)時(shí)間、總能源消耗最少的目標(biāo)。

1 遺傳算法與重型裝備企業(yè)優(yōu)化排程研究

1.1 重型裝備企業(yè)特點(diǎn)

重型裝備制造企業(yè)是典型的能耗大戶，其消耗的能源介質(zhì)包括電、煤、天然氣、煤氣、蒸汽、氧氣、水等。重型裝備制造企業(yè)能源管理普遍屬于粗放型、分散化的模式，其熱加工處理環(huán)節(jié)消耗能量巨大，熱加工排程往往采用人工經(jīng)驗(yàn)方式制定，沒(méi)有考慮到能源約束，熱加工環(huán)節(jié)往往不考慮到余熱的回收利用，熱能損失大，所以對(duì)重型的裝備企業(yè)的能耗實(shí)行精細(xì)化管理、對(duì)企業(yè)的生產(chǎn)排程進(jìn)行優(yōu)化是企業(yè)節(jié)能減排與緩解企業(yè)能源約束矛盾的根本措施。

1.2 遺傳算法優(yōu)化調(diào)度應(yīng)用

在國(guó)內(nèi)企業(yè)對(duì)生產(chǎn)排程的調(diào)度由于技術(shù)上的制約，基本上是依靠技術(shù)人員的經(jīng)驗(yàn)。隨著智能算法尤其是遺傳算法的研究越來(lái)越成熟，遺傳算法在企業(yè)生產(chǎn)排程上的應(yīng)用也越來(lái)越多。

基本遺傳算法[6]（簡(jiǎn)稱SGA）是一種種群型操作，該操作以種群中的所有個(gè)體為對(duì)象，只使用基本遺傳算子、選擇算子、交叉算子和變異算子，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其他一些遺傳算法的基礎(chǔ)，不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。選擇、交叉和變異是遺傳算法的三個(gè)主要操作算子，它們構(gòu)成了所謂的遺傳操作，使遺傳算法有了其他傳統(tǒng)方法沒(méi)有的特點(diǎn)。

圖1 遺傳算法流程圖Fig.1 Genetic algorithm flow chart

1.3 建模仿真工具介紹

優(yōu)化結(jié)果的驗(yàn)證通過(guò)重型裝備能耗耦合建模仿真軟件來(lái)實(shí)現(xiàn)，該軟件是用C#在.NET平臺(tái)上開(kāi)發(fā)的用來(lái)模擬企業(yè)生產(chǎn)過(guò)程中能源消耗過(guò)程。通過(guò)對(duì)重型裝備企業(yè)生產(chǎn)流程的建模，能夠清晰地反映出生產(chǎn)過(guò)程中的能源流、物料流、信息流和排放流。在設(shè)置完設(shè)備加工時(shí)間、設(shè)備能耗、加工訂單數(shù)量、物料加工時(shí)間等參數(shù)后，通過(guò)對(duì)相應(yīng)模型的仿真，能夠得到一次加工過(guò)程所消耗的折標(biāo)能源總量、單臺(tái)設(shè)備所消耗的折標(biāo)能源總量等數(shù)值，為驗(yàn)證優(yōu)化結(jié)果是否正確提供了一條有效的途徑。

2 遺傳算法在生產(chǎn)調(diào)度中的應(yīng)用

2.1 企業(yè)背景

某重型裝備廠是一家典型的高能耗企業(yè)，該企業(yè)對(duì)于節(jié)能減排的需求相當(dāng)迫切。近些年，企業(yè)結(jié)合自身情況逐步對(duì)一些耗能設(shè)備進(jìn)行了節(jié)能改造。如鍋爐加裝分層燃燒裝置，增設(shè)蒸汽蓄熱器和引進(jìn)天然氣替代自制發(fā)生爐煤氣及重油，但是隨著公司熱加工產(chǎn)品的比重上升，能耗呈加速上升趨勢(shì)。

目前，比較常用的應(yīng)用于企業(yè)節(jié)能減排的方法主要有以下幾種方式。通過(guò)改變?cè)O(shè)備的工藝參數(shù)，在保證生產(chǎn)產(chǎn)品質(zhì)量的情況下，減少工件加工時(shí)間、降低加工爐膛溫度等。在生產(chǎn)過(guò)程中通過(guò)余熱回收，提高燃油、煤炭等能源介質(zhì)的熱效率。改變生產(chǎn)排程，使工件間加工過(guò)程更加緊湊，從而提高了設(shè)備的利用率，減少了設(shè)備的開(kāi)機(jī)總時(shí)間、啟停次數(shù)、保溫時(shí)間。本案例通過(guò)遺傳算法對(duì)企業(yè)的生產(chǎn)排程及設(shè)備調(diào)度策略可行解進(jìn)行快速搜索，找到最佳的生產(chǎn)排程及設(shè)備調(diào)度方案，實(shí)現(xiàn)企業(yè)節(jié)能減排的目標(biāo)。

2.2 軟件總體設(shè)計(jì)思想

遺傳算法后臺(tái)操作主要包含兩個(gè)類：染色體類與遺傳操作類。染色體類中包含了用來(lái)存儲(chǔ)基本遺傳信息的一些屬性如染色體碼、染色體適應(yīng)值、染色體輪盤(pán)選擇概率等。遺傳操作類屬性主要包含兩部分?jǐn)?shù)據(jù)，一部分是用來(lái)記錄遺傳操作控制信息如遺傳代數(shù)、種群大小、交叉概率、變異概率等。另一部分用來(lái)記錄每一代進(jìn)化過(guò)程中的中間信息如染色體種群適應(yīng)值的平均值、染色體種群中最優(yōu)染色體、染色體種群中最差染色體等。

（1）編碼設(shè)計(jì)。遺傳算法編碼采用整數(shù)編碼，將一條染色體分成兩部分，前半部分為企業(yè)生產(chǎn)計(jì)劃信息，例如 [3142]編碼方式表示企業(yè)先加工3號(hào)訂單，其次是1號(hào)與4號(hào)訂單，最后是2號(hào)訂單。后半部分為設(shè)備調(diào)度策略信息，例如 [1132]編碼方式表示1號(hào)設(shè)備使用第一種工件進(jìn)入策略，第2臺(tái)設(shè)備使用第一種工件進(jìn)入策略，第三臺(tái)設(shè)備使用第三種工件進(jìn)入策略。設(shè)備的每種進(jìn)入策略包含在建模信息中，只要在仿真過(guò)程中讀取即可，如第一種工件進(jìn)入策略為先到先加工（FIFO），第二種工件進(jìn)入策略為最短加工時(shí)間優(yōu)先（SPT），只需根據(jù)建模信息映射即可。在軟件中，染色體編碼信息以動(dòng)態(tài)數(shù)組（List＜＞）的方式保存。

（2）適應(yīng)度函數(shù)設(shè)計(jì)。針對(duì)優(yōu)化目標(biāo)為生產(chǎn)能耗最小的情況，選取電消耗、天然氣消耗、煤氣消耗折標(biāo)求和后的值直接作為優(yōu)化的適應(yīng)度函數(shù)。由于本案例屬于最小化優(yōu)化問(wèn)題，所以在做選擇操作時(shí)必須以適應(yīng)值最小作為最優(yōu)條件。

（3）遺傳操作設(shè)計(jì)思想：①初始化種群操作：主要根據(jù)優(yōu)化操作的基本信息生成符合要求的初始種群；②選擇操作：采用輪盤(pán)賭選擇方法。進(jìn)行輪盤(pán)賭選擇操作時(shí)，首先按照適應(yīng)值大小進(jìn)行排序，適應(yīng)值小的染色體排在前，適應(yīng)值大的染色體排在后，然后進(jìn)行選擇概率統(tǒng)計(jì)，計(jì)算出每條染色體的適應(yīng)值與所有染色體適應(yīng)值的和之間的比值。由于該問(wèn)題是最小化問(wèn)題，所以在計(jì)算完概率值后，將對(duì)應(yīng)染色體的概率值進(jìn)行逆序操作，保證適應(yīng)值小的染色體被選擇到的概率大。完成這些操作后再分別將這些數(shù)值從第一條染色體開(kāi)始進(jìn)行累加，并將累加值存入對(duì)應(yīng)的染色體中。進(jìn)行選擇時(shí)，只需用調(diào)用Random類的NextDouble方法，生成一個(gè)0～1之間的隨機(jī)小數(shù)，并將其與遺傳池中的每個(gè)染色體累計(jì)值進(jìn)行比較，當(dāng)隨機(jī)小數(shù)值大于染色體累積值時(shí)，選擇當(dāng)前染色體進(jìn)入選擇池。重復(fù)此操作，直到選擇的染色體數(shù)量滿足種群大小要求；③交叉操作：按照交叉概率選擇一定數(shù)量的染色體進(jìn)入交叉池，例如當(dāng)交叉概率為0.4，種群大小為10時(shí)，則選擇4條染色體進(jìn)入交叉池執(zhí)行交叉操作，交叉的方法采用單點(diǎn)交叉法，交叉點(diǎn)的位置由隨機(jī)數(shù)生成，由于訂單排程編碼必須保證唯一性原則，所以交叉點(diǎn)選擇范圍為第一個(gè)設(shè)備策略碼至最后一個(gè)策略碼；④變異操作：按照變異概率選擇一定數(shù)量的染色位并改變其值，當(dāng)變異概率為0.05時(shí)，表示每一百個(gè)染色體位中，有五個(gè)位要發(fā)生變異。變異操作的實(shí)現(xiàn)是通過(guò)對(duì)染色體池中的每條染色體的每一位進(jìn)行遍歷，每次遍歷通過(guò)Random類的NextDouble方法，生成一個(gè)0～1之間的隨機(jī)小數(shù)，當(dāng)該小數(shù)小于變異概率時(shí)，則進(jìn)行當(dāng)前位的變異操作。

2.3 仿真結(jié)果及分析

為驗(yàn)證算法解決調(diào)度問(wèn)題的有效性，結(jié)合某重型裝備企業(yè)的生產(chǎn)流程與生產(chǎn)仿真軟件進(jìn)行仿真，工件加工路徑在建模時(shí)確定，工件加工時(shí)間、準(zhǔn)備時(shí)間等設(shè)備參數(shù)在仿真前設(shè)定。加工初始訂單根據(jù)企業(yè)生產(chǎn)情況確定，如圖2所示。

圖2 生產(chǎn)計(jì)劃輸入界面Fig.2 Production plan input interface

遺傳算法使用的參數(shù)如下：種群大小M=20；遺傳運(yùn)算終止進(jìn)化代數(shù)T=30；交叉概率=0.5；變異=0.05。由仿真優(yōu)化報(bào)告可知，當(dāng)按照優(yōu)化算法得出訂單投料順序?yàn)?324、機(jī)器使用調(diào)度策略如圖3所示時(shí)，生產(chǎn)能耗（折標(biāo)能耗）比使用隨機(jī)投料與機(jī)器隨機(jī)調(diào)度方式的情況下的能耗少了7.09%。

圖3 優(yōu)化結(jié)果展示界面Fig.3 Optimization results show interface

3 結(jié)束語(yǔ)

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性，遺傳算法是解決生產(chǎn)調(diào)度問(wèn)題的一種有效途徑。生產(chǎn)調(diào)度問(wèn)題在很多情況下建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解.也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。目前在單件生產(chǎn)車(chē)間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。

[1]王錫祿.Job-Shop調(diào)度問(wèn)題的優(yōu)化模型及算法[J].系統(tǒng)工程理論與實(shí)踐，2000，1.

[2]謝勝利，策金祥，黃強(qiáng).基于遺傳算法的車(chē)間作業(yè)調(diào)度問(wèn)題求解[J].計(jì)算機(jī)工程與應(yīng)用，2002，10.

[3]王凌.車(chē)間調(diào)度及其遺傳算法[M].清華大學(xué)出版社，2003.

[4]陸薄.作業(yè)車(chē)間調(diào)度的建模及優(yōu)化方法研究[D].上海.上海交通大學(xué)，2007.

[5]馮紅娟.基于遺傳算法的車(chē)間作業(yè)調(diào)度問(wèn)題研究[D].長(zhǎng)春理工大學(xué)，2008.

[6]周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].國(guó)防工業(yè)出版社，1999.