解云龍,袁魯平,朱寧帥
(山東聯(lián)誠精密制造股份有限公司,濟(jì)寧272100)
隨著市場(chǎng)競爭的加劇,保證交期是生產(chǎn)制造業(yè)生產(chǎn)制造過程中的核心競爭力之一。中國很多生產(chǎn)制造企業(yè)開始轉(zhuǎn)向按訂單生產(chǎn)(MTO),甚至按訂單設(shè)計(jì)(ETO)的制造模式[1-2],這種情況下,通過計(jì)劃排程控制產(chǎn)品最終的交期,變得越發(fā)重要。保證產(chǎn)品最終交期,在生產(chǎn)制造過程中體現(xiàn)為最小化生產(chǎn)完成時(shí)間。最小化生產(chǎn)完成時(shí)間基本上涉及兩個(gè)目標(biāo),即最小化機(jī)器閑置時(shí)間和最小化訂單提前率/延遲率。必須通過考慮所有約束條件(例如優(yōu)先級(jí)、可用機(jī)器、機(jī)器轉(zhuǎn)換、機(jī)器設(shè)置、機(jī)器容量、大量庫存等)來實(shí)現(xiàn)這兩個(gè)目標(biāo)的最小化。這需要通過高級(jí)計(jì)劃和排程(APS)來實(shí)現(xiàn)。APS 本質(zhì)是實(shí)現(xiàn)有限資源的優(yōu)化配置和調(diào)度,需要依靠強(qiáng)大的計(jì)劃和排程算法驅(qū)動(dòng),很多學(xué)者在這些方面做了大量的研究。文獻(xiàn)[3]給出了基于常規(guī)遺傳算法和基于混合遺傳算法的車間作業(yè)調(diào)度問題的有效解法,文中表明混合遺傳算法在比常規(guī)遺傳算法效果更好,在更短的時(shí)間內(nèi)找到最佳結(jié)果;文獻(xiàn)[4]和文獻(xiàn)[5]提出的基于多階段的多目標(biāo)遺傳算法(moGA)可以有效求解生產(chǎn)車間計(jì)劃調(diào)度(JSP)過程中多目標(biāo)多約束的問題,并引出懲罰系數(shù)解決遺傳算法陷入局部最優(yōu)解的問題;文獻(xiàn)[6]和文獻(xiàn)[7]解釋了自適應(yīng)遺傳算法的概念,該算法以最佳適應(yīng)性自適應(yīng)地生成染色體,實(shí)現(xiàn)了在n 個(gè)工序(job)的m 臺(tái)設(shè)備/工作中心(machine)上進(jìn)行計(jì)劃調(diào)度,該過程是一個(gè)典型的NP-Hard 問題,求解及其復(fù)雜。因此,為了解決這個(gè)問題,給出了一種具有基于禁忌搜索的遺傳算法,即GATS[8]。GATS 的主要方法是最小化制造時(shí)間、處理時(shí)間和迭代次數(shù),從而獲得更好的結(jié)果[9-10]。文獻(xiàn)[11]針對(duì)多目標(biāo)高級(jí)計(jì)劃和調(diào)度問題的基于偏好的自適應(yīng)遺傳算法研究中心中給出了數(shù)值實(shí)驗(yàn),以說明所開發(fā)算法的有效性和效率。
綜上所述,本文提出了一種基于迭代搜索技術(shù)的遺傳算法,以實(shí)現(xiàn)生產(chǎn)制造生產(chǎn)車間的多目標(biāo)多約束條件下的計(jì)劃調(diào)度問題。本算法采用通用編程模型的形式,可以滿足所有優(yōu)先級(jí)和替代機(jī)器容量的限制。基于迭代搜索技術(shù)的遺傳算法主要考慮3個(gè)步驟,即染色體編碼、確定適應(yīng)度函數(shù)以及將遺傳算子用作選擇、交叉和變異3 個(gè)步驟,以最小化目標(biāo)函數(shù)并提供更優(yōu)化的解決方案。
本節(jié)描述了典型的裝配車間生產(chǎn)計(jì)劃和排產(chǎn)數(shù)學(xué)模型,該模型已經(jīng)在大多數(shù)研究中應(yīng)用[3-7]。
車間調(diào)度數(shù)學(xué)模型的變量列舉如下:
K:訂單數(shù)量
D:位置數(shù)量
N:資源數(shù)量
Ok:訂單K 一組工序
JK:訂單K 的工序數(shù)
Mm:第M 項(xiàng)資源
Pd:第d 處位置
qk:訂單K 的批量
Am:在Mm上資源加工的工序
Pkim:機(jī)器m 上的Oki操作的單位處理時(shí)間
Lm:設(shè)備m 上的產(chǎn)能
tkilj:從Oki操作到Okj操作的設(shè)置時(shí)間
tmn:設(shè)備m 到設(shè)備n 之間的單位運(yùn)輸時(shí)間
ukij:從運(yùn)行Oki到運(yùn)行的訂單k 的單位負(fù)載大小
Sd:工廠Pd的資源集
Ld:可用于從Pd運(yùn)輸?shù)馁Y源集
rkij:優(yōu)先約束
考慮到每臺(tái)機(jī)器上每個(gè)工序的處理時(shí)間的輸入數(shù)據(jù)集,每個(gè)工序之間的建立時(shí)間和每臺(tái)機(jī)器之間的轉(zhuǎn)換時(shí)間,優(yōu)化兩個(gè)目標(biāo)函數(shù)所需的各種參數(shù)如下:
(1)加工工時(shí)
(2)訂單k 的完工時(shí)間
(3)從機(jī)器m 到機(jī)器n 的總運(yùn)輸時(shí)間
(4)設(shè)備M 的工作負(fù)荷
(5)設(shè)備總空閑時(shí)間
式中:i,j 為工序號(hào)序列,i,j=1,2,…,Jk;k,l 為訂單號(hào)序列,k,l=1,2,…,K;m,n 為資源號(hào)序列,m,n=1,2,…,N;d,e 為位置號(hào)序列,d,e=1,2,…,D。
在每個(gè)方程式中,變量xkim,ykilj稱為決策變量,可以通過將條件循環(huán)應(yīng)用為以下變量來應(yīng)用:
目標(biāo)函數(shù)
這兩個(gè)目標(biāo)函數(shù)必須通過牢記一些約束來最小化:
(1)如果出現(xiàn)以下情況,機(jī)器不能同時(shí)處理多個(gè)操作
(2)在以下情況下,確保機(jī)器之間的中間傳遞:
必須滿足以上兩個(gè)約束條件,這樣操作才能在一臺(tái)機(jī)器上運(yùn)行而不會(huì)產(chǎn)生任何中斷。
(3)產(chǎn)能約束條件滿足:
(4)如果沒有違反關(guān)于優(yōu)先級(jí)限制的保證:
(5)確保靈活的工序(操作順序):
(6)對(duì)可變的設(shè)備列表選擇:
基于上述的數(shù)學(xué)模型建立車間計(jì)劃排產(chǎn)問題的數(shù)學(xué)解法,將問題定義為(訂單數(shù)量,工序數(shù)量,資源數(shù)量)。采用經(jīng)典的數(shù)據(jù)模型[3-4](2,10,4),(4,17,6),(5,25,8),(8,40,10),(20,70,15)(30,150,20)。對(duì)于所有這些要滿足的問題,參數(shù)和約束需要設(shè)置3 個(gè)輸入數(shù)據(jù)集,即在各種資源上的每個(gè)工序的處理時(shí)間,每個(gè)工序之間的設(shè)置時(shí)間以及資源之間的轉(zhuǎn)換時(shí)間。其中表1 是對(duì)應(yīng)工序在對(duì)應(yīng)設(shè)備/工作中心的加工時(shí)間;表2 為不同設(shè)備之間的轉(zhuǎn)移時(shí)間;表3 為不同工序之間的設(shè)置時(shí)間(前置時(shí)間)。
表1 對(duì)應(yīng)工序在對(duì)應(yīng)設(shè)備/工作中心的加工時(shí)間/(min)Tab.1 Processing time of corresponding process in corresponding equipment/work/(min)
表2 不同設(shè)備之間的轉(zhuǎn)移時(shí)間/(min)Tab.2 Transfer time between machines/(min )
表3 不同任務(wù)的安裝時(shí)間/(min)Tab.3 Setup time of different tasks/(min)
對(duì)于數(shù)據(jù)(2、10、4),所有10 個(gè)操作都可以在多臺(tái)機(jī)器上處理,因此稱為自由工序。
可以通過最小化上述兩個(gè)目標(biāo)函數(shù)f1和f2來找到給定過程的最優(yōu)解。相對(duì)于給定數(shù)據(jù)集和約束條件,可以通過應(yīng)用遺傳算法的概念來最小化這兩個(gè)方程。遺傳算法會(huì)為給定問題生成隨機(jī)解的數(shù)量,并從中選擇適合度最大的一個(gè)。這些解決方案將進(jìn)行多次迭代以找到最大擬合值。具有最大適合度值的解決方案表示最佳解決方案。在遺傳算法應(yīng)用可以通過考慮設(shè)置一些基本參數(shù):
最大變種數(shù)MG=100;
種群規(guī)模Psize=50;
最大迭代數(shù)N=50;
目標(biāo)函數(shù)Oj1的權(quán)重w1=0.2;
目標(biāo)函數(shù)Oj2的權(quán)重w2=0.5;
最早時(shí)間的權(quán)重α=0.1;
總延遲時(shí)間的權(quán)重β=0.9;
2.2.1 工序優(yōu)先級(jí)分配向量
這基本上是通過牢記優(yōu)先約束來隨機(jī)處理所有工序的分配,以完成所有任務(wù)。由于在上述案例研究中有10 個(gè)工序。這意味著為機(jī)器生成的初始染色體只會(huì)隨機(jī)生成10 個(gè)帶有隨機(jī)序列的操作的染色體。用P1表示。
如圖1所示,從P1到Pn隨機(jī)生成工序分配矢量的數(shù)量,其中n 表示總代數(shù)。
圖1 遺傳算法中工序優(yōu)先級(jí)分配向量示圖Fig.1 Vector diagram of process priority allocation in genetic algorithm
2.2.2 工序的設(shè)備分配向量
再次為上述工序隨機(jī)分配設(shè)備/工作中心。由于針對(duì)提供的不同設(shè)備進(jìn)行處理時(shí),每個(gè)工序都具有不同的加工時(shí)間,因此設(shè)備分配是尋找遺傳算法最優(yōu)解的有效任務(wù)之一,對(duì)于每個(gè)工序序列,將分配多個(gè)設(shè)備序列,即從M1到Mn,如圖2所示。
圖2 遺傳算法中工序的設(shè)備分配向量示圖Fig.2 Vector diagram of equipment allocation in genetic algorithm
(1)適應(yīng)度函數(shù)
最佳解決方案是由對(duì)前代具有更高適應(yīng)性的染色體代表的,公式如下:
式中:w1和w2是基于目標(biāo)函數(shù)的分配權(quán)重。
(2)交叉
通過保持對(duì)應(yīng)工序的設(shè)備分配向量相同,可以選擇具有最高適應(yīng)性的2 條最佳染色體,示意圖如圖3所示。
圖3 遺傳算法中交叉過程示圖Fig.3 Diagram of crossover process in genetic algorithm
(3)突變
遺傳算法中突變的實(shí)際目是檢查在雜交過程中產(chǎn)生的后代具有比先前最大適應(yīng)性的其他可能性。在計(jì)劃排產(chǎn)問題上表現(xiàn)為從每個(gè)工序處理時(shí)間的給定數(shù)據(jù)來看,每個(gè)工序在不同的機(jī)器上具有不同的執(zhí)行時(shí)間,如圖4所示。
圖4 遺傳算法中突變過程示圖Fig.4 Diagram of mutation process in genetic algorithm
表1 中顯示了針對(duì)每臺(tái)設(shè)備的優(yōu)化測(cè)試計(jì)劃。它由行數(shù)為1~4 的行的矩陣組成,每臺(tái)設(shè)備的工序順序?yàn)?~10。優(yōu)化的時(shí)間表顯示,首先為所有4 臺(tái)設(shè)備選擇了所有獨(dú)立的操作。其余工序?qū)⒌玫絻?yōu)先處理。
對(duì)于用例(2,10,4)采用上述基于迭代搜索的遺傳算法的優(yōu)化。得到優(yōu)化結(jié)果如表4所示,圖5展示了當(dāng)前適應(yīng)度函數(shù)的設(shè)備利用率。
表4 對(duì)于(2,10,4)的優(yōu)化結(jié)果Tab.4 Optimization results of(2,10,4)
與以往的研究對(duì)比發(fā)現(xiàn)[3-5],在相同的目標(biāo)函數(shù)下,優(yōu)化結(jié)果更佳,且計(jì)算時(shí)間更短。
迭代次數(shù)在最小化編譯時(shí)間的情況下起著至關(guān)重要的作用,可以最大程度地減少總生產(chǎn)時(shí)間,確保交期,表5 給出了幾個(gè)數(shù)據(jù)集下的最小化完工時(shí)間。
圖5 設(shè)備利用率Fig.5 Equipment utilization
表5 迭代搜索遺傳算法下的最小化完工時(shí)間Tab.5 Minimizing completion time under iterative search genetic algorithm
本文給出了一種迭代搜素的遺傳算法(IGA),該算法提供引入了均值匯編參數(shù),建立基于一個(gè)編程模型的遺傳算法,可以在滿足多約束條件的情況下最小化生產(chǎn)的總生產(chǎn)時(shí)間,經(jīng)與以往研究對(duì)比發(fā)現(xiàn),該算法可行。同時(shí)針對(duì)不同的數(shù)據(jù)集進(jìn)行計(jì)算分析,這些數(shù)據(jù)集的求解結(jié)果與迭代次數(shù)的所需變化有關(guān)。因此,對(duì)于多目標(biāo)多約束高級(jí)計(jì)劃和調(diào)度,基于迭代搜索的遺傳算法可以以較少的計(jì)算時(shí)間找到給定問題的最佳和最佳解決方案,可以滿足實(shí)際生產(chǎn)應(yīng)用中的實(shí)時(shí)性要求,尤其是在以按訂單設(shè)計(jì)(ETO)、按訂單生產(chǎn)(MTO)制造模式為主的生產(chǎn)制造業(yè)具備良好的應(yīng)用性。