陳 龍

（上海交通大學(xué)，上海 200240）

基于遺傳算法求解生產(chǎn)調(diào)度問題的探討

陳 龍

（上海交通大學(xué)，上海 200240）

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

遺傳算法 生產(chǎn)調(diào)度 制冷產(chǎn)品

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

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

1 運用遺傳算法求解生產(chǎn)調(diào)度問題

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

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

1.1 空間制冷產(chǎn)品生產(chǎn)調(diào)度問題的數(shù)學(xué)描述

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

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

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

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

1.2 編碼方式

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

1.3 初始種群

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

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

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

1.4 目標函數(shù)和適應(yīng)度函數(shù)

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

1.5 選擇操作

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

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

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

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

2 結(jié)語

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

[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調(diào)度研究進展[J].控制與決策，2001，16（B11）：641-646.

[3]陳恩紅，劉貴全，蔡慶生.基于遺傳算法的Job-shop調(diào)度問題求解方法[J].軟件學(xué)報，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]歐陽珍.基于遺傳算法的車間調(diào)度研究與應(yīng)用[D].杭州：浙江大學(xué)，2004：3-4.

[6]孫月蘭.基于遺傳算法的紡織企業(yè)生產(chǎn)計劃與調(diào)度研究[D].杭州：浙江工業(yè)大學(xué)，2008.

[7]李錦飛，馬漢武.生產(chǎn)管理與調(diào)度[M].北京：化學(xué)工業(yè)出版社，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]李霄峰，史金飛，閻威武.混合流水車間調(diào)度的變鄰域禁忌搜索算法[J].計算機工程，2008，34（21）：10-12.

[12]劉延風，劉三陽.置換流水車間調(diào)度的蟻群優(yōu)化算法[J].計算機應(yīng)用，2008，28（2）：302-304.

[13]蔣淑瑁.基于最優(yōu)化的冶金生產(chǎn)批量計劃及調(diào)度問題研究[D].沈陽：東北大學(xué)，2009.

[14]朱建炳.空間低溫制冷技術(shù)的應(yīng)用與發(fā)展[J].真空與低溫，2010，16（4）.

[15]蘇路聲.面向多品種小批量生產(chǎn)計劃與控制研究[D].南京：南京理工大學(xué)，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