高珂婷

（天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300380）

0 引言

混合流水線車間調(diào)度問題（Hybrid Flow shop Schedul?ing Problem，HFSP）是一個(gè)典型的NP-hard 難題，其結(jié)合了傳統(tǒng)的Flow shop 調(diào)度問題和多機(jī)并行分配問題，故其解決方案更加復(fù)雜。

遺傳算法（Genetic Algorithm，GA）作為一種自組織、自適應(yīng)、自學(xué)習(xí)的全局搜索算法［1］，具有很強(qiáng)的魯棒性和并行搜索能力，可以防止陷入局部最優(yōu)。利用仿真軟件通過構(gòu)建仿真模型計(jì)算調(diào)度問題的目標(biāo)函數(shù)值可以免去構(gòu)建復(fù)雜的數(shù)學(xué)模型，直觀地觀察到車間流水線最優(yōu)的調(diào)度路線，實(shí)現(xiàn)最小化最大完工時(shí)間與總生產(chǎn)成本等目標(biāo)。

近年來，學(xué)者們對(duì)混線排序問題的研究不斷深入。一部分文獻(xiàn)利用仿真軟件對(duì)該問題進(jìn)行優(yōu)化，如文獻(xiàn)［2］利用仿真軟件建立混流裝配線的物料配送系統(tǒng)仿真模型，對(duì)物料系統(tǒng)進(jìn)行優(yōu)化；文獻(xiàn)［3］針對(duì)某軍工車間的生產(chǎn)任務(wù)進(jìn)行排產(chǎn)仿真，得到合理的作業(yè)規(guī)劃；文獻(xiàn)［4］參考企業(yè)提供的實(shí)際參數(shù)及條件，在不同優(yōu)化目標(biāo)下利用仿真軟件進(jìn)行對(duì)比分析，提出最佳措施；文獻(xiàn)［5］針對(duì)供應(yīng)鏈庫存管理提出一種仿真優(yōu)化方法作為過程控制策略。還有一部分文獻(xiàn)結(jié)合相關(guān)算法對(duì)該問題進(jìn)行優(yōu)化，如文獻(xiàn)［6］提出最優(yōu)家族遺傳算法解決了超大規(guī)模車間調(diào)度效率低的問題；文獻(xiàn)［7］針對(duì)實(shí)時(shí)生產(chǎn)系統(tǒng)提出一種調(diào)度算法和啟發(fā)式方法，使生產(chǎn)線上的零件使用率保持恒定；文獻(xiàn)［8］用GA 求解混流裝配線排序問題，在求解速度方面表現(xiàn)良好；文獻(xiàn)［9］將GA 與局部優(yōu)化程序相結(jié)合，用于生成針對(duì)流水線平衡問題的多種解決方案，提高了執(zhí)行速度；文獻(xiàn)［10］采用改進(jìn)粒子群優(yōu)化生成系統(tǒng)中的管理參數(shù)，并借助仿真軟件很好地解決了裝配線平衡問題。

綜上所述，對(duì)于車間調(diào)度問題的求解可以結(jié)合仿真方法和遺傳算法，該方法具有很好的通用性［11］。針對(duì)HFSP這一復(fù)雜問題，本文以Plant Simulation 作為仿真建模工具，建立實(shí)例中的車間流水線調(diào)度模型，再用遺傳算法（GA）結(jié)合SPT 規(guī)則進(jìn)行仿真優(yōu)化，調(diào)度目標(biāo)是最小化Makespan（最大加工完成時(shí)間），最后通過Plant Simulation仿真平臺(tái)上的優(yōu)化結(jié)果驗(yàn)證其有效性［12］。

1 問題描述

混合流水線車間調(diào)度問題可描述為：n 個(gè)工件在一臺(tái)或多臺(tái)機(jī)床上通過m 道工序完成加工，各道工序的加工時(shí)間已知［13］，如圖1 所示。

Fig.1 HFSP scheduling problem圖1 HFSP 調(diào)度問題

