基于圍道矩陣的遺傳算法求解柔性作業(yè)車間調(diào)度問題研究

崔晨浩 任工昌

摘? 要：在經(jīng)濟(jì)全球化的時(shí)代，我國制造業(yè)面臨著巨大的商機(jī)和激烈的市場競爭，企業(yè)在滿足客戶個(gè)性化需求的同時(shí)需要具備快速響應(yīng)市場的能力，所以研究柔性作業(yè)車間調(diào)度問題（FJSP）成為解決這些問題的一個(gè)重要方向。在這樣的背景下，本文提出一種利用多色集合理論中的圍道矩陣，改進(jìn)傳統(tǒng)遺傳算法，對FJSP問題中完工時(shí)間這一指標(biāo)進(jìn)行優(yōu)化。

關(guān)鍵詞：遺傳算法;圍道矩陣;完工時(shí)間;車間調(diào)度

中圖分類號：TH164;TP18? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：2096-4706（2019）24-0153-05

Abstract：In the era of economic globalization，China’s manufacturing industry is facing huge business opportunities and fierce market competition. Enterprises need to have the ability to respond to the market quickly while meeting the personalized needs of customers，so the study of flexible job shop scheduling （FJSP） has become an important direction to solve these problems. Under this background，this paper proposes a new method to optimize the completion time of FJSP by using the contour matrix of polychromatic set theory and improving the traditional genetic algorithm.

Keywords：genetic algorithm;enclosure matrix;completion time;workshop scheduling

0? 引? 言

制造業(yè)是社會(huì)經(jīng)濟(jì)的重要支柱之一。當(dāng)下，中國制造企業(yè)的工藝過程與調(diào)度較多地依賴于人工經(jīng)驗(yàn)，由于目前大多數(shù)制造企業(yè)的工藝過程與調(diào)度不夠先進(jìn)，制定的調(diào)度方案難以使得生產(chǎn)線資源利用最大化，最終影響產(chǎn)品的完工時(shí)間[1]。本文主要研究一類基于多色集合理論的工藝過程與調(diào)度集成的優(yōu)化建模方法，以優(yōu)化產(chǎn)品完工時(shí)間為目標(biāo)，以此解決柔性作業(yè)車間調(diào)度問題。旨在降低生產(chǎn)成本，提高生產(chǎn)效率，從而提高企業(yè)的競爭力。

1? 多色集合中的圍道矩陣

1.1? 多色集合理論

多色集合理論是一種新型的信息處理工具和系統(tǒng)理論，它的核心思想是使用形式相同的數(shù)學(xué)模型來仿真不同的對象（產(chǎn)品、設(shè)計(jì)過程、工藝過程和生產(chǎn)系統(tǒng)等等），來描述元素之間的層次結(jié)構(gòu)與復(fù)雜關(guān)系，重點(diǎn)是在集合層和邏輯層組織與處理信息，再在數(shù)量層解決低層數(shù)量大小及數(shù)學(xué)計(jì)算問題。因此，多色集合理論在問題的形式化研究方向具有明顯的優(yōu)勢，被廣泛應(yīng)用于產(chǎn)品的概念設(shè)計(jì)建模、零件制造工藝建模、產(chǎn)品裝配工藝建模和工作流過程建模等領(lǐng)域[2，3]。

1.2? 圍道布爾矩陣

在對產(chǎn)品、設(shè)計(jì)過程和制造工藝過程進(jìn)行建模時(shí)，集合論的數(shù)學(xué)工具得到了廣泛的應(yīng)用。但傳統(tǒng)的集合論不能描述集合本身以及其元素之間的性質(zhì)，這就限制了其在復(fù)雜系統(tǒng)建模方面的應(yīng)用。使用多色集合來表示性質(zhì)統(tǒng)一的標(biāo)準(zhǔn)數(shù)學(xué)模型來進(jìn)行系統(tǒng)仿真，由于其中系統(tǒng)形式不取決于仿真對象的內(nèi)容，從而使仿真系統(tǒng)更具柔性，也便于編程。基于此，該方向已成為關(guān)于多色集合理論的主流研究方向，多色集合理論使用了“圍道”這一概念來代替純數(shù)學(xué)理論中“顏色”的概念，以便更好地抽象與概括實(shí)際系統(tǒng)中對象的性質(zhì)、屬性、特征與參數(shù)等概念[4]。

2? 柔性作業(yè)車間的調(diào)度問題及其約束

2.1? 柔性作業(yè)車間調(diào)度問題

柔性作業(yè)車間調(diào)度是指生產(chǎn)車間中在m臺(tái)設(shè)備上加工n個(gè)工件，每個(gè)工件包含ni個(gè)事先確定加工順序的工序，每道工序可以在多臺(tái)設(shè)備上加工，每道工序不同的機(jī)器加工時(shí)間有所不同，本文主要考慮完工時(shí)間最短的性能指標(biāo)[5]。

