陳宇軒

(合肥工業(yè)大學(xué)機(jī)械工程學(xué)院，合肥 230009)

工時(shí)不確定條件下基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度問題的區(qū)間數(shù)求解方法

陳宇軒

(合肥工業(yè)大學(xué)機(jī)械工程學(xué)院，合肥 230009)

以不確定工序加工時(shí)間為切入點(diǎn)，使用區(qū)間數(shù)表征不確定工序加工時(shí)間，研究了基于不確定工時(shí)的單目標(biāo)柔性作業(yè)車間調(diào)度問題，并設(shè)計(jì)了基于區(qū)間數(shù)理論的改進(jìn)遺傳算法對(duì)該問題進(jìn)行求解。

不確定工序加工時(shí)間；區(qū)間數(shù)；改進(jìn)遺傳算法；柔性作業(yè)車間調(diào)度

0 引言

實(shí)際生產(chǎn)過程中，存在著大量的不確定因素，大多數(shù)不確定因素的隨機(jī)波動(dòng)都直接反映到工序加工時(shí)間的變化上[1]。然而以往文獻(xiàn)為了簡(jiǎn)化問題難度常常假定工序具有確定的加工時(shí)間，這樣做的后果是得出的調(diào)度方案嚴(yán)重偏離了實(shí)際生產(chǎn)情況[2-3]。因此，本文以不確定工序加工時(shí)間為切入點(diǎn)，研究不確定工時(shí)的車間調(diào)度問題。從目前國內(nèi)外文獻(xiàn)可以了解到，工序加工時(shí)間的描述方法基本可以分為三類：1）模糊數(shù)理論。以Zadeh提出模糊集理論[4]為核心，衍生出的一系列模糊方法，主要研究與處理問題的模糊性以及決策上的不確定性。2）隨機(jī)數(shù)理論[5-6]。以大量實(shí)際數(shù)據(jù)為研究依據(jù)，歸納出研究對(duì)象服從的分布，并根據(jù)分布進(jìn)行求解。3）區(qū)間數(shù)理論[7]。用區(qū)間數(shù)描述工序加工時(shí)間的分布區(qū)間，再根據(jù)區(qū)間數(shù)

的比較規(guī)則進(jìn)行求解。隨機(jī)數(shù)和模糊數(shù)都需要事先得知生產(chǎn)數(shù)據(jù)服從的分布。但在車間實(shí)際生產(chǎn)中，獲得工序加工時(shí)間的分布受到統(tǒng)計(jì)等技術(shù)條件的影響相對(duì)比較困難，而工序加工時(shí)間往往都存在一個(gè)上限和下限，因此本文使用區(qū)間數(shù)理論表征不確定工時(shí)[8]。

1 區(qū)間數(shù)理論及問題模型

1.1 區(qū)間數(shù)理論概述

通常情況下人們對(duì)事物的判斷往往不會(huì)是一個(gè)定量的值，而是一個(gè)在特定范圍內(nèi)的變量。這種在特定范圍內(nèi)的變量，我們稱之為區(qū)間數(shù)。區(qū)間數(shù)的數(shù)學(xué)定義如下：

定義1.1：設(shè)R為實(shí)數(shù)域，［a］=［a-,a+］，稱a為區(qū)間數(shù)。

區(qū)間數(shù)之間的比較規(guī)則比較特殊[8]：設(shè)［a］、［b］為兩個(gè)區(qū)間數(shù)，則有：

1.2 問題模型

該問題數(shù)學(xué)模型可以表示為：

下面對(duì)上述約束條件進(jìn)行介紹：Cj表示工件j的加工完成時(shí)間，Sij,k表示工件Ji的第j道工序在第k臺(tái)設(shè)備上的開始加工時(shí)間；Pijk表示工件Ji的第j道工序在第k臺(tái)設(shè)備上的加工時(shí)間；ni表示工件Ji的工序數(shù)，Q表示無窮大的整數(shù)，xijk表示工件決策變量，可以從{0,1}中取值，表示工件Ji的第j道工序是否在加工機(jī)器Mk上加工；yihk表示機(jī)器決策變量，可以從{0,1}中取值，表示同一個(gè)機(jī)器上不同工序的先后加工順序；式（3）表示同一工件的工序之間存在順序約束；式（5）和式（6）表示機(jī)器只能同時(shí)加工一個(gè)工件。值得一提的是本文涉及工序加工時(shí)間的內(nèi)容，均使用區(qū)間數(shù)進(jìn)行表征。

2 算法設(shè)計(jì)

本文針對(duì)柔性作業(yè)車間調(diào)度問題設(shè)計(jì)了改進(jìn)遺傳算法進(jìn)行計(jì)算[9]：使用雙層編碼及解碼方式進(jìn)行操作，并設(shè)計(jì)了隨機(jī)初始化種群方法和基于區(qū)間數(shù)的選優(yōu)方法相結(jié)合的初始種群方法，同時(shí)設(shè)計(jì)了基于區(qū)間數(shù)的最佳個(gè)體保存法的選擇方法，并采用了基于POX[10]方法和多點(diǎn)交叉法[11]的交叉操作以及平移變異[12]和兩點(diǎn)變異[13]的編譯方法。