一般混合流水線車間調(diào)度問題有如下假設(shè)：①在加工過程中，所有工件只能在一臺(tái)機(jī)器上加工；②下一道工序必須在上一道工序結(jié)束后才能開始進(jìn)行；③各工序的加工設(shè)備可獨(dú)立完成全部工件的加工；④每個(gè)工件必須完成該工序的操作后才能開始下一道工序；⑤工件位置按一定優(yōu)先級(jí)排列，位置越靠前越早開始加工；⑥若遇到工件的同一道工序恰好需要在同一臺(tái)機(jī)器上完成，則后一個(gè)工件必須等前一個(gè)工件加工完成后再進(jìn)行加工［14］。

2 遺傳算法

2.1 染色體編碼

通常古典生產(chǎn)車間調(diào)度問題共有8 種染色體編碼方式，本文采用基于矩陣的實(shí)數(shù)編碼方式作為染色體編碼方式。對(duì)于n 個(gè)工件、m 臺(tái)機(jī)器的問題，可構(gòu)造M×N 矩陣［15］：

其中j=1，2，…，m，i=1，2，…，n，aji表示第i個(gè)工件的第j道工序，該實(shí)數(shù)取值區(qū)間為［1，M(j)+1］［16］，M(j) 為第j道工序包含的機(jī)器數(shù)，整數(shù)部分表示所在工序的機(jī)器號(hào)，小數(shù)部分表示加工優(yōu)先級(jí)。如a21=3.1，a22=3.8，a24=3.4，表示工件1、2、4 的M2工序均使用編號(hào)為3 的機(jī)器，而由于3.1＜3.4＜3.8，故加工次序?yàn)楣ぜ?/工件4/工件2。除第一道工序按上述編碼規(guī)則對(duì)工件進(jìn)行排序外，后面的工序應(yīng)加入一定的優(yōu)先規(guī)則，本文采取最短作業(yè)時(shí)間（Shortest Process?ing Time，SPT）規(guī)則。

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

遺傳算法基因被選擇遺傳的機(jī)會(huì)取決于所組成的染色體適應(yīng)度大?。?7］，如何使適應(yīng)度函數(shù)與求解對(duì)象有效匹配是檢驗(yàn)遺傳算法有效性的關(guān)鍵。對(duì)于HFSP 問題，求解目標(biāo)為Makespan 的最小值，所以采用Cmax的倒數(shù)作為適應(yīng)度函數(shù)。n 個(gè)工件經(jīng)過m 道工序，其中染色體pop｛i｝在每道工序上花費(fèi)的時(shí)間為Cmax=max1≤i≤n{ }Ci，則適應(yīng)度函數(shù)表示為：

2.3 選擇算子

采用遺傳算法將適應(yīng)度值高的個(gè)體遺傳到下一代，即對(duì)種群進(jìn)行優(yōu)勝劣汰。本文選擇輪盤賭，其基本思想是：每個(gè)個(gè)體被選中的概率與其適應(yīng)度值成正比，即值越大，被選擇的概率越高，反之亦然。染色體i被選中遺傳到下一代的概率為：

其中，i=（1，2，…，n），n為種群大小，F(xiàn)i為染色體i的適應(yīng)度值。

2.4 交叉算子

對(duì)于HFSP 問題，由于排序在編碼中的唯一性，如果采用簡單交叉方法，會(huì)出現(xiàn)非法解，故這里使用部分映射交叉法（Partially Mapping Crossover，PMX）以避免該問題的產(chǎn)生，從而使解更有效。具體步驟描述為：①隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，在兩個(gè)染色體中的兩點(diǎn)之間交換基因；②若交換后的片段與交叉點(diǎn)外的基因不沖突，保留；③若存在沖突，則在交換基因集合中利用部分映射尋找替換基因，產(chǎn)生新個(gè)體。

PMX 具體過程如圖2 所示。

Fig.2 PMX specific process圖2 PMX 具體過程

2.5 變異算子

在序號(hào)編碼方式下，基因有兩種突變方式：一種是互聯(lián)變異，即在序列中隨機(jī)選擇兩個(gè)基因，交換其在染色體上的位置后形成新的后代個(gè)體，如個(gè)體［1，2，3，4，5，6，7，8，9］，隨機(jī)選擇2、8，交換后的個(gè)體為［1，8，3，4，5，6，7，2，9］。另一種是逆轉(zhuǎn)變異，即將在染色體中隨機(jī)選擇的兩點(diǎn)間基因段進(jìn)行逆轉(zhuǎn)，如個(gè)體［1，2，3，4，5，6，7，8，9］，隨機(jī)選擇2、5，逆轉(zhuǎn)后的個(gè)體為［1，2，5，4，3，6，7，8，9］。本文選擇互聯(lián)變異方式［18］。

