求解混合多處理機(jī)任務(wù)作業(yè)車間調(diào)度的改進(jìn)粒子群算法

翟亞飛,樊 坤,王 蒙,李心寧

(北京林業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院,北京 100083)

1 引 言

中國(guó)加入WTO后,全球性的競(jìng)爭(zhēng)加劇,給國(guó)內(nèi)的制造業(yè)帶來了新的挑戰(zhàn).隨著市場(chǎng)競(jìng)爭(zhēng)的日益激烈以及客戶需求的日益?zhèn)€性化多樣化,大批量流水生產(chǎn)模式正逐漸被適應(yīng)市場(chǎng)動(dòng)態(tài)變化的多品種、單件、小批量離散生產(chǎn)方式所替代[1].在這種離散制造企業(yè)中,經(jīng)常會(huì)出現(xiàn)工件的某些工序需要由多位工人(或多臺(tái)設(shè)備)同時(shí)加工的情況,這種多處理機(jī)任務(wù)加工已經(jīng)逐漸成為車間生產(chǎn)的主要方式.然而,傳統(tǒng)的車間調(diào)度卻要求每個(gè)工件的每道工序只能在一臺(tái)處理機(jī)上加工,因此具有這種單處理機(jī)任務(wù)約束的調(diào)度系統(tǒng)很難在現(xiàn)實(shí)的車間中得以應(yīng)用,使得這類企業(yè)目前主要根據(jù)調(diào)度人員的經(jīng)驗(yàn)來確定排產(chǎn),成為了影響生產(chǎn)效率提升的重大瓶頸.如何對(duì)具有多處理機(jī)任務(wù)約束的作業(yè)車間進(jìn)行高效排產(chǎn)已經(jīng)成為如今許多離散制造企業(yè)亟待解決的問題.

多處理機(jī)任務(wù)是指需要多個(gè)處理機(jī)(處理機(jī)通常指加工設(shè)備、機(jī)器或人)同時(shí)運(yùn)行的任務(wù).Chen & Lee[2]指出多處理機(jī)任務(wù)調(diào)度(Multiprocessor task scheduling,MTS)廣泛應(yīng)用在制造加工過程的勞動(dòng)力分配中,此外在實(shí)時(shí)機(jī)器視覺系統(tǒng)、并行計(jì)算機(jī)系統(tǒng)、多處理機(jī)診斷系統(tǒng)、泊位分配、人力資源計(jì)劃等方面均有應(yīng)用.

從上世紀(jì)90年代末開始出現(xiàn)了專門針對(duì)車間調(diào)度中的多處理機(jī)任務(wù)問題的研究[3].在此之前,對(duì)于MTS的研究主要都是針對(duì)只有一道加工工序的工件,Drozdowski[4]根據(jù)機(jī)器有無差異對(duì)MTS從無差異的并行機(jī)和有差異的專用機(jī)進(jìn)行了詳盡的綜述.

雖然流水車間調(diào)度是作業(yè)車間調(diào)度的特例,但是作業(yè)車間相對(duì)于流水車間來說更加復(fù)雜,因此目前對(duì)于混合多處理任務(wù)作業(yè)車間調(diào)度(Hybrid Job-shop Scheduling with Multiprocessor Task,HJSMT)的研究就更少了,這是因?yàn)樽鳂I(yè)車間調(diào)度僅是HJSMT調(diào)度的特例.所以針對(duì)HJSMT的研究主要集中在對(duì)某一類特殊的確定性問題進(jìn)行建模和設(shè)計(jì)求解算法.例如Brucker & Kramer[3]對(duì)相關(guān)問題進(jìn)行計(jì)算復(fù)雜性證明.Huang 等[14]對(duì)系統(tǒng)中只有4臺(tái)機(jī)器的情況進(jìn)行研究,提出一種線性時(shí)間近似算法求解該問題.Jansen & Porkolab[15]就可打斷與不可打斷兩種情形,提出一種近似調(diào)度方法.Gr?flin等[16]對(duì)具有工件插入的多處理機(jī)任務(wù)作業(yè)車間調(diào)度進(jìn)行研究,得到一個(gè)可行的工件插入定理.

