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

陳 龍

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

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

陳 龍

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 編碼方式

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

1.3 初始種群

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

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

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

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

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

1.5 選擇操作

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

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

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

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

2 結(jié)語(yǔ)

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

[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ìn)展[J].控制與決策，2001，16（B11）：641-646.

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

[6]孫月蘭.基于遺傳算法的紡織企業(yè)生產(chǎn)計(jì)劃與調(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].計(jì)算機(jī)工程，2008，34（21）：10-12.

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

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

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

[15]蘇路聲.面向多品種小批量生產(chǎn)計(jì)劃與控制研究[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