改進遺傳算法求解柔性作業(yè)車間調(diào)度問題

陽光燦，熊禾根

(武漢科技大學機械自動化學院，湖北 武漢 430081)

1 引言

作業(yè)車間調(diào)度問題(JSP，Job shop scheduling problem)是一類具有機器約束和順序約束的組合優(yōu)化問題，在數(shù)學上屬于是典型的NP-Hard問題。與JSP相比，柔性作業(yè)車間調(diào)度問題(FJSP，F(xiàn)lexible job shop scheduling problem)減少了機器約束，是一類更符合實際生產(chǎn)情況的調(diào)度問題，但同時增加了機器分配問題，擴大了可行域空間，是更復雜的NP-Hard問題。文獻[1]將FJSP分為部分柔性和全部柔性，部分柔性指每道工序僅可以在給定的機器集合加工，全部柔性指每道工序可以在所有機器上加工。通常，將FJSP的求解分為兩個子問題：機器分配和加工順序。對此，大多數(shù)文獻對兩個子問題分別進行編碼，即采用兩級編碼方式。對于機器分配問題，目前主要有兩類編碼方式[2]，第一類是根據(jù)基于操作的編碼的對應(yīng)編碼，第二類是按工件進行編碼；對于加工順序問題，通常采用基于操作的編碼。對于機器編碼，除隨機編碼外，相關(guān)研究還提出一系列編碼策略[3-4]，比如平衡機器負荷、全局最小加工時間、局部最小加工時間。同機器編碼一樣，對于基于操作的編碼，除隨機編碼外，相關(guān)研究也提出了一系列編碼策略[3]，比如剩余加工時間最多、剩余工序數(shù)量最多、最短加工時間。對于兩個子問題的編碼方式，文獻[5]還采用了基于知識的編碼?；趦杉壘幋a方式，解碼方式一般分為半主動解碼和主動解碼。半主動解碼方式簡單并直接產(chǎn)生一個可行調(diào)度方案，為大多數(shù)研究采用的解碼方式。主動解碼比半主動解碼復雜，文獻[6]提出一種主動解碼方式，方法為在解碼工序加工所選擇的機器上找到一個介于解碼工序前序工序的加工完成時刻與機器上的最大完成時間之間的相鄰工序時間間隔大于解碼工序加工時長的時間間隔，則將解碼工序的加工開始時刻移至相鄰工序中的左端工序的加工完成時間后。文獻[6]的解碼算法未考慮解碼工序前序工序的加工完成時刻與時間間隔的開始、結(jié)束時刻之間的關(guān)系，因此該解碼算法不能充分利用機器上的空閑時間，比如存在這樣一個時間間隔，其開始時刻小于解碼工序前序工序的加工完成時刻，但解碼工序前序工序的加工完成時刻與時間間隔的結(jié)束時刻之間的時間間隔大于等于解碼工序的加工時長，則也可以將解碼工序插入其前序工序的加工完成時刻之后，進而更充分利用機器上的空閑時間。

對于NP-Hard類問題的求解，比如0/1背包問題、路徑規(guī)劃問題、旅行商問題、作業(yè)車間調(diào)度問題、柔性作業(yè)車間調(diào)度問題。多數(shù)研究均采用近似優(yōu)化算法，如遺傳算法[3-4，6-13]、蟻群優(yōu)化[5]、粒子群優(yōu)化[14]、灰狼優(yōu)化算法[15]。其中遺傳算法(Genetic algorithm，GA)具有魯棒性好、全局尋優(yōu)能力強等特點，在眾多領(lǐng)域得到廣泛應(yīng)用。比如，文獻[7]應(yīng)用遺傳算法求解了數(shù)值優(yōu)化問題；文獻[8]基于遺傳算法求解了物流配送車輛路徑問題，提出了一種貪婪自適應(yīng)隨機算法改進遺傳算法的鄰域搜索能力；文獻[9]提出一種改進遺傳算法求解了旅行商問題，簡化了遺傳算法；文獻[10]基于遺傳算法求解0/1背包問題，提出了一種二重結(jié)構(gòu)編碼，結(jié)合“貪心法”提高了遺傳算法的搜索效率；文獻[11]應(yīng)用遺傳算法求解無人機航跡規(guī)劃問題，引入差分進化變異策略增加變異的多樣性，結(jié)合模擬退火算法提高全局搜索能力。

