基于遺傳算法求解生產調度問題的探討

陳 龍

（上海交通大學，上海 200240）

基于遺傳算法求解生產調度問題的探討

陳 龍

（上海交通大學，上海 200240）

為了適應日益嚴苛的空間裝備的要求及高速提升的裝備需求，多品種、小批量、高柔性的生產模式，已經逐漸成為我國空間制冷產品研制與生產的主流模式。此外，由于生產規模的迅速擴大以及綜合性與復雜程度的不斷提高，管理和過程監控提的要求更高更嚴。

遺傳算法 生產調度 制冷產品

如何根據制冷器產品生產的需求，準確快速地進行決策并組織生產；如何在生產計劃改變的情況下，確保質量的同時又對過程進行控制，以便更大限度地發揮生產系統的柔性；如何在現有生產工藝盡可能不改變的前提下，有效地管理、決策、調度制冷產品的生產，并產生最大的綜合效益。

通過了解空間制冷產品生產線的基本流程、工藝要求及其他特性，可以把這一類生產車間的調度問題簡化為較為典型的流水車間調度問題。流水車間調度問題（Flow-Shop Seheduling Program，簡稱FSSP）是車間調度中一個常見且重要的論題，在離散制造工業及流程工業中應用較為廣泛，具有一定的代表意義。本文將首次運用遺傳算法探討求解空間制冷產品生產調度問題。

1 運用遺傳算法求解生產調度問題

本課題以某研究所航天制冷產品制作部為平臺，基于遺傳算法，以空間制冷產品為例，對具有品種多、批量小等特點的航天器元部件的生產調度問題進行研究。

對該制作平臺而言，現有的簡單、局部和常規的生產計劃，或僅憑經驗的管理模式和現場調度已經不能滿足現有的生產要求。此外，生產安排很少考慮實際生產負荷、生產效率、成本等因素，這也將大大影響未來空間裝備研制的發展。因此，如何縮短生產周期、優化生產工序、保證交付節點，是該制作平臺的難題之一。

1.1 空間制冷產品生產調度問題的數學描述

空間制冷產品生產調度問題描述為：n類產品在多個工段內制作加工，每個工段完成多道工序，每類產品都會以相同加工順序在工段間流轉，每類產品都需要經過m道工序。產品在各道工序的制作加工時間都是確定的，可將其設為tij(i=1...n;j=1...m)，表示第i類產品在第j道工序上的制作加工時間。探討調度問題的目標是確定n類產品的最優加工順序，從而使完成所有產品制作加工的最大流程時間達到最小。

令c(ji,k)表示產品ji在工序k上的制作加工完成時間，(j1,j2,…,jn)表示產品的調度順序，則n類產品、m道工序的流水車間調度的流程時間可表示為：

(i=2...n;k =2...m)

這里，最大流程時間為cmax=c(jn,m)。探討調度問題的目標是確定產品調度順序(j1,j2,…,jn)，從而使最大流程時間cmax最小。

1.2 編碼方式

采用十進制的編碼方式，用染色體表示產品的制作加工順序，而產品的種類表示染色體的長度。如果流水車間調度問題中有5類產品，并假設這些產品的加工順序確定為{j2,j3,j1,j5,j4}，那么可以將其編碼為νi={2,3,1,5,4}。

1.3 初始種群

采用NEH算法與隨機法共同產生初始種群。這樣既可以保證初始種群具有一定的質量，又能保證繁衍出種群的多樣性。不僅可以減少非優質解產生的概率，也可以盡可能在整個問題空間里面縮小最優解在其中的分布范圍，從而得出較為滿意和優質的結果。

設定初始種群的產生時，初代種群中一半規模將采用NEH算法來產生，即先產生一定數量的個體，并挑選其中最好的個體加入初始種群；而另一半規模則采用隨機方式產生。

NEH算法的基本假設原理是：一類產品，其總加工時間決定了其優先權，總加工時間越長則其優先權越高。NEH算法的描述：計算所有產品的總加工時間，按降序方式排列，此為初始排序序列。初始排序序列則采用部分枚舉搜索的方法，以得到最終的近似最優排序。

1.4 目標函數和適應度函數