2.2? 車間調(diào)度的應(yīng)用算例及約束條件

本文采用3×6×8的FJSP調(diào)度問題算例（3類工件，對應(yīng)最大工序數(shù)為6，在8臺(tái)設(shè)備上進(jìn)行加工）來實(shí)現(xiàn)求解完工時(shí)間最小這一個(gè)目標(biāo)。加工信息如表1所示。

2.4? 約束條件

當(dāng)工件i的第j道工序和工件e的第g道工序在同一臺(tái)機(jī)床上加工時(shí)，設(shè)：

當(dāng)工件e的第g道工序在機(jī)床k上加工時(shí)，設(shè)：

共有s個(gè)加工順序，要求工件從開始加工到加工完成時(shí)間最短的加工順序，那么要先求某一個(gè)加工順序x，對應(yīng)的工件從開始到結(jié)束加工的時(shí)間，也就是求x中所有工件的總完工時(shí)間，所以Ep=MS。

3? 遺傳算法操作步驟

3.1? 加工信息處理

3.1.1? 染色體單層編碼

在進(jìn)行染色體的具體編碼之前，先進(jìn)行碼位信息的確定，第一種是顯性碼位信息，第二種是隱性碼位信息，是顯性碼位信息的具體化即具體化某種工件的工序碼位。

（1）確定染色體長度。染色體的長度為所有工件的全部工序數(shù)的總和。多件多品種生產(chǎn)方式：有N種工件共S件，第i種工件有Pi道工序。由于是多件多品種，首先得對數(shù)量大于1的多種工件進(jìn)行加工順序排布，寫出顯性碼位信息，然后具體化每種工件的隱性碼位信息即該種工件的具體工序編碼。例：有A、B、C三種工件各1、2、3件。

那么這6件工件的加工順序有很多種，任意選擇一種，寫出顯性碼位信息：

然后根據(jù)工序-設(shè)備布爾矩陣，寫出隱性碼位信息：

采用圍道布爾矩陣進(jìn)行顯性、隱性碼位信息確定，不僅降低了編碼的空間復(fù)雜度（原來需要二層編碼），而且在解決批量生產(chǎn)問題時(shí)，只需要將工件種類作為顯性碼位信息，某種工件的工序加工信息作為隱性碼位信息出現(xiàn)在矩陣中，再根據(jù)染色體的設(shè)備編碼就能較為快速地求解調(diào)度問題。

（2）確定染色體編碼。根據(jù)A、B、C三種工件各1件的隱性碼位信息，可以搜索對應(yīng)工件的工序-設(shè)備圍道布爾矩陣中，搜尋與工件的工序?qū)?yīng)的可使用的設(shè)備信息，產(chǎn)生染色體，即產(chǎn)生每個(gè)工件每道工序的可用設(shè)備編碼。如表3所示只是其中一種編碼方式。

3.1.2? 染色體解碼

根據(jù)染色體編碼，反向搜索工序-設(shè)備圍道矩陣，從而獲得各工序在相應(yīng)設(shè)備上的加工時(shí)間。并在滿足各工件工序約束的基礎(chǔ)上，按照染色體（設(shè)備編碼）對應(yīng)的工序，在每臺(tái)設(shè)備上安排的相應(yīng)工序進(jìn)行加工。

具體過程如下：將每臺(tái)設(shè)備上各工件的第一道工序先進(jìn)行加工，并返回工序-機(jī)床圍道矩陣，獲取其對應(yīng)加工時(shí)間。（設(shè)備上的開始時(shí)間+工序加工時(shí)間=設(shè)備上最早完工時(shí)間=對應(yīng)工件的某道工序的最早完工時(shí)間）按照工序約束與設(shè)備約束的雙重約束，依次確定各設(shè)備上各任務(wù)的開始和完工時(shí)間;當(dāng)確定出每臺(tái)設(shè)備上所有任務(wù)的開始和完工時(shí)間，即可獲得所有任務(wù)的加工方案，也就完成了解碼過程。

3.2? 適應(yīng)度值計(jì)算

在遺傳算法中，一個(gè)個(gè)體能否被遺傳到下一代群體中，評判標(biāo)準(zhǔn)是該個(gè)體的適應(yīng)度值的大小，適應(yīng)度值越大，被遺傳到下一代的概率越高。

設(shè)：fk=Ep=MS，適應(yīng)度函數(shù)fit（k）=1/fk，k：表示第k條顯性染色體

計(jì)算各設(shè)備上各工序的起始加工時(shí)間，完工時(shí)間。設(shè)工序j（j=1，…，P）的起始加工時(shí)間為Sj，完工時(shí)間為Ej，在設(shè)備k上的加工時(shí)間為Tj，那么有Ej=Sj+Tj（Tj已知，Sj未知）。