由此可見,已有的HJSMT研究都是將該問題增加約束進(jìn)行簡(jiǎn)化后求解,即在特定情境下進(jìn)行研究,所提出的模型和求解方法普適性較差,因此本文就一般HJSMT問題進(jìn)行建模,并提出一種改進(jìn)粒子群算法(Improved Particle Swarm Optimization,IPSO)對(duì)其求解.同時(shí),由于目前國(guó)內(nèi)外文獻(xiàn)中已有的求解車間調(diào)度問題的改進(jìn)PSO算法,主要都是針對(duì)流水車間調(diào)度、作業(yè)車間調(diào)度以及柔性車間調(diào)度[17]等常見的調(diào)度問題進(jìn)行求解,而本文提出的改進(jìn)PSO算法主要專門求解HJSMT問題.編碼、解碼規(guī)則等算法機(jī)制的不同使得能夠求解常見調(diào)度問題的改進(jìn)PSO算法通常不能求解HJSMT問題.因此,本文的貢獻(xiàn)不僅體現(xiàn)在對(duì)一般HJSMT問題的建模上,而且更體現(xiàn)在專門求解HJSMT調(diào)度的改進(jìn)PSO算法的設(shè)計(jì)方面.

2 HJSMT問題調(diào)度建模

2.1 問題描述

HJSMT問題是經(jīng)典JSP問題和MTS問題的結(jié)合,并且已被證明為強(qiáng)NP-hard問題[3].對(duì)一般HJSMT問題描述如下:n個(gè)工件(J1,J2,…,Jn)在m臺(tái)處理機(jī)(M1,M2,…,Mm)上進(jìn)行加工,每個(gè)工件都包含一定數(shù)量的工序,同一個(gè)工件的工序之間存在工藝路線約束.處理機(jī)之間存在差異,任意一道工序Oij(工件i的第j道工序)需要由多臺(tái)指定的處理機(jī)加工,所需要的處理機(jī)集合為cij,相應(yīng)的加工時(shí)間為tij.目標(biāo)是找到一種調(diào)度方案,將所有工序在滿足約束(工藝路線約束和有限資源約束)的前提下,分派到各處理機(jī)上處理加工,使得總加工時(shí)間Cmax最短.

該模型有以下假設(shè):

1)不同工件的工序之間不存在約束;

2)工序的加工一旦開始就必須直到結(jié)束,中間不允許中斷;

3)一臺(tái)處理機(jī)一次只能加工一道工序;

4)不存在處理機(jī)損壞、原材料缺失、工件插入等突發(fā)情況;

5)處理機(jī)之間互不相同,不能相互替代.

2.2 數(shù)學(xué)建模

設(shè)S為所有工件的集合,O為所有工序的集合.對(duì)于S中的任意一個(gè)工作JiS,都有集合Ji={Oi1,Oi2,Oi3,…,Oi|Ji|},當(dāng)然也有Ji?O.在建立數(shù)學(xué)模型時(shí),定義一個(gè)“開始虛工序”σ和一個(gè)“結(jié)束虛工序”μ,分別代表整個(gè)加工過程的開始時(shí)刻和結(jié)束時(shí)刻.開始虛工序σ在所有工作開始之前開始,結(jié)束虛工序μ在所有工作結(jié)束之后才開始,它們的加工時(shí)間全部設(shè)定為0.如果使用xq,cq和tq分別代表工序q(其中qI∪{σ,μ})的開始加工時(shí)間、需要的處理機(jī)集合和加工時(shí)間,那么有cσ=cμ=?,tσ=tμ=0.由“結(jié)束虛工序”μ的含義可知:xμ就是最大完工時(shí)間.基于上述符號(hào)建立數(shù)學(xué)模型如下:

目標(biāo)函數(shù):

minimizeCmaxor minimizexμ

約束條件:

xb-xa≥ta，for all {a,b}A

