基于改進(jìn)遺傳算法對車間調(diào)度問題的研究?

曲 媛 劉慶閣 唐曉彬 魏 驍 王 碩

（中國船舶重工集團(tuán)公司第七○三研究所 哈爾濱 150060）

1 引言

近年來，隨著科技和行業(yè)要求逐步提升，車間調(diào)度問題逐漸成為現(xiàn)代制造企業(yè)關(guān)注的主要問題，同時(shí)也是生產(chǎn)制造領(lǐng)域研究的熱點(diǎn)問題之一［1］。車間調(diào)度問題屬于非確定性多項(xiàng)式難題，主要針對不同制造企業(yè)對生產(chǎn)車間、機(jī)器、人員、物流等調(diào)度不同，生產(chǎn)周期會隨之變長的問題［2～4］。隨著行業(yè)需求的不斷上升，人工排產(chǎn)調(diào)度不僅會增強(qiáng)生產(chǎn)成本、延長生產(chǎn)周期，而且會浪費(fèi)制造企業(yè)的部分生產(chǎn)資源［5～6］。同時(shí)車間調(diào)度問題是計(jì)算機(jī)集成制造系統(tǒng)工程中的一個重要組成部分，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。在當(dāng)今的競爭環(huán)境下，如何利用計(jì)算機(jī)技術(shù)實(shí)現(xiàn)生產(chǎn)調(diào)度計(jì)劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進(jìn)度，提高設(shè)備利用率已成為許多加工企業(yè)面臨的重大課題［7～8］。

遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法［9～11］。其主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則［12～13］。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域，是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)［14］。

2 問題描述

有m個工作臺（5＜m＜10），有n項(xiàng)作業(yè)（n＞50），每項(xiàng)作業(yè)需要MTi時(shí)間（MTi為隨機(jī)數(shù)）完成，每項(xiàng)作業(yè)均在工作臺上完成，請采用優(yōu)化方法實(shí)現(xiàn)這一優(yōu)化作業(yè)方案。本文根據(jù)問題的復(fù)雜程度不同，給出以下約束條件：

1）每個工作臺對應(yīng)一道工序；

2）每個作業(yè)使用每個工作臺不多于1次；

3）每個作業(yè)利用每個工作臺的順序可以不同；

4）No.2、3、4工作臺上所對應(yīng)的工序加工順序必須滿足先后順序要求：2＞3＞4，后工序不能先于前工序，其他工序無順序要求；

5）任何作業(yè)沒有搶先加工的優(yōu)先權(quán)，應(yīng)服從生產(chǎn)順序調(diào)度安排；

6）作業(yè)加工過程中沒有新作業(yè)加入，也不能臨時(shí)取消作業(yè)的加工。

根據(jù)以上定義和約束條件，要研究的問題是：確定各項(xiàng)作業(yè)在各個工作臺的工作順序，給出優(yōu)化方案，優(yōu)化生產(chǎn)，得到滿足生產(chǎn)約束條件的較優(yōu)生產(chǎn)時(shí)間。

3 建立模型及目標(biāo)函數(shù)

車間調(diào)度問題的調(diào)度目的是確定各工作在不同工作臺的工作順序，得到滿足約束條件的較優(yōu)生產(chǎn)時(shí)間，建立車間調(diào)度問題的目標(biāo)函數(shù)表示如下：

最小化完工時(shí)間f：

式（1）中i表示每個作業(yè)i∈｛1，2，…，N｝，j表示每個工作臺j∈｛1，2，…，M｝，t_ij表示第i個工作在第j個工作臺上的工作時(shí)間，H_j表示第j個工作臺在開始生產(chǎn)后的未工作時(shí)間和，T_j表示第j個工作臺耗時(shí)多少結(jié)束生產(chǎn)。式（1）表示第j個工作臺的耗時(shí)等同于每個工作的工作時(shí)間和工作臺未工作的空閑時(shí)間的總和。式（2）表示車間調(diào)度問題的目標(biāo)函數(shù)即最小化M個工作臺工作時(shí)長最大的工作臺的耗時(shí)。

由于上述有約束條件：

1）每個工作臺對應(yīng)一道工序

2）每個作業(yè)使用每個工作臺不多于1次

所以有：

式（3）中l(wèi)代表每道工序l∈｛1，2，…，M｝，由式（3）可知每個工作臺對應(yīng)一道工序，則一個作業(yè)需在每個工作臺加工，且只加工一次。所以l=j且l，j∈｛1，2，…，M｝，j工作臺結(jié)束工作即所有工作的第j道工作已完成。M個工作臺均結(jié)束任務(wù)后即所有工作的M道工序均已完成，生產(chǎn)結(jié)束。

3）No.2、3、4工作臺上所對應(yīng)的工序加工順序必須滿足先后順序要求：2＞3＞4，后工序不能先于前工序，其他工序無順序要求；

所以有：