2.1 編碼與解碼

根據(jù)柔性作業(yè)車間調(diào)度問題的特性，本文按照工序碼和機(jī)器碼的雙層編碼和解碼方式進(jìn)行介紹[14]。

1）工序碼。包含多個(gè)基因，基因中的數(shù)字代表工件號(hào)，該數(shù)字出現(xiàn)的次數(shù)表示工序號(hào)。也就是說第j次出現(xiàn)的工件序號(hào)i表示工件Ji的第j道工序，即Oij。

2）機(jī)器碼。包含若干片段，片段按照工件序號(hào)排序，同時(shí)每個(gè)片段又包含多個(gè)基因，基因中的數(shù)字表示該道工序分配到那一臺(tái)機(jī)器，如在某個(gè)機(jī)器碼中，第3個(gè)片段的第2個(gè)基因中數(shù)字為4，表示工件J3的Q32在加工機(jī)器M4上加工。

2.2 改進(jìn)初始種群方法

我們提出隨機(jī)初始化種群方法和基于區(qū)間數(shù)的選擇方法綜合判定。具體思路如下：1）為種群中的所有個(gè)體隨機(jī)產(chǎn)生的0～1之間隨機(jī)值；2）若隨機(jī)數(shù)大于0.8，則個(gè)體采用隨機(jī)方式生成，反之，則個(gè)體采用基于區(qū)間數(shù)的選擇方法生成?；趨^(qū)間數(shù)的選擇方法的核心思想是按照工件完工時(shí)間最短的原則選擇加工機(jī)器。具體來說是將所有工件的全部工序的加工時(shí)間根據(jù)式（1）區(qū)間數(shù)比較規(guī)則進(jìn)行排序，用時(shí)最少的優(yōu)先配置機(jī)器，循環(huán)上述過程直到全部工序分配到機(jī)器。

2.3 改進(jìn)選擇操作

本文采用基于區(qū)間數(shù)最佳個(gè)體保存選擇的方法進(jìn)行選擇操作。對(duì)于基于區(qū)間數(shù)最佳個(gè)體保存法其過程為：1）使用區(qū)間可能度的比較規(guī)則將工序時(shí)間進(jìn)行排序，將用時(shí)最短的父代種群中的個(gè)體直接復(fù)制到下一代中。2）當(dāng)一個(gè)選擇完成后，將被選擇的個(gè)體重新放回種群。并且被選擇的個(gè)體仍可作為一個(gè)父染色體繼續(xù)參與選擇。使用該方法的主要目的是該方法可以使得選擇出的所有個(gè)體不會(huì)被交叉和變異操作破壞，從而可以提高實(shí)例模擬收斂可靠性。

2.4 基于POX法多點(diǎn)交叉法的交叉操作

本文針對(duì)工序碼采用POX交叉[10]算子，針對(duì)機(jī)器碼采用多點(diǎn)交叉[11]的方法。

2.5 基于平移變異和兩點(diǎn)變異的變異操作

本文針對(duì)工時(shí)不確定條件下的柔性作業(yè)車間調(diào)度問題中工序排序和設(shè)備分配的不同需求，對(duì)工序編碼采用平移變異[12]；對(duì)機(jī)器分配編碼采用兩點(diǎn)變異[13]方法。

2.6 算法流程

步驟1：首先設(shè)置算法相關(guān)參數(shù)，具體包括種群規(guī)模、算法最大迭代代數(shù)、交叉概率、變異概率等[15]。步驟2：采用隨機(jī)方法和基于區(qū)間數(shù)的選擇方法相結(jié)合的初始種群方法產(chǎn)生N個(gè)個(gè)體組成一個(gè)初始種群，并令其規(guī)模為P。步驟3：使用POX交叉對(duì)父代種群進(jìn)行操作，其中當(dāng)t=0時(shí)，Pt表示初始種群。步驟4：對(duì)個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)。步驟5：采用基于區(qū)間數(shù)的最佳個(gè)體保存法進(jìn)行選擇操作。步驟6：工序碼和機(jī)器碼分別使用平移變異和兩點(diǎn)變異，產(chǎn)生子代種群Ct。步驟7：產(chǎn)生下一代種群并返回到步驟4。

3 實(shí)例驗(yàn)證

本文以3×5FJSP問題作為樣本，數(shù)據(jù)如表1，并設(shè)計(jì)了原型系統(tǒng)根據(jù)上文設(shè)計(jì)的改進(jìn)遺傳算法進(jìn)行計(jì)算。

表1 原始數(shù)據(jù)