xb-xa≥ta∪xa-xb≥tb， for all {a,b}B

xa-xσ≥0 ∪xμ-xa≥ta， for allaI

其中,A={{a,b}:aJ,bJ′withJ,J′S,J=J′anda

3 粒子群算法

粒子群算法(Particle Swarm Optimization,PSO)是一種模擬鳥群覓食的進(jìn)化計(jì)算技術(shù),與遺傳算法類似,也是一種迭代算法,但比遺傳算法具有簡(jiǎn)單易用,精度高,收斂速度快等優(yōu)點(diǎn).PSO以一組初始解為基礎(chǔ),通過對(duì)初始解的迭代更新來不斷接近最優(yōu)解.

PSO模擬鳥群的捕食行為,設(shè)想這樣一個(gè)場(chǎng)景:一群鳥在隨機(jī)搜尋食物,這個(gè)區(qū)域里面只有一塊食物,并且所有的鳥都不知道食物的具體位置,只是知道自己當(dāng)前的位置距離食物還有多遠(yuǎn).那么,尋找食物的最優(yōu)策略就是,搜尋目前距離食物最近的鳥的周圍區(qū)域.在PSO算法中,每一只鳥就被抽象成一個(gè)粒子.所有粒子都有兩個(gè)重要屬性:一是適應(yīng)值,通常由被優(yōu)化的函數(shù)決定,用來評(píng)價(jià)當(dāng)前位置的優(yōu)劣程度;二是速度,決定著粒子的飛行方向和距離.在每一次迭代中,每個(gè)粒子都通過追求兩個(gè)“極值”來更新自己的速度和位置.一個(gè)是粒子本身所能找到的最優(yōu)解,稱為“個(gè)體極值”pbest;另一個(gè)是整個(gè)種群目前找到的最優(yōu)解,稱為“全局極值”gbest.在找到這兩個(gè)極值時(shí),粒子通過公式(1)和公式(2)來分別更新自己的速度和位置:

(1)

(2)

圖1 粒子迭代更新示意圖Fig.1 Diagram of the particle iterative updating

維的速度都被限制在[-vdmax,vdmax][19].粒子通過追求個(gè)體極值和全局極值來進(jìn)行自我更新的方式,反映出粒子的自我學(xué)習(xí)能力和社會(huì)學(xué)習(xí)能力,正是通過這種群體的智慧才能夠不斷接近最優(yōu)解.在每次迭代中,種群中所有的粒子都通過公式(1)來更新速度,粒子速度在當(dāng)前速度、當(dāng)前位置、局部最優(yōu)位置和全局最優(yōu)位置的影響下發(fā)生有方向的變化,然后通過公式(2)更新其位置,如圖1所示.

4 改進(jìn)粒子群算法

在采用PSO算法進(jìn)行優(yōu)化求解時(shí),往往使用粒子的位置代表問題的解,通過位置的不斷更新來尋求優(yōu)化問題的最優(yōu)解.所以在求解調(diào)度問題時(shí),首要解決的問題就是如何在粒子位置和調(diào)度方案之間建立映射關(guān)系,主要工作包括兩個(gè)方面:

圖2 算法流程圖Fig.2 Flowchart of algorithm

編碼策略和解碼策略.在建立的映射關(guān)系的基礎(chǔ)上,必須保證粒子的迭代在可行解區(qū)域內(nèi)進(jìn)行.另外,PSO算法雖然精度高、收斂快,卻容易陷入局部最優(yōu).為了解決這個(gè)問題,設(shè)計(jì)了類似遺傳算法變異操作的變異機(jī)制.IPSO算法流程如圖2所示.

4.1 粒子編碼策略

為了建立粒子位置和調(diào)度方案的映射關(guān)系,本研究采用基于工序的編碼規(guī)則.這種編碼方式常用于JSP問題,在n個(gè)工件在m臺(tái)處理機(jī)上加工的JSP問題中,每個(gè)工件都要經(jīng)過m臺(tái)處理機(jī)進(jìn)行加工,即每個(gè)工件都要經(jīng)歷m道工序(工序數(shù)量和處理機(jī)數(shù)量相等)完成加工[20],那么一共有n*m道工序.與JSP問題不同,HJSMT問題中工件的工序數(shù)量是根據(jù)實(shí)際需要設(shè)定的,并不一定和處理機(jī)數(shù)量相等,用|Ji|表示工件i的工序數(shù)(i=1,2,3,…,n),此時(shí),n個(gè)工件共有|J1|+|J2|+…+|Jn|道工序.用一個(gè)粒子代表一個(gè)調(diào)度方案,那么粒子必須包含所有工序的信息,所以粒子是一個(gè)維度為|J1|+|J2|+…+|Jn|的向量.粒子向量中的元素為:自然數(shù)1,2,…,n,每個(gè)元素表示一個(gè)工件,工件i在粒子向量中出現(xiàn)|Ji|次,出現(xiàn)的次序表示該工件的工序.在這樣的編碼方式下,粒子向量中元素的排列組合可以表示出所有可能的調(diào)度方案.

以一個(gè)n=3,m=4的HJSMT問題為例,表1說明了該問題的處理機(jī)使用情況以及相應(yīng)的加工時(shí)間(由括號(hào)中的數(shù)字表示).

表1n=3,m=4的HJSMT問題示例
Table 1 An example for HJSMT withn=3,m=4

工件/工序工序1工序2工序3工件1M2M4(4)M1M2M4(4)-工件2M1M2(5)M3(5)M3M4(7)工件3M1M3(2)M1M2M3(3)M2M4(9)

以工件2的工序1中對(duì)應(yīng)的內(nèi)容M1M2(5)為例,則表示c21={M1,M2},t21=5,即第二個(gè)工件的第一道工序需要處理機(jī)1和處理機(jī)2在5個(gè)時(shí)間單位內(nèi)共同完成.

粒子向量的長(zhǎng)度為2+3+3=8,其中元素1出現(xiàn)2次,元素2和3各出現(xiàn)3次.現(xiàn)在給出一個(gè)粒子向量p=(3 2 2 1 1 2 3 3).其中的元素1,2,3代表工件1,工件2和工件3,其每一個(gè)元素出現(xiàn)的次序代表工序.例如,粒子中第三個(gè)元素為2,代指第2個(gè)工件,由于是第2次出現(xiàn),表明這是工件2的第2道工序O22,粒子向量與工序的對(duì)應(yīng)關(guān)系具體如表2所示.

表2 粒子向量與工序的對(duì)應(yīng)關(guān)系示例

Table 2 An example for the corresponding relation between

particle vector and process

p32211233工序O31O21O22O11O12O23O32O33

在此編碼規(guī)則下,粒子向量必須滿足如下三個(gè)約束條件:

a.每個(gè)粒子向量的長(zhǎng)度為:|J1|+|J2|+…+|Jn|;

b.粒子向量中的元素為:i=1,2,…,n;

c.任一元素i∈{1,2,…,n}出現(xiàn)的次數(shù)為|Ji|次,每次代表工件i的一道工序.

4.2 初始解產(chǎn)生機(jī)制

PSO算法是從一組初始解開始,通過不斷地對(duì)初始解進(jìn)行迭代更新來尋找最優(yōu)解,所以在開始計(jì)算之前需要生成初始粒子群(初始解).隨機(jī)產(chǎn)生的初始粒子必定不能滿足約束條件c,因此必須設(shè)計(jì)一個(gè)新的策略來產(chǎn)生初始粒子群,使其可以滿足約束a,b和c.

首先根據(jù)HJSMT問題生成一個(gè)長(zhǎng)度為|J1|+|J2|+…+|Jn|的向量p0,并將p0的所有元素初始化為0.然后按照如下程序生成初始粒子:

步驟0.i=1;

步驟1.在p0中隨機(jī)選取|Ji|個(gè)0,將其改寫成i;

步驟2.i=i+1

步驟3.if(i

True,步驟1;

False,步驟4;

步驟4.輸出p0.

重復(fù)上述程序s(種群的數(shù)量)次就可以生產(chǎn)一組數(shù)量為s的初始粒子群.按照這種機(jī)制產(chǎn)生的初始種群不但滿足所有的約束條件,而且因?yàn)槭请S機(jī)生成,粒子均勻分布于解空間中,避免了因?yàn)槌跏挤N群過于集中而導(dǎo)致的早熟.

