曲 媛 劉慶閣 唐曉彬 魏 驍 王 碩
(中國船舶重工集團(tuán)公司第七○三研究所 哈爾濱 150060)
近年來,隨著科技和行業(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]。
有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í)間。
車間調(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í)間。
本文提出了遺傳退火算法解決生產(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所示。
編碼:利用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ù)目。
首先隨機(jī)生成L條含N×M個基因的染色體構(gòu)成初始種群,每條染色體代表一個個體,即車間分配任務(wù)的一種可行調(diào)度。
根據(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)行排序。
在遺傳算法中,通常從一個父代種群中選擇一部分遺傳給子代,為避免損失有效基因,所以提高適應(yīng)度較大的個體被選擇的概率,從而提高算法的收斂效率,降低計(jì)算時(shí)長。本文采用傳統(tǒng)的輪盤賭的方式來選擇子代染色體,編寫函數(shù)selection(),用于選擇個體。
在遺傳算法中,交叉操作是為了在不發(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ù)組合并。
編寫函數(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í)間。
調(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。
本文對改進(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)定。