圖1為原型系統(tǒng)主界面，對(duì)于單目標(biāo)問題進(jìn)行目標(biāo)選擇，針對(duì)本文研究?jī)?nèi)容勾選最大完工時(shí)間最小，然后點(diǎn)擊【問題導(dǎo)入】插入計(jì)算基礎(chǔ)數(shù)據(jù)，然后點(diǎn)擊【參數(shù)設(shè)置】。

圖2為參數(shù)設(shè)置界面，選擇種群規(guī)模、變異概率、交叉概率、選擇概率和最大進(jìn)化代數(shù)。

最后點(diǎn)擊計(jì)算，這里我們進(jìn)行10次運(yùn)算求得最優(yōu)解，具體數(shù)據(jù)如表2所示。

4 結(jié)語

圖1 原型系統(tǒng)主界面

圖2 參數(shù)設(shè)置

文中針對(duì)不確定工序加工時(shí)間的柔性作業(yè)車間調(diào)度問題，使用區(qū)間數(shù)理論對(duì)傳統(tǒng)遺傳算法進(jìn)行改造。首先使用雙層編碼及解碼方式進(jìn)行編碼和解碼操作，并設(shè)計(jì)了隨機(jī)初始化種群方法和基于區(qū)間數(shù)的選優(yōu)方法相結(jié)合的初始種群方法，同時(shí)設(shè)計(jì)了基于區(qū)間數(shù)的最佳個(gè)體保存法的選擇方法，并采用了基于POX方法和多點(diǎn)交叉法的交叉操作以及平移變異和兩點(diǎn)變異的編譯方法。最后開發(fā)了調(diào)度模型系統(tǒng)，計(jì)算求得了調(diào)度問題最優(yōu)解。

圖3 計(jì)算結(jié)果

表2 運(yùn)行結(jié)果

[1] 王凌.車間調(diào)度及其遺傳算法[M].北京:清華大學(xué)出版社,2003.

[2] 何霆,劉飛,馬玉林.車間生產(chǎn)調(diào)度問題研究[J].機(jī)械工程學(xué)報(bào),2000,36(5):97-102.

[3] 李懷祖.生產(chǎn)計(jì)劃與控制[M].北京:中國科技出版社,2010.

[4] ZADEH L A.Fuzzy Sets[J].Information and Control,1965,8(3):338-353.

[5] 彭建剛,劉明周,張璽,等.工序加工時(shí)間不確定的柔性制造車間重調(diào)度算法[J].中國機(jī)械工程,2014,25(17):2320-2326.

[6] 賈春福.加工時(shí)間服從指數(shù)分布單機(jī)隨機(jī)調(diào)度[J].系統(tǒng)工程,2002,20(6):58-61.

[7] SAKAWA M,Mori T.An efficient genetic algorithm for jobshop scheduling problems with fuzzy processing time and fuzzy duedate[J].Computers&Industrial Engineering,1999,36(2):325-341.

[8] 楊宏安,王周鋒,呂陽陽,等.工序加工時(shí)間不確定條件下作業(yè)車間調(diào)度問題的區(qū)間數(shù)求解方法[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(9):2231-2240.

[9] 袁波,應(yīng)保勝,謝皓.基于遺傳算法的不確定條件下作業(yè)車間調(diào)度[J].現(xiàn)代制造工程,2012(10):52-56.

[10]張超勇,饒運(yùn)清,李培根.基于POX交叉的遺傳算法求解Job-Shop調(diào)度問題[J].中國機(jī)械工程,2004,15(23):2149-2153.

[11]張超勇,饒運(yùn)清,李培根,等.柔性作業(yè)車間調(diào)度問題的兩級(jí)遺傳算法[J].機(jī)械工程學(xué)報(bào),2007,43(4):119-124.

[12]葛繼科,邱玉輝,吳春明,等.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2008,25(10):2911-2916.

[13]席裕庚,柴天佑,惲為民.遺傳算法綜述[J].控制理論與應(yīng)用,1996(6):697-708.

[14]劉壯.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度[J].機(jī)械工程師,2016(10):43-45.

[15]劉捷.不確定條件下基于遺傳算法的柔性作業(yè)車間調(diào)度問題研究[D].武漢:華中科技大學(xué),2009.

Solution about the Interval Number of Flexible Job Shop Scheduling Problem Based on Improved Genetic Algorithm under Uncertain Time

CHEN Yuxuan
(School ofMechanical Engineering,Hefei UniversityofTechnology,Hefei 230009,China)

In this paper,the processing time of indefinite process is characterized by interval number,and the singleobjective flexible job-shop scheduling problem based on uncertain processing time is studied.The improved genetic algorithm based on interval number theory is designed.The problem is solved.

uncertain process processing time;interval number;improved genetic algorithm;flexible job shop scheduling

TH 186

A

1002－2333（2018）01－0074－03

（編輯黃 荻）

陳宇軒(1992—)，男，碩士研究生，主要從事制造過程監(jiān)測(cè)與控制研究。

2017-04-01