4.3 迭代機(jī)制

在粒子迭代的過程中需要保證新一代粒子必須在解空間內(nèi),即必須滿足粒子的約束條件.但是如果僅僅使用公式(1)和公式(2)進(jìn)行迭代,則在新粒子向量中難以避免地會(huì)產(chǎn)生小數(shù),使新的粒子不能滿足約束條件b和約束條件c,也沒有實(shí)際的意義.所以必須對(duì)迭代機(jī)制進(jìn)行調(diào)整,使其不僅能夠保留粒子群算法的優(yōu)越性,還可以使新產(chǎn)生的粒子滿足所有的約束條件.

在新的機(jī)制中,仍然使用公式(1)和公式(2)進(jìn)行迭代,但是對(duì)迭代的結(jié)果進(jìn)行重新的調(diào)整和賦值.經(jīng)過公式(1)和公式(2)更新后的新粒子向量中的元素可能是整數(shù)也可能是小數(shù),這里把這些元素視為“排序指標(biāo)”.記錄這些“排序指標(biāo)”和對(duì)應(yīng)工序的映射關(guān)系.然后將“排序指標(biāo)”按照從大到小的順序降序排列,根據(jù)“排序指標(biāo)”和工序的映射關(guān)系,得到新的粒子,這樣的粒子顯然滿足約束條件.