根據(jù)工序j的編號，搜索對應(yīng)工件的工序-設(shè)備圍道布爾矩陣，確定它是第幾道工序。如果j不是該工件的第一道工序，那么搜索矩陣，確定j的上一道工序j0，得到j(luò)0的完工時(shí)間PreEj0，那么Sj≥PreEj0;如果j是第一道工序，那么Sj≥0。

根據(jù)工序j的編號，確定該工序在哪種設(shè)備上加工（如在設(shè)備k上加工），并確定該種設(shè)備的上道工序的編號。如果工序j是機(jī)床k上的第一道工序，k的起始加工時(shí)間為MSk，那么Sj≥MSk;如果工序j不是機(jī)床k上的第一道工序，k的上道工序的完工時(shí)間PreEk，那么Sj≥PreEk。

綜述Sj取值，Sj=max（上道工序j0的完工時(shí)間，工序j在設(shè)備上的起始時(shí)間）。

3.3? 選擇、交叉、變異操作及結(jié)果

（1）選擇。采用精英保留策略，根據(jù)適應(yīng)度值fit（k）的 結(jié)果，將值最大的fit（k）對應(yīng)的隱性染色體不經(jīng)過后續(xù)的交叉變異，直接選擇進(jìn)入下一代的種群，保證優(yōu)良性狀的傳承。

（2）交叉。根據(jù)交叉概率PC，隨機(jī)選擇兩個(gè)染色體，并根據(jù)設(shè)定的交叉算子交換染色體上的部分基因編碼，形成兩個(gè)新的子代個(gè)體，評估其適應(yīng)度值，選出適應(yīng)度值較高的子代個(gè)體，進(jìn)行后續(xù)操作。

（3）變異。選擇一條隱性染色體，根據(jù)設(shè)置的變異概率PV，產(chǎn)生變異的碼位，接著搜索工件的工序-設(shè)備圍道矩陣，搜尋對應(yīng)碼位的可以代替的設(shè)備編碼，從而產(chǎn)生新的個(gè)體。通過計(jì)算已經(jīng)變異個(gè)體的適應(yīng)度值fit（k′）和fit（k），若fit（k′）≥fit（k）則變異可行，反之變異失敗，該條染色體無須進(jìn)行變異。

（4）結(jié)果。由于計(jì)算結(jié)果較為復(fù)雜，在Matlab中求解后得出加工信息表如表4所示、迭代曲線如圖1所示。

從迭代曲線可以看出，最小完工時(shí)間在迭代26次后趨于平穩(wěn)，是73h，即為單目標(biāo)調(diào)度的最優(yōu)時(shí)間，并可以依據(jù)求解得出的加工信息表畫出調(diào)度甘特圖。如圖2所示。

4? 結(jié)? 論

本文針對當(dāng)下制造業(yè)中的單目標(biāo)柔性作業(yè)車間調(diào)度問題進(jìn)行了研究，構(gòu)建了基于多色集合圍道矩陣的改進(jìn)遺傳算法來解決改善作業(yè)車間完工時(shí)間的問題。改進(jìn)遺傳算法，是在多色集合的集成模型與數(shù)量排列模型的基礎(chǔ)上，建立了柔性作業(yè)車間調(diào)度優(yōu)化組合約束模型。采用此組合約束模型來處理調(diào)度中的工藝約束、設(shè)備約束和時(shí)間約束等，實(shí)現(xiàn)解域的構(gòu)造與維護(hù)，再結(jié)合遺傳算法來優(yōu)化搜索解域。因此，改進(jìn)后的遺傳算法不僅保證了解的有效性，還顯著提高了算法的求解速度。

參考文獻(xiàn)：

[1] 張文生.改進(jìn)的遺傳算法在多目標(biāo)車間調(diào)度中的應(yīng)用研究 [D].大連：大連交通大學(xué)，2010.

[2] 張博，李宗斌.采用多色集合理論的公差信息建模與推理技術(shù) [J].機(jī)械工程學(xué)報(bào)，2005（10）：111-116.

[3] Pavlov VV.Polychromatic sets theory of systems：Structure of PS [J].Information technology，1997（7）：11-16.

[4] 張國輝，高亮，李培根，等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題 [J].機(jī)械工程學(xué)報(bào)，2009，45（7）：145-151.

[5] 張超勇，劉瓊，邱浩波，等.考慮加工成本和時(shí)間的柔性作業(yè)車間調(diào)度問題研究 [J].機(jī)械科學(xué)與技術(shù)，2009（8）：1005-1011.

作者簡介：崔晨浩（1993-），男，漢族，河南鄭州人，碩士，研究方向：為制造系統(tǒng)資源調(diào)度的優(yōu)化;任工昌（1962-），男，漢族，陜西西安人，教授，博士生導(dǎo)師，研究方向：產(chǎn)品創(chuàng)新理論、機(jī)電設(shè)備狀態(tài)監(jiān)控。