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

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

1 引言

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

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

2 問題描述

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

1）每個工作臺對應一道工序；

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

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

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

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

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

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

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

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

最小化完工時間f：

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

由于上述有約束條件：

1）每個工作臺對應一道工序

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

所以有：

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

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

所以有：

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

4 改進遺傳算法

4.1 算法描述

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

流程圖見圖1所示。

4.2 編碼與解碼

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

圖1 改進遺傳算法流程圖

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

4.3 初始化種群

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

4.4 適應度計算

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

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

2）從b［1］到b［480］順序判斷應放到哪個工作臺上，當j=b［i］］判斷可進行當前j工作的工作臺；

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

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

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

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

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

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

4.5 選擇操作

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

4.6 交叉操作

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

圖2 改進遺傳算法的交叉操作實例

具體步驟如下：

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

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

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

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

4.7 變異操作

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

輸出結果：

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

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

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

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

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

表1 各個工作對應的工作時間

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

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

其甘特圖見圖3。

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

其中灰色代表工作時間，白色代表未工作時間。

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

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

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

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

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

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

6 結語

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