表3 迭代機(jī)制示例
Table 3 An example for iteration mechanism

p0122312133工序O11O21O22O31O12O23O13O32O33Index3.45.43.68.72.13.26.32.81.8降序8.76.35.43.63.43.22.82.11.8p*0312212313工序O31O11O21O22O12O23O32O13O33

4.4 變異機(jī)制

粒子群算法有收斂速度快的優(yōu)點(diǎn),但是也伴隨著容易陷入局部最優(yōu)的缺點(diǎn).局部最優(yōu)又叫“早熟”,表現(xiàn)為所有的粒子聚集在一個(gè)非最優(yōu)解的周圍區(qū)域,粒子的全局搜索能力大大減弱,其結(jié)果往往是收斂于一個(gè)非最優(yōu)解,使得優(yōu)化性能降低.應(yīng)對(duì)局部最優(yōu)的策略往往是加強(qiáng)粒子的全局搜索能力,例如采用線性變化的ω(本研究也做了類似的設(shè)置).本文參考遺傳算法(Genetic Algorithm,GA)中的“變異”思想,在粒子迭代時(shí)增加變異過程,提高粒子跳出局部最優(yōu)的能力,從而增加粒子的全局搜索能力,達(dá)到減輕“早熟”的效果.

針對(duì)本文粒子的編碼規(guī)則,變異策略如下:對(duì)于任意一個(gè)粒子,隨機(jī)產(chǎn)生兩個(gè)不同的整數(shù)v1,v2∈{1,2,…,n}.然后將下標(biāo)為v1,v2的元素進(jìn)行交換.

表4 變異機(jī)制示例
Table 4 An example for variation mechanism

4.5 適應(yīng)值函數(shù)

適應(yīng)值函數(shù)用于衡量粒子的優(yōu)劣.本文研究的HJSMT問題的目標(biāo)是使得總加工時(shí)間最短,將適應(yīng)值函數(shù)設(shè)為目標(biāo)函數(shù),適應(yīng)值越小的粒子越優(yōu).

適應(yīng)值函數(shù)為:

F(x)= minimizeCmax

4.6 解碼策略