式（4～5）中 Cij表示第i個工作在第j個機(jī)器上加工的開始時(shí)間即開始第j個工序的開始時(shí)間，式（4）表示，以剛開始生產(chǎn)的時(shí)間點(diǎn)為起始點(diǎn)，第i個工作在第2個機(jī)器上的開始時(shí)間加上第i個工作在第2個機(jī)器上的工作時(shí)間要小于第i個工作在第3個機(jī)器上的開始加工時(shí)間。同理，第i個工作在第3個機(jī)器上的開始時(shí)間加上第i個工作在第3個機(jī)器上的工作時(shí)間要小于第i個工作在第4個機(jī)器上的開始加工時(shí)間。

4 改進(jìn)遺傳算法

4.1 算法描述

本文提出了遺傳退火算法解決生產(chǎn)過程中的車間調(diào)度問題，解決不同的約束條件下的調(diào)度問題。對車間調(diào)度問題進(jìn)行編碼，創(chuàng)建染色體和初始種群，進(jìn)行選擇、交叉、變異等一系列操作，得到目標(biāo)函數(shù)值即為適應(yīng)度函數(shù)值。之后進(jìn)行選擇，交叉，變異操作，再重復(fù)評價(jià)；在適應(yīng)度值持續(xù)偏差不大后退出循環(huán)，輸出適應(yīng)度最大的解［15～16］。

流程圖見圖1所示。

4.2 編碼與解碼

編碼：利用N個作業(yè)在M個工作臺工作構(gòu)建染色體，一個染色體上基因數(shù)量為N×M，是由M個N基因組成。例如：N=3，M=2，則染色體可以為［1，2，3，1，2，3］。

圖1 改進(jìn)遺傳算法流程圖

解碼：假設(shè)此次車間調(diào)度問題為N=3，M=2，3個工作的工作編號為1-3，將1-3每個編號均隨機(jī)生成2次作為一條染色體記作數(shù)組b［6］。假設(shè)j=b［i］，i代表要安排的第幾個任務(wù)i∈｛1，2，…，N×M｝，j代表第i個安排的任務(wù)為第j個工作，b［6］=［1，3，3，2，2，1］，從左至右依次判斷安排工作，b［1］=1則表示第一個要安排的工作為第1個工作，b［2］=3則表示第二個安排的工作為第3個工作。同理安排到b［5］時(shí)，b［1］到 b［4］中 i的數(shù)量為工作i已完成的工序數(shù)目。

4.3 初始化種群

首先隨機(jī)生成L條含N×M個基因的染色體構(gòu)成初始種群，每條染色體代表一個個體，即車間分配任務(wù)的一種可行調(diào)度。

4.4 適應(yīng)度計(jì)算

根據(jù)編碼方式得到j(luò)=b［i］判斷可進(jìn)行當(dāng)前j工作的工作臺；再從中判斷可用工作臺的運(yùn)行進(jìn)程，即之前工作運(yùn)行結(jié)束的結(jié)束時(shí)間，將當(dāng)前工作賦給結(jié)束時(shí)間最小的工作臺；重復(fù)上述操作將所有工作安排完成后，記錄各臺機(jī)器最終的結(jié)束時(shí)間，并找出其中結(jié)束時(shí)間最大的工作臺，將其結(jié)束時(shí)間進(jìn)行變換后作為適應(yīng)度值進(jìn)行評價(jià)。假設(shè)有N=60個工作，M=8個工作臺，具體步驟如下：

1）建立e［i］［j］數(shù)組存儲工作臺在當(dāng)前工作完成后各工作臺的工作進(jìn)程；

2）從b［1］到b［480］順序判斷應(yīng)放到哪個工作臺上，當(dāng)j=b［i］］判斷可進(jìn)行當(dāng)前j工作的工作臺；

3）當(dāng) l=1，2，5，6，7，8時(shí) e［l］［j］為空，即此時(shí) j工作未完成的工序 l，或 l=3時(shí) e［2］［j］不為空，即j工作的2工序已完成，當(dāng)前可加工3工序，或l=4時(shí)e［3］［j］＞e［2］［j］，即 j工作的 3 工序已完成，當(dāng)前可加工4工序；

4）將當(dāng)前可加工的工序數(shù)存入c［］數(shù)組中，c［ii］數(shù)組存儲可進(jìn)行當(dāng)前工作的工作臺；

5）再計(jì)算當(dāng)前可進(jìn)行j工作的工作臺的運(yùn)行進(jìn)度，將當(dāng)前工作賦給進(jìn)度最小的工作臺l，并將該工作j的需工作時(shí)間a［j］加上上一時(shí)刻l工作臺的結(jié)束時(shí)間的記入e［l］［j］數(shù)組即為此時(shí)l工作臺的運(yùn)行結(jié)束時(shí)間；

6）num變量存儲當(dāng)前工作j已完成的工作臺數(shù)量，記入f［l］［h］數(shù)組（即j工作的完成工序順序）用于輸出；

7）編寫函數(shù)Comparetime（），用于將各工作臺的最終結(jié)束時(shí)間賦給g［ii］數(shù)組；