3 案例仿真分析

3.1 Plant Simulation

Plant Simulation 平臺(tái)是Siemens 公司研發(fā)的一款仿真軟件，可用于優(yōu)化生產(chǎn)線及生產(chǎn)物流過程。其特點(diǎn)主要體現(xiàn)在面向?qū)ο蟮膭?dòng)態(tài)系統(tǒng)建模過程、模塊化和多層次的建模單元、圖形化和對(duì)象化的并行仿真環(huán)境、多類型接口、多種工具集成等方面［19］。

3.2 仿真模型

在本案例中，整個(gè)車間由9 臺(tái)設(shè)備（M1，M2，…，M9）加工12 個(gè)工件（J1，J2，…，J12），所有工件所需加工時(shí)間如表1所示［20］。

Table 1 All workpiece processing time表1 所有工件加工時(shí)間單位：h

在Plant Simulation 平臺(tái)中模擬建立本案例的車間制造模型，如圖3 所示。仿真部分包括區(qū)域1、3、4，GA 模塊位于區(qū)域2，其中區(qū)域1 中的Start 對(duì)象自動(dòng)生成區(qū)域4 中的模型，Jobs 對(duì)象存放由GA 模塊產(chǎn)生的某個(gè)體；區(qū)域3 中SUB_FSP 數(shù)據(jù)子層存放機(jī)床M1-M9對(duì)各個(gè)工件的加工時(shí)間，Result_Table 表存放個(gè)體仿真結(jié)果；區(qū)域2 中GAWizard和GASequence 為軟件自帶的遺傳算法優(yōu)化工具。

在GAWizard 模塊中設(shè)置種群規(guī)模為20，種群大小為15，在GASequence 模塊中設(shè)置交叉概率為0.8，變異概率為0.1。在Start 方法中，全局變量AssignRule 為2，通過GA 運(yùn)算優(yōu)化排程，得到優(yōu)化結(jié)果如圖4 所示（彩圖掃OSID 碼可見）。

Fig.3 Workshop manufacturing simulation model圖3 車間制造仿真模型

Fig.4 GA+SPT ranking results圖4 GA+SPT 排優(yōu)結(jié)果

Fig.5 GA+FIFS ranking results圖5 GA+FIFS 排優(yōu)結(jié)果

從圖4（橫坐標(biāo)代表種群代數(shù)，縱坐標(biāo)代表適應(yīng)值）可以看出，隨著遺傳代數(shù)的增加，運(yùn)算結(jié)果逐漸趨于最優(yōu)化，紅線代表每次進(jìn)化過程中種群的最優(yōu)排程方案，藍(lán)線代表最差排程方案，綠線是二者的平均值。采用SPT 調(diào)度規(guī)則在第12 代種群之后收斂到最佳個(gè)體，實(shí)現(xiàn)最優(yōu)的排序方式，工件加工順序?yàn)?-11-2-1-7-12-5-9-3-6-10-8，得到最優(yōu)適應(yīng)度值25。與圖5 中GA 結(jié)合FIFS 規(guī)則的結(jié)果相比，改進(jìn)算法可以更快地找到最優(yōu)方案，再運(yùn)行MyGantt 方法得到最優(yōu)排序結(jié)果甘特圖，如圖6 所示（彩圖掃描OSID碼可見），得到Makespan=25min，相比文獻(xiàn)［20］的最優(yōu)結(jié)果縮短了4min。

Fig.6 Optimal ranking result Gantt chart圖6 最優(yōu)排序結(jié)果甘特圖

4 結(jié)語

本文提出一種改進(jìn)遺傳算法，結(jié)合調(diào)度規(guī)則，使用Plant Simulation 仿真工具對(duì)流水線車間調(diào)度問題進(jìn)行優(yōu)化仿真，并結(jié)合示例說明其可行性，對(duì)企業(yè)生產(chǎn)可起到一定的指導(dǎo)作用。但由于車間調(diào)度的復(fù)雜性，要想更接近車間的實(shí)際生產(chǎn)情況，還需進(jìn)一步完善仿真模型，使其可擴(kuò)展到其它生產(chǎn)調(diào)度多目標(biāo)優(yōu)化問題上。