在粒子的編碼策略中,粒子被表示成集合了所有工序的有序向量.為了實(shí)現(xiàn)粒子和調(diào)度方案之間的映射關(guān)系,還必須建立粒子解碼策略,將一個(gè)粒子“翻譯”成一個(gè)對(duì)應(yīng)的調(diào)度方案并求出該粒子的適應(yīng)值.在本研究設(shè)計(jì)的解碼策略中,針對(duì)粒子向量中元素的先后順序,按照FIFO(First In First Out)規(guī)則進(jìn)行排班.在這種策略下,粒子向量中排列靠前的元素(工序)具有更高的優(yōu)先權(quán).解碼策略如下:

輸入:粒子向量

輸出:甘特圖和適應(yīng)值

步驟0.粒子向量中元素的下標(biāo)為r(r=1,2,…,|J1|+|J2|+…+|Jn|),這里初始化為r=1;所有處理機(jī)皆處于可用狀態(tài);Ci0=0(i = 1,2,…,n);

步驟1.對(duì)于粒子向量中的下標(biāo)為r的元素i所對(duì)應(yīng)的工序 Oij(這里i是第j次出現(xiàn),j=1,2,…,|Ji|),找出其處理機(jī)占用情況和時(shí)間:cij和 tij;

步驟2.找出前行工序Oi,j-1的完工時(shí)間為Ci(j-1);

步驟3.對(duì)于時(shí)間段 [ Ci(j-1),Ci(j-1)+tij]內(nèi)的每一個(gè)時(shí)間單位,檢查可用處理機(jī)是否滿足cij:

不滿足,則步驟4;

滿足,則步驟5;

步驟4.令Ci(j-1)=Ci(j-1)+1,并回到步驟3;

步驟5.讓Oij在時(shí)間段 [ Ci(j-1),Ci(j-1)+tij]內(nèi)開始加工;

步驟6.更新時(shí)間段 [Ci(j-1),Ci(j-1)+tij]內(nèi)的可用處理機(jī)情況,并且Cij=Ci(j-1)+tij;r=r+1;

步驟7. if(r > |J1|+|J2|+…+|Jn|):

False,步驟1;

True,步驟8;

步驟8.得出甘特圖;

步驟9.適應(yīng)值minimizeCmax=Max {C1|J1|,C2|J2|,…,Cn|Jn|}.

5 實(shí)驗(yàn)仿真與結(jié)果分析

實(shí)驗(yàn)參數(shù)的設(shè)定既要保證粒子具備一定的全局和局部搜索能力,還要盡可能地提高粒子跳出局部最優(yōu)解的能力.Eberhart[21]在其著作“Particle swarm optimization:developments applications and resources ”提出一種動(dòng)態(tài)慣性權(quán)重法,可以滿足上述要求并且結(jié)果精度更高.根據(jù)Eberhart的研究結(jié)果將算法的參數(shù)設(shè)置如下:

1)c1=c2=1.49445;

2)ω=[0.5+(Rnd/2.0)](Rnd是范圍在(0,1)的隨機(jī)數(shù));

3)rand1,rand2～ U(0,1);

4)粒子種群數(shù)量為40;

5)迭代次數(shù)為120次.

為驗(yàn)證算法的性能,首先使用本文提出的IPSO算法求解經(jīng)典JSP問題,之后再對(duì)HJSMT問題進(jìn)行求解分析.本文所介紹的算法使用Java語言實(shí)現(xiàn),實(shí)驗(yàn)在一臺(tái)配置為2.10 GHz CPU和4.0 GB RAM的個(gè)人電腦上進(jìn)行.

5.1 JSP經(jīng)典算例求解