主要目標函數以最大流程時間cmax=c(jn,m)來表示，其倒數1/cmax為適應度函數。

1.5 選擇操作

選擇操作則使用輪盤賭選擇策略，同時搭配最優保存策略，即本代群體中經過交叉、變異操作后所產生的適應度最低的個體，將會被當前群體中不參與交叉運算和變異運算的適應度最高的個體替換掉。

交叉操作。采用部分映射交叉（PMX）與順序交叉（OX）兩種方法，以保留雙親染色體中不同方面的特征，從而獲得較高質量的后代。

變異操作。采用互換變異與逆序變異的方法。第一步產生兩組隨機數，將這兩組隨機數的染色體中對應位置的基因進行互換操作。第二步再產生兩組隨機數，將這兩組隨機數對應的位置的基因顛倒順序。

結合制冷產品生產線實際調度數據，利用Matlab軟件進行5次計算，最大流程時間均小于實際生產所用的時間。借助軟件計算數據更改實際生產線調度方案，實際生產用時略有縮短，驗證了遺傳算法的可行性。但是，調度方案之間的優劣無法判斷，因此后續可采用仿真工具模擬分析后再做選擇。

2 結語

通過了解空間制冷產品生產線的基本流程、工藝要求及其他特性，把生產車間的調度問題簡化為流水車間調度問題，并通過遺傳算法理論求解經典的流水車間調度問題的方法。建立空間制冷產品生產的數學模型，運用遺傳算法求解該生產調度問題，最后利用Matlab軟件計算并與實際生產調度方案比較，驗證了遺傳算法求解此類問題的可行性。

[1]Taillard E.Some Efficient Heuristic Methods for the Flow-shop Sequencing Problem[J].European Journal of Oper.Res.，1990，47（1）：65-74.

[2]王凌，鄭大種.基于遺傳算法的Job Shop調度研究進展[J].控制與決策，2001，16（B11）：641-646.

[3]陳恩紅，劉貴全，蔡慶生.基于遺傳算法的Job-shop調度問題求解方法[J].軟件學報，1998，9（2）：139-143.

[4]K N Mc Kay，V C S Wiers.UnifyiJlg Thetheory and Practice of Production Scheduling[J].Journal of Manufacturing System，1999，18（4）：241-255.

[5]歐陽珍.基于遺傳算法的車間調度研究與應用[D].杭州：浙江大學，2004：3-4.

[6]孫月蘭.基于遺傳算法的紡織企業生產計劃與調度研究[D].杭州：浙江工業大學，2008.

[7]李錦飛，馬漢武.生產管理與調度[M].北京：化學工業出版社，2005.

[8]Mendez C A，Cerda J，Gorssmann，et al.State of the Art Review of Optimization Methods for Shotterm Scheduling of Batch Processes[J].Computers and Chemical Engineering，2006，（30）：913-946.

[10]Rodammer FA，Whir KP.A Recent Survey of Production Scheduling[J].IEEE Transactions on System Man and Cybernetic，1988，18（6）：841-851.

[11]李霄峰，史金飛，閻威武.混合流水車間調度的變鄰域禁忌搜索算法[J].計算機工程，2008，34（21）：10-12.

[12]劉延風，劉三陽.置換流水車間調度的蟻群優化算法[J].計算機應用，2008，28（2）：302-304.

[13]蔣淑瑁.基于最優化的冶金生產批量計劃及調度問題研究[D].沈陽：東北大學，2009.

[14]朱建炳.空間低溫制冷技術的應用與發展[J].真空與低溫，2010，16（4）.

[15]蘇路聲.面向多品種小批量生產計劃與控制研究[D].南京：南京理工大學，2008.

Discussion on Solving Production Scheduling Problem Based on Genetic Algorithm

CHEN Long
(Shanghai Jiaotong University, Shanghai 200240)

In order to meet the increasingly stringent requirements of space equipment and high-speed upgrading of equipment needs, multi-species, small batch, highly flexible production mode, has become China’s space refrigeration product development and production of the mainstream model. In addition, due to the rapid expansion of production scale and the comprehensive and complexity of the continuous improvement of management and process control requirements put forward higher and more stringent.

genetic algorithm, production scheduling, refrigeration products