工時不確定條件下基于改進遺傳算法的柔性作業車間調度問題的區間數求解方法

陳宇軒

(合肥工業大學機械工程學院，合肥 230009)

工時不確定條件下基于改進遺傳算法的柔性作業車間調度問題的區間數求解方法

陳宇軒

(合肥工業大學機械工程學院，合肥 230009)

以不確定工序加工時間為切入點，使用區間數表征不確定工序加工時間，研究了基于不確定工時的單目標柔性作業車間調度問題，并設計了基于區間數理論的改進遺傳算法對該問題進行求解。

不確定工序加工時間；區間數；改進遺傳算法；柔性作業車間調度

0 引言

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

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

1 區間數理論及問題模型

1.1 區間數理論概述

通常情況下人們對事物的判斷往往不會是一個定量的值，而是一個在特定范圍內的變量。這種在特定范圍內的變量，我們稱之為區間數。區間數的數學定義如下：

定義1.1：設R為實數域，［a］=［a-,a+］，稱a為區間數。

區間數之間的比較規則比較特殊[8]：設［a］、［b］為兩個區間數，則有：

1.2 問題模型

該問題數學模型可以表示為：

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

2 算法設計

本文針對柔性作業車間調度問題設計了改進遺傳算法進行計算[9]：使用雙層編碼及解碼方式進行操作，并設計了隨機初始化種群方法和基于區間數的選優方法相結合的初始種群方法，同時設計了基于區間數的最佳個體保存法的選擇方法，并采用了基于POX[10]方法和多點交叉法[11]的交叉操作以及平移變異[12]和兩點變異[13]的編譯方法。

2.1 編碼與解碼

根據柔性作業車間調度問題的特性，本文按照工序碼和機器碼的雙層編碼和解碼方式進行介紹[14]。

1）工序碼。包含多個基因，基因中的數字代表工件號，該數字出現的次數表示工序號。也就是說第j次出現的工件序號i表示工件Ji的第j道工序，即Oij。

2）機器碼。包含若干片段，片段按照工件序號排序，同時每個片段又包含多個基因，基因中的數字表示該道工序分配到那一臺機器，如在某個機器碼中，第3個片段的第2個基因中數字為4，表示工件J3的Q32在加工機器M4上加工。

2.2 改進初始種群方法

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

2.3 改進選擇操作

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

2.4 基于POX法多點交叉法的交叉操作

本文針對工序碼采用POX交叉[10]算子，針對機器碼采用多點交叉[11]的方法。

2.5 基于平移變異和兩點變異的變異操作

本文針對工時不確定條件下的柔性作業車間調度問題中工序排序和設備分配的不同需求，對工序編碼采用平移變異[12]；對機器分配編碼采用兩點變異[13]方法。

2.6 算法流程

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

3 實例驗證

本文以3×5FJSP問題作為樣本，數據如表1，并設計了原型系統根據上文設計的改進遺傳算法進行計算。

表1 原始數據

圖1為原型系統主界面，對于單目標問題進行目標選擇，針對本文研究內容勾選最大完工時間最小，然后點擊【問題導入】插入計算基礎數據，然后點擊【參數設置】。

圖2為參數設置界面，選擇種群規模、變異概率、交叉概率、選擇概率和最大進化代數。

最后點擊計算，這里我們進行10次運算求得最優解，具體數據如表2所示。

4 結語

圖1 原型系統主界面

圖2 參數設置

文中針對不確定工序加工時間的柔性作業車間調度問題，使用區間數理論對傳統遺傳算法進行改造。首先使用雙層編碼及解碼方式進行編碼和解碼操作，并設計了隨機初始化種群方法和基于區間數的選優方法相結合的初始種群方法，同時設計了基于區間數的最佳個體保存法的選擇方法，并采用了基于POX方法和多點交叉法的交叉操作以及平移變異和兩點變異的編譯方法。最后開發了調度模型系統，計算求得了調度問題最優解。

圖3 計算結果

表2 運行結果

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

[2] 何霆,劉飛,馬玉林.車間生產調度問題研究[J].機械工程學報,2000,36(5):97-102.

[3] 李懷祖.生產計劃與控制[M].北京:中國科技出版社,2010.

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

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

[6] 賈春福.加工時間服從指數分布單機隨機調度[J].系統工程,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] 楊宏安,王周鋒,呂陽陽,等.工序加工時間不確定條件下作業車間調度問題的區間數求解方法[J].計算機集成制造系統,2014,20(9):2231-2240.

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

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

[11]張超勇,饒運清,李培根,等.柔性作業車間調度問題的兩級遺傳算法[J].機械工程學報,2007,43(4):119-124.

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

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

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

[15]劉捷.不確定條件下基于遺傳算法的柔性作業車間調度問題研究[D].武漢:華中科技大學,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—)，男，碩士研究生，主要從事制造過程監測與控制研究。

2017-04-01