JSP問題是HJSMT問題的簡(jiǎn)化,即每道工序每次只需1臺(tái)處理器同時(shí)進(jìn)行加工.本文選取FISHER 和THOMPSON提出的JSP標(biāo)準(zhǔn)算例FT類:FT06,FT10和FT20,以及LAWRENCE設(shè)計(jì)的LA類標(biāo)準(zhǔn)算例,選取LA01,LA05;LA06,LA10;LA11,LA15;LA16,LA20四類,共11個(gè)算例進(jìn)行求解.每個(gè)算例求解10次,記錄最優(yōu)解以及平均解,并與 MAnt算法[22]、PaGA算法[23]、NIMGA 算法[24]、TLBO-DL算法[25]等進(jìn)行比較,結(jié)果如表5所示.由表可知,本文提出的IPSO共找到7個(gè)算例的最優(yōu)解,且結(jié)果穩(wěn)定,10次求解均可找到最優(yōu)解;對(duì)于未找到最優(yōu)解的FT10、FT20、LA16、LA20問題,其10次運(yùn)算找到的最優(yōu)解相比其他算法表現(xiàn)也不差,并且穩(wěn)定性明顯比其他四種算法更加優(yōu)秀.由此可說明,本文所提出的IPSO算法具備較好性能.

表5 JSP標(biāo)準(zhǔn)算例求解結(jié)果
Table 5 Computational result of JSP benchmark problems

算例n*mMAnt[22]最優(yōu)解最優(yōu)解PaGA[23]最優(yōu)解平均解NIMGA[24]最優(yōu)解平均解TLBO-DL[25]最優(yōu)解平均解IPSO最優(yōu)解平均解FT066*6555555555555.0055555555FT1010*109309449971208930952.10930949.9951967FT2020*5116511781196122411731187.4011741182.312021214LA0110*5666666666666666666.00666666666666LA0510*5593593593593593593.00593593593593LA0615*5926926926926926926.00926926926926LA1015*5958958958958958958.00958958958958LA1120*5122212221222122312221222.001222122312221222LA1520*5120712401207127312071207.001207120712071207LA1610*109459779941005946956.07945950946946LA2010*10902925912917907909.30902905907910

5.2 HJSMT算例求解

設(shè)有5個(gè)工件要在6臺(tái)不同的處理機(jī)上面加工,處理機(jī)的編號(hào)為M1～M6.為了體現(xiàn)一般性,工件1、2、4的工序數(shù)為5道,工件2、5的工序數(shù)為6道,每道工序的處理機(jī)需求和加工時(shí)間具體如表6所示.

利用IPSO進(jìn)行求解,得到如圖3所示收斂曲線.粒子的優(yōu)化過程呈階梯狀,并且“更優(yōu)解”的更新效率逐漸降低.這是因?yàn)樵趦?yōu)化剛開始的時(shí)候,初始粒子均勻分布于解空間,只需要幾次的迭代就可以找到更加優(yōu)質(zhì)的解,如圖中顯示,在前20次迭代中就找到了4個(gè)“更優(yōu)解”.隨著迭代進(jìn)行,粒子群逐漸向某一區(qū)域聚集,找到“更優(yōu)解”的迭代成本也越來越高,在最后100次迭代中只找到了兩個(gè)“更優(yōu)解”.

從解的性質(zhì)來講,開始時(shí)初始的全局最優(yōu)解為48,對(duì)應(yīng)的粒子為:p0=(1,1,3,4,4,5,3,2,1,1,4,2,3,2,4,5,3,2,4,5,3,2,5,1,5,3,5),調(diào)度方案圖4(圖中方框中的數(shù)字“ij”代表Oij,即工件i的第j道工序).

圖3 HJSMT算例的收斂曲線Fig.3 Convergence curve of HJSMT instance

由圖4可以看出,不同工件的工序之間存在著嚴(yán)重的抵觸,導(dǎo)致初始方案中存在大量的空閑區(qū)域,處理機(jī)的利用率很低,完工時(shí)間較長(zhǎng).在實(shí)際生產(chǎn)中就表現(xiàn)為資源(設(shè)備和工人)利用率不高、生產(chǎn)效率低下、生產(chǎn)周期較長(zhǎng)、原料周轉(zhuǎn)率低、甚至可能導(dǎo)致延遲交貨.出現(xiàn)這種結(jié)果的原因有以下三個(gè)方面:

表6 n=5,m=6的HJSMT問題示例
Table 6 An instance for HJSMT with n=5,m=6