8）編寫函數(shù)evaluation（），用于評價(jià)遺傳算法，將種群中的染色體按適應(yīng)度進(jìn)行排序。

4.5 選擇操作

在遺傳算法中，通常從一個父代種群中選擇一部分遺傳給子代，為避免損失有效基因，所以提高適應(yīng)度較大的個體被選擇的概率，從而提高算法的收斂效率，降低計(jì)算時(shí)長。本文采用傳統(tǒng)的輪盤賭的方式來選擇子代染色體，編寫函數(shù)selection（），用于選擇個體。

4.6 交叉操作

在遺傳算法中，交叉操作是為了在不發(fā)生優(yōu)質(zhì)基因損失的情況下產(chǎn)生新的個體，本文中通過交叉兩個父代個體產(chǎn)生兩個新的子代個體，由于編碼方式染色體b［i］中必須含有M個N工作，假設(shè)有N=60個工作，M=8個工作臺，即b［i］是由8個1～60的編號組成，任意交叉會破壞染色體結(jié)構(gòu)，使染色體失效，所以本文編寫了函數(shù)cross（），用于進(jìn)行遺傳算法中的交叉操作，交叉操作找出相同的數(shù)據(jù)段按照原有的順序進(jìn)行兩段基因的交換到不同的染色體上。

圖2 改進(jìn)遺傳算法的交叉操作實(shí)例

具體步驟如下：

1）見圖2，在1～480中選擇一個隨機(jī)數(shù)m，將父代1中m-480的基因取出記作ff［］數(shù)組，將父代1中1-m的基因記作father1［］數(shù)組；

2）分別計(jì)算ff［］數(shù)組中各個工作i的數(shù)量；3）在父代2中從左至右抽出相應(yīng)基因并以父代2的編碼排列形式排列記作ff1數(shù)組；

4）將父代2中剩余基因，以本身排序方式排序記作father2［］數(shù)組；

5）將father1［］數(shù)組同ff［］數(shù)組合并，同時(shí)將fa?ther2［］數(shù)組同ff1［］數(shù)組合并。

4.7 變異操作

編寫函數(shù)mutation（），用于進(jìn)行遺傳算法中的變異操作。將父代中一個染色體的兩段基因互換位置形成一個新的子代個體。

輸出結(jié)果：

1）編寫函數(shù)record（），用于記錄最優(yōu)解和判斷是否滿足條件；

2）編寫函數(shù)showresult（），用于輸出最終結(jié)果

3）程序主函數(shù)如下，添加計(jì)時(shí)函數(shù)clock計(jì)算程序運(yùn)行時(shí)間，并輸出最終各工作臺用時(shí)、最長耗時(shí)的工作臺用時(shí)、最短耗時(shí)的工作臺用時(shí)、兩者差值、各工作臺進(jìn)行工作的編號和算法運(yùn)行時(shí)間。

5 車間調(diào)度問題的實(shí)例仿真

調(diào)度實(shí)例分析，假設(shè)M為8，N為60，每個工作對應(yīng)的時(shí)間如表1所示。

表1 各個工作對應(yīng)的工作時(shí)間

設(shè)定種群數(shù)量SUM為4000，交叉概率為0.7，變異概率為0.09，應(yīng)用模擬退火算法在10條染色體的適應(yīng)度值相差不超過0.001時(shí)結(jié)束算法。得到的一組最優(yōu)解見表2。

表2 仿真最優(yōu)解：每個工作臺的工作總時(shí)間

其甘特圖見圖3。

圖3 仿真最優(yōu)解對應(yīng)甘特圖

其中灰色代表工作時(shí)間，白色代表未工作時(shí)間。

最優(yōu)解工序表如圖4。

圖4 各個工作臺工作各個作業(yè)的順序圖

總工作時(shí)間為2369.7952h，平均每臺位工作296.2244h，該算法所得結(jié)果較均值略有差異，結(jié)果較為滿意。

將算法運(yùn)行100次，記錄每次優(yōu)化結(jié)果和耗時(shí)，算法結(jié)果如圖5。

圖5 100次運(yùn)行算法的最優(yōu)解曲線圖

平均耗時(shí)387.08709h，從曲線上可看出算法較為穩(wěn)定。每次算法平均耗時(shí)141.221s。

6 結(jié)語

本文對改進(jìn)遺傳算法解決車間調(diào)度問題展開了深入的研究。車間調(diào)度問題是NP型問題，通過改進(jìn)的遺傳算法可有效解決車間調(diào)度問題，得到滿足生產(chǎn)約束條件的較優(yōu)調(diào)度，有指導(dǎo)生產(chǎn)，大幅減少生產(chǎn)時(shí)間的功效。同時(shí)通過仿真實(shí)驗(yàn)有效證明了本算法的全局搜索能力較好，能得到較優(yōu)的實(shí)驗(yàn)結(jié)果，且算法較為穩(wěn)定。