也有大量研究將遺傳算法應(yīng)用于柔性作業(yè)車間調(diào)度問題。比如，文獻[4]提出一種改進的遺傳算法，采用了兩級編碼方式，機器編碼采用第一類機器編碼，并采取了不同的編碼策略，根據(jù)機器編碼和結(jié)合最早允許加工時刻再生成基于操作的編碼，以保證生成的調(diào)度為主動調(diào)度，提高了求解效率；文獻[12]結(jié)合年齡分層人口結(jié)構(gòu)(Age-Layered Population Structure，ALPS)和遺傳算法，并應(yīng)用了自適應(yīng)概率，提高了遺傳算法的全局搜索能力；文獻[13]提出了一種改進遺傳退火算法，也采用兩級編碼方式，機器編碼采用第二類機器編碼，遺傳操作中采用自適應(yīng)交叉變異算子，同樣提高了遺傳算法的全局搜索能力。

本文以最小化最大完工時間為目標研究FJSP，編碼方式為僅采用基于操作的編碼，并提出一種解碼算法。在解碼算法過程中以最早完成時刻為規(guī)則選擇工序的加工機器以可能達到優(yōu)化目標，并充分利用機器上的空閑時間。與兩級編碼方式不同，遺傳操作僅需對基于操作的編碼進行，得到了極大的簡化。

2 問題描述

柔性作業(yè)車間調(diào)度問題可描述為有n工件m機器，每個工件有ni道工序，每道工序有一個加工機器集合，安排工序的加工機器及每臺機器上工件的加工順序，以實現(xiàn)某個優(yōu)化指標。

假設(shè)不同工件的工序之間沒有順序約束；同一時刻，一臺機器只能加工一個工件；工件加工不允許搶占；所有工件在0時刻釋放；所有機器在0時刻可用。

以4工件3機器，各工件的工序數(shù)量2～3為例，一個部分FJSP的例子如表1，其中，“-”表示工序不能在對應(yīng)機器上加工。

表1 一個部分FJSP的例子

本文以最小化最大完工時間為優(yōu)化指標，即最小化Makespan。

3 改進遺傳算法

采用遺傳算法進行求解柔性作業(yè)車間調(diào)度問題，改進了染色體編碼方式，研究了一種解碼算法。

3.1 編碼與解碼

與兩級編碼方式不同，對染色體編碼僅采用基于操作的編碼，每個工件i出現(xiàn)ni次。比如，以表1的數(shù)據(jù)為例，一條染色體的編碼為[4，3，2，1，4，3，2，4，1，2]。

基于編碼方式，提出一種解碼算法。在解碼過程中以最早完成時刻為規(guī)則選擇工序的加工機器以可能達到優(yōu)化目標，若存在多臺機器具備相同的最早完成時刻，則采取隨機策略。采用空閑時間段的開始時刻和空閑時長來記錄每臺機器上的空閑時間段，將滿足空閑時間插入的條件分為兩類：(一)機器上的空閑開始時刻大于等于當前解碼工序的前序工序完成時刻(若不存在，則設(shè)置為0)，且空閑時長大于當前解碼工序在對應(yīng)機器上的加工時長。與文獻[6]相似，區(qū)別在于未限制機器；(二)機器上的空閑開始時刻小于當前解碼工序的前序工序完成時刻(若不存在，則設(shè)置為0)，且前序工序完成時刻至當前解碼工序?qū)?yīng)機器的空閑結(jié)束時刻之間的時間間隔大于當前解碼工序在對應(yīng)機器上的加工時長。一個滿足兩類空閑時間插入條件的例子如圖1。從圖1中可看出，機器上的空閑時間能得到充分利用。

圖1 一個滿足兩類空閑時間插入條件的例子

以表1的一個部分FJSP數(shù)據(jù)為例，染色體編碼以[4，3，2，1，4，3，2，4，1，2]為例，進行解碼，得到圖2的調(diào)度結(jié)果。

圖2 一個解碼算法的調(diào)度結(jié)果

對應(yīng)的主要解碼過程如表2。

表2 一個解碼算法的主要過程

3.2 遺傳操作