工件/工序工序1工序2工序3工序4工序5工序6工件1M1M3M5(2)M2M6(1)M1M5(2)M3M4(4)-M1M4M6(2)工件2M2M4(1)M2M3M6(4)M2(1)M1M3(3)M4M5(4)-工件3M1(3)M5M6(4)M1M6(1)M2M5M6(1)M2M4(5)M2M3(1)工件4M1M4M6(2)M1M3M5(3)M2M6(2)M2M4M6(2)M2M5(1)-工件5M3M5(2)M3M6(1)M3M5M6(3)M2M4(1)M1M4M6(2)M1M3M4M6(2)

1)相同工件的工序之間存在工藝路線約束.例如:O13和O14雖然需要的處理機(jī)種類完全不同,但是由于O14必須在其前行工序O13完成之后才能開始,就增加了總完工時(shí)長(zhǎng).

2)同一時(shí)間單位上存在資源(這里指處理機(jī))約束.由于

圖4 初始調(diào)度方案的甘特圖Fig.4 Gantt chart of initial scheduling scheme

某一處理機(jī)已經(jīng)被其他工序所占用,導(dǎo)致后面到來的需要此處理機(jī)的工序的開始時(shí)間只能向后推遲,直到該處理機(jī)被釋放.例如:O14和O22在處理機(jī)需求上存在沖突,O22必須在O14完工之后開始.

圖5 優(yōu)化后調(diào)度方案的甘特圖Fig.5 Gantt chart of optimized scheduling scheme

3)工序分配的不合理.這是本研究提出的改進(jìn)型粒子群優(yōu)化算法主要解決的問題.

在優(yōu)化后的調(diào)度方案中,可以找出真正影響完工時(shí)間的“關(guān)鍵路徑”:O11-O12-O41-O52-O22-O32/O14-O53/O24-O54/O33

-O55-O34-O35-O25-O16-O44-O56或O11-O12-O41-O31-O13-O32/O14-O53/O24-O54/O33-O55-O34-O35-O25-O16-O44-O56.這些工序是制約完工時(shí)間的瓶頸,如果想要進(jìn)一步縮短完工時(shí)間就要首先從這些工序上采取措施.

由圖5可以看出,在工藝路線和有限資源約束的前提下,算法考慮了各個(gè)工序的處理機(jī)占用情況,盡可能地進(jìn)行并行加工,大幅度提高了處理機(jī)的使用率,將最大完工時(shí)間從初開始的48縮短至36.

6 總 結(jié)

多處理機(jī)任務(wù)作業(yè)車間調(diào)度是多處理機(jī)任務(wù)調(diào)度和作業(yè)車間調(diào)度問題的結(jié)合,本文對(duì)HJSMT的研究有效擴(kuò)展了MTS和JSP兩個(gè)領(lǐng)域,具有重要的理論意義.此外,隨著單件、小批量和定制化生產(chǎn)逐漸成為離散制造企業(yè)的主流生產(chǎn)方式,對(duì)于HJSMT問題的研究又有著重要的實(shí)踐意義.

在對(duì)HJSMT問題建模時(shí)主要考慮了工藝路線約束和有限資源約束.模型的求解方面主要采用了一種改進(jìn)的粒子群算法,其中的改進(jìn)工作包括:為建立粒子和調(diào)度方案之間的映射關(guān)系,設(shè)計(jì)了粒子的編碼策略和解碼策略;為保證迭代在可行解區(qū)域內(nèi)進(jìn)行,改進(jìn)了迭代機(jī)制;為提高粒子群跳出局部最優(yōu)解的能力,引入了變異機(jī)制.并通過對(duì)JSP經(jīng)典算例和HJSMT問題的仿真實(shí)驗(yàn)證明該算法的有效性.下一步將繼續(xù)完善模型,利用提出的改進(jìn)粒子群算法去解決考慮機(jī)器故障、加工時(shí)間不確定等更為符合實(shí)際生產(chǎn)中的調(diào)度問題.