遺傳操作中，選擇操作基于精英策略的輪盤賭選，變異操作采用兩點交換變異。在JSP、FJSP中，POX是最常用的交叉操作，文獻[16]分析指出POX交叉在迭代初期具有較快的收斂速度，但在迭代后期種群中的個體會變得相似的缺點，并采用了錯位操作。采用改進的POX。與POX不同，改進的POX選擇的是一系列離散的工序集合，且最大工序集合選擇數(shù)量在編碼長度的20%～50%之間，提高了交叉的靈活性，其步驟如下：

步驟一：從父代中隨機選擇相同的工序集合；

步驟二：保持工序集合在父代中的位置不變，按順序交換剩余工序集合。

交叉操作的一個例子如圖3，其中選擇的工序集合為{O4，2，O2，1，O3，2，O1，2}。

圖3 改進POX交叉操作的例子

終止條件為達到最大滯留代數(shù)或達到算例的現(xiàn)有下界值。

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

為驗證改進遺傳算法(Improvedgeneticalgorithm，IGA)的可行性和有效性，采用BRData基準算例進行實驗，對每個算例獨立運行10次。并與文獻[14]所提的DPSO(2018年)、文獻[15]所提的HGWO(2018年)、文獻[17]所提的Heuristic(2014年)以及文獻[12]所提的ALPS-GA(2019年)的最優(yōu)Makespan進行對比。算法采用Python3編程。運行環(huán)境為Windows10系統(tǒng)，AMDE1-7010處理器，4GRAM。遺傳算法參數(shù)設(shè)置：種群規(guī)模200，交叉概率0.85，變異概率0.05，最大迭代次數(shù)150，最大滯留代數(shù)100。

仿真結(jié)果及對比如表3。其中LB代表算例的現(xiàn)有下界值，Best表示算法的最優(yōu)Makespan。RPD表示IGA的Best與其它文獻所提算法的Best的相對百分比偏差，計算公式為RPD=100×(比較算法的Best-IGA的Best)/比較算法的Best。S.D.列的值表示運行10次，改進遺傳算法得到最優(yōu)解的標準差。

表3 實驗結(jié)果及對比

從表3可以看出，IGA在5個算例上優(yōu)于DPSO，在7個算例上優(yōu)于HGWO，在9個算例上優(yōu)于Heuristic及在9個算例上優(yōu)于ALPS-GA；IGA的最優(yōu)解與DPSO、HDWO、Heuristic以及ALPS-GA的相對百分比偏差如圖4，從中可以看出相對百分比偏差的值多數(shù)為正值、平均相對百分比偏差均為正值且較大，表明與DPSO、HDWO、Heuristic以及ALPS-GA相比，IGA在解的質(zhì)量上具有較大優(yōu)勢。

圖4 相對百分比偏差

各算例結(jié)果的箱形圖如圖5，用*標記改進POX的仿真結(jié)果，與POX進行比較。從中可以看出，改進POX的仿真結(jié)果中mk1～3、mk6～9的解較為集中；mk4～5、mk10的波動程度較小，且其表3中對應(yīng)的S.D.值均較?。慌cPOX相比，mk1～mk2、mk6～mk7、mk9的解更集中、平均值更優(yōu)，mk4～mk5、mk10的平均值更優(yōu)，表明與POX相比，IGA具有更好的求解效率和穩(wěn)定性。

圖5 各算例結(jié)果的箱形圖

以上分析表明改進遺傳算法在編碼方式與解碼算法上是正確的、可行的和有效的，且具有較高的求解效率和較好的穩(wěn)定性。

求解mk1、mk2的一個最優(yōu)調(diào)度甘特圖分別如圖6、7。

圖6 求解mk1的一個最優(yōu)調(diào)度甘特圖

5 結(jié)束語與展望

以最小化最大完工時間為目標研究了柔性作業(yè)車間調(diào)度問題，僅采用了基于操作的編碼，極大簡化了遺傳操作，并提出了一種解碼算法。采用標準算例進行了實驗，通過對比驗證了改進遺傳算法在編碼方式與解碼算法上的正確性、可行性和有效性，且具有較高的求解效率?？紤]企業(yè)生產(chǎn)的實際需求，對于柔性作業(yè)車間調(diào)度問題的研究，通常包含多個目標，比如交貨期、加工成本、人力成本等。因此，在今后的研究中，可以研究多目標FJSP的求解，且考慮啟發(fā)式編碼和在解碼過程中實施不同的規(guī)則以可能實現(xiàn)多目標優(yōu)化。

圖7 求解mk2的一個最優(yōu)調(diào)度甘特圖