劉 宇，吳杰程，錢(qián)晨紅，潘厲冰

(溫州大學(xué) 機(jī)電工程學(xué)院，浙江 溫州325035)

并行機(jī)生產(chǎn)是目前工業(yè)上普遍采用的一種生產(chǎn)方式，如LED半導(dǎo)體晶粒揀選工藝[1]等。并行機(jī)調(diào)度是車(chē)間生產(chǎn)調(diào)度中的一個(gè)重要問(wèn)題。關(guān)于并行機(jī)調(diào)度問(wèn)題的研究，通常需假設(shè)所有并行機(jī)在調(diào)度過(guò)程中持續(xù)可用，但實(shí)際調(diào)度生產(chǎn)過(guò)程經(jīng)常會(huì)出現(xiàn)由機(jī)器故障或長(zhǎng)時(shí)間運(yùn)行損耗等導(dǎo)致的停機(jī)問(wèn)題，因此必須進(jìn)行預(yù)防性維修來(lái)保障正常生產(chǎn)過(guò)程[2]。此外，在精益生產(chǎn)和無(wú)庫(kù)存生產(chǎn)方式下，工件通常不都是同一時(shí)刻到達(dá)而是在計(jì)劃范圍內(nèi)隨機(jī)到達(dá)的。因此，安排生產(chǎn)計(jì)劃時(shí)應(yīng)考慮工件到達(dá)時(shí)間的約束。

對(duì)于預(yù)防性維修的并行機(jī)調(diào)度問(wèn)題，已有不少學(xué)者進(jìn)行了研究，如：劉民等提出一種解決較大規(guī)模并行機(jī)調(diào)度問(wèn)題的遺傳算法[3]；?？×值柔槍?duì)并行多機(jī)調(diào)度問(wèn)題，基于遺傳算法的搜索能力提出一種能改善求解質(zhì)量的混合啟發(fā)式算法[4]；金壽松等采用兩段染色體編碼方式，對(duì)種群的初始化過(guò)程進(jìn)行優(yōu)化，并結(jié)合自適應(yīng)算子改進(jìn)了遺傳算法[5]；江才林等針對(duì)考慮周期預(yù)防性維護(hù)的異速并行機(jī)系統(tǒng)，提出了一種混合遺傳算法[6]；蔣凱麗等針對(duì)具有時(shí)間窗的預(yù)防性維護(hù)并行機(jī)下的混合流水線系統(tǒng)，提出了一種構(gòu)造式算法[7]。分析有關(guān)文獻(xiàn)可知，對(duì)于同時(shí)考慮預(yù)防性維修和工件到達(dá)時(shí)間的等效并行機(jī)調(diào)度問(wèn)題，用傳統(tǒng)遺傳算法求解可以獲得不錯(cuò)的結(jié)果，但存在種群中個(gè)體多樣性不強(qiáng)、易陷入局部最優(yōu)等問(wèn)題。為此，本文提出一種基于自適應(yīng)交叉變異概率以及災(zāi)變機(jī)制的改進(jìn)遺傳算法。

1 并行機(jī)調(diào)度問(wèn)題

并行機(jī)調(diào)度問(wèn)題可描述為：將n個(gè)工件安排在m臺(tái)并行機(jī)中的一臺(tái)機(jī)器上加工，實(shí)現(xiàn)預(yù)期目標(biāo)的最優(yōu)。

1.1 并行機(jī)調(diào)度的五要素

(1) 待加工工件集。設(shè)J={J1,J2,…,Jn}是一組數(shù)量為n的不可中斷加工工件。Jj表示第j(j=1,2,…,n)個(gè)工件。其中工件Jj的加工時(shí)間為p[j]，工件Jj的到達(dá)時(shí)間為r[j]，且每個(gè)工件到達(dá)的時(shí)間是動(dòng)態(tài)的。

(2) 加工機(jī)器集。設(shè)M={M1,M2,…,Mm}是m臺(tái)機(jī)器的集合。

(3) 預(yù)防性維修(Preventive Maintenance,PM)。機(jī)器需要進(jìn)行彈性的PM，以保證機(jī)器能正常生產(chǎn)。本文考慮的預(yù)防性維修均為彈性維修形式，即連續(xù)加工工件時(shí)間或者機(jī)器的使用時(shí)限不能超過(guò)維修時(shí)間的門(mén)檻(即維護(hù)門(mén)檻)Tu，且機(jī)器上工件Jj的加工時(shí)間不超過(guò)維護(hù)門(mén)檻，即p[j]≤Tu。維護(hù)作業(yè)所需時(shí)間(即維修時(shí)間)固定為t。

(4) 約束條件。①加工過(guò)程中不允許搶占工件，也不允許中斷工件供應(yīng)；②每臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件，且每個(gè)工件在同一時(shí)刻只能在一臺(tái)機(jī)器上加工；③工件之間沒(méi)有加工優(yōu)先級(jí)之別；④每個(gè)工件都有自己的到達(dá)時(shí)間；⑤工件Jj的到達(dá)時(shí)間r[j]和加工時(shí)間p[j]都是預(yù)先給定的；⑥機(jī)器的維修門(mén)檻Tu和維修時(shí)間t都是預(yù)先給定的；⑦同一工件在任一臺(tái)機(jī)器上的加工時(shí)間相同。

(5) 調(diào)度目標(biāo)。調(diào)度目標(biāo)是最大完工時(shí)間的最小化。

1.2 并行機(jī)調(diào)度問(wèn)題的甘特圖

根據(jù)調(diào)度問(wèn)題的三域表示法[8]，可將考慮PM與工件到達(dá)時(shí)間約束，以最小化完工時(shí)間為目標(biāo)的調(diào)度問(wèn)題標(biāo)記為Pm/r[j],FPM/Cmax。圖1所示為考慮PM和工件到達(dá)時(shí)間約束的多臺(tái)等效并行機(jī)單目標(biāo)調(diào)度問(wèn)題甘特圖。

圖1 考慮PM和工件到達(dá)時(shí)間約束的多臺(tái)等效并行機(jī)單目標(biāo)調(diào)度問(wèn)題甘特圖

考慮PM和工件到達(dá)時(shí)間約束的多臺(tái)等效并行機(jī)單目標(biāo)調(diào)度問(wèn)題包括M1，M2，…，Mm機(jī)器上所有工件的排序。Ji[k]表示機(jī)器Mi上第k個(gè)位置加工的工件。r[i][k]表示工件Ji[k]的到達(dá)時(shí)間，p[i][k]表示工件Ji[k]的加工時(shí)間，Ti[a]表示工件Ji[k]的總加工時(shí)間。PMia表示對(duì)機(jī)器Mi的第a次PM。C[i][nm]表示機(jī)器Mi的完工時(shí)間。

2 數(shù)學(xué)規(guī)劃模型

2.1 參數(shù)定義

C[j]：工件Jj的完工時(shí)間,j=1,2,…,n。

Ts,[i][k]：機(jī)器Mi上第k個(gè)位置的開(kāi)始加工時(shí)間(i=1,2,…,m;k=1,2,…,n-m+1)。

Q[i][k]：機(jī)器Mi上第k個(gè)位置的累計(jì)加工時(shí)間。

Tc,[j][k]：工件Jj在機(jī)器Mi上第k個(gè)位置的完工時(shí)間。

Cmax：m臺(tái)機(jī)器中最大的完工時(shí)間。

2.2 決策變量設(shè)置

X[i][j][k]：若工件Jj在第i臺(tái)機(jī)器Mi的第k個(gè)位置上加工，則為1；否則為0(i=1,2,…,m;j=1,2,…,n;k=1,2,…,n-m+1)。

Y[i][k]：若在機(jī)器Mi的第k個(gè)位置加工工件后需要維護(hù)機(jī)器,則為1；否則為0。

2.3 模型構(gòu)建

以最大完工時(shí)間最小為目標(biāo)的數(shù)學(xué)模型為：

Min.Cmax

(1)

每臺(tái)機(jī)器的每個(gè)位置最多加工一個(gè)工件，每個(gè)工件也必須在一臺(tái)機(jī)器的一個(gè)位置上加工。由此可列出下列式子：

(2)

每臺(tái)機(jī)器的最后一個(gè)位置不需要維修。由此可列出下列式子：

Y[i][n-m+1]=0

(3)

機(jī)器Mi第k個(gè)位置的開(kāi)始加工時(shí)間與累計(jì)到達(dá)時(shí)間的關(guān)系為：

(4)

機(jī)器Mi第k個(gè)位置的開(kāi)始加工時(shí)間要大于等于上一個(gè)工件的完工時(shí)間與該位置的PM時(shí)間之和。由此可列出下列式子：

Ts,[i][k]≥Tc,[j][k-1]+Y[i][k-1]·t

(5)

機(jī)器Mi第k個(gè)位置的完工時(shí)間等于該位置的開(kāi)始加工時(shí)間與該位置上工件的加工時(shí)間之和。由此可列出下列式子：

(6)

每臺(tái)機(jī)器上各位置的累計(jì)加工時(shí)間為：

(7)

機(jī)器Mi的累計(jì)加工時(shí)間的約束可表示為：

為盡早安排工件的加工，決策變量應(yīng)滿足下列條件：

(9)

工件Jj完工時(shí)間的約束可表示為：

(10)

最大完工時(shí)間可表示為：

Cmax≥C[j]

(11)

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

為解決考慮預(yù)防性維修的并行多機(jī)調(diào)度問(wèn)題，這里給出了圖2所示基于災(zāi)變機(jī)制的改進(jìn)遺傳算法流程。相比傳統(tǒng)遺傳算法，本文提出的算法采用隨機(jī)與啟發(fā)式混合方法生成初始種群，設(shè)計(jì)了自適應(yīng)交叉概率、變異概率和災(zāi)變算子。

圖2 基于災(zāi)變機(jī)制的改進(jìn)遺傳算法流程

3.1 設(shè)計(jì)編碼并生成初始種群

編碼方式采用自然數(shù)編碼，1～n表示工件號(hào)，用0區(qū)別兩臺(tái)機(jī)器，兩個(gè)0之間的數(shù)表示在一臺(tái)機(jī)器上加工的工件序號(hào)。

Pm/r[j],FPM/Cmax問(wèn)題具有下列性質(zhì)：若每臺(tái)機(jī)器的完工時(shí)間趨于一致，則最大完工時(shí)間趨于最?。辉跈C(jī)器都空閑的情況下，到達(dá)時(shí)間早的工件先加工；在已經(jīng)確定每臺(tái)機(jī)器加工工件順序的情況下，最優(yōu)解一定是耗費(fèi)時(shí)間最少的[8]。根據(jù)文獻(xiàn)[9],若能盡量使機(jī)器滿載，則最大完工時(shí)間趨于最優(yōu)。

為確保初始種群的質(zhì)量和多樣性，本文利用啟發(fā)式算法生成80%的初始種群，讓剩余的20%種群隨機(jī)生成。

按啟發(fā)式算法生成較優(yōu)初始種群的具體步驟有6個(gè)。

(1) 根據(jù)工件Jj到達(dá)時(shí)間r[j]從小到大的順序，對(duì)每個(gè)工件的序號(hào)進(jìn)行逆排序。如果兩個(gè)工件的加工時(shí)間相同，則將工件序號(hào)小的排在前面；如果兩個(gè)工件的到達(dá)時(shí)間相同，則將加工時(shí)間短的工件排在前面。

(2) 取前m個(gè)工件，分別安排在m臺(tái)機(jī)器的第一個(gè)位置。

(4) 將剩余的n-m個(gè)工件隨機(jī)排序并安排加工，若某臺(tái)機(jī)器的完工時(shí)間超過(guò)了S3，就將相應(yīng)的工件安排到下一臺(tái)機(jī)器上，以此類(lèi)推到最后一臺(tái)機(jī)器。

(5) 將剩余工件分配結(jié)束，并針對(duì)每臺(tái)機(jī)器上的工件,根據(jù)r[j]的值從小到大重新排序。

(6) 根據(jù)維護(hù)門(mén)檻Tu，對(duì)每臺(tái)機(jī)器上的工件進(jìn)行滿載調(diào)整。

3.2 計(jì)算目標(biāo)函數(shù)適應(yīng)度并進(jìn)行個(gè)體的選擇復(fù)制

個(gè)體I的適應(yīng)度為：

(12)

式中，Cmax(I)為對(duì)應(yīng)個(gè)體I的目標(biāo)最大值。

根據(jù)適應(yīng)度大小，采用輪盤(pán)賭法[10]選擇個(gè)體，并將其復(fù)制到后代種群中。

3.3 自適應(yīng)操作

在文獻(xiàn)[11]的基礎(chǔ)上，本文采用一種能自適應(yīng)調(diào)整交叉概率和變異概率的方法,進(jìn)一步提高遺傳算法的求解速度和收斂速度，以實(shí)現(xiàn)遺傳操作后的種群多樣化。

交叉概率為：

(13)

式中:gmax為后代種群中個(gè)體的最大適應(yīng)度；gmin為后代種群中個(gè)體的最小適應(yīng)度；g′為遺傳操作中兩個(gè)個(gè)體中較大的適應(yīng)度；gavg為后代種群中個(gè)體的平均適應(yīng)度；k1、k2、k3、k4均為指定系數(shù)，且1>k1>k2>k3>k4>0。

變異概率為：

(14)

式中，1>k5>k6>k7>k8>0。

只要指定kq(q=1,2,3,4,5,6,7,8)的值，就可以實(shí)現(xiàn)交叉概率和變異概率的自適應(yīng)調(diào)整。

3.4 交叉操作

將隨機(jī)選擇的兩條染色體分別作為父代1和父代2，并隨機(jī)采用兩種交叉方法(交叉方法A和交叉方法B)中的一種，進(jìn)行交叉操作，生成兩個(gè)子代。

(1) 交叉方法A：在兩個(gè)父代P1、P2中各選擇一個(gè)基因段，進(jìn)行交換?；蚨蔚奶攸c(diǎn)在于其兩個(gè)端點(diǎn)各為兩個(gè)相鄰的0。對(duì)于較優(yōu)的父代，選擇最大完工時(shí)間值最大的一段基因；對(duì)于較差的父代，選擇最大完工時(shí)間值最小的一段基因。交叉方法A的操作如圖3所示。

圖3 交叉方法A的操作示意圖

(2) 交叉方法B：鑒于工件數(shù)量為n、機(jī)器數(shù)量為m，可從1到n+m+1隨機(jī)生成兩個(gè)交叉點(diǎn)，將兩個(gè)父代P1，P2各分成3個(gè)區(qū)域；從集合{1,2,3}中隨機(jī)生成一個(gè)整數(shù)γ。如果γ=1，則交換P1，P2的前段區(qū)域；如果γ=2，則交換P1，P2的中段區(qū)域；如果γ=3，則交換P1，P2的后段區(qū)域。這里給出了γ=2 時(shí)交叉方法B的操作示意圖(圖4)。

圖4 γ=2時(shí)交叉方法B的操作示意圖

3.5 變異操作

對(duì)隨機(jī)選擇的染色體進(jìn)行變異操作時(shí)，應(yīng)先后采用兩種變異方法(變異方法A和變異方法B)，進(jìn)行變異操作。

(1) 變異方法A：在前50%代的種群中，隨機(jī)選擇兩個(gè)基因，進(jìn)行交換(若取到了0，則需要重新選擇)。變異方法A的操作如圖5所示。

圖5 變異方法A的操作示意圖

(2) 變異方法B：在后50%代的種群中，隨機(jī)選擇一個(gè)基因段，并對(duì)基因段內(nèi)的排序進(jìn)行倒置處理。變異方法B的操作如圖6所示。

圖6 變異方法B的操作示意圖

3.6 災(zāi)變操作

為避免遺傳種群出現(xiàn)“早熟”，可在傳統(tǒng)遺傳算法中加入災(zāi)變機(jī)制，運(yùn)用災(zāi)變算子進(jìn)行災(zāi)變操作[12]。在多次迭代后，大多數(shù)個(gè)體與最優(yōu)個(gè)體相似度較高時(shí)，應(yīng)進(jìn)行災(zāi)變操作。災(zāi)變操作是指，保存當(dāng)前種群中部分較優(yōu)秀個(gè)體而刪除其他個(gè)體，并隨機(jī)產(chǎn)生新的個(gè)體，對(duì)種群進(jìn)行補(bǔ)充，從而提高種群的多樣性[13]。

在災(zāi)變操作時(shí)，傳統(tǒng)上要將災(zāi)變規(guī)模設(shè)置成常數(shù)，若迭代后期使用前期的較大災(zāi)變規(guī)模，則會(huì)導(dǎo)致求解速度變慢以及最優(yōu)解的質(zhì)量變差。為保障算法的收斂性和最優(yōu)解的質(zhì)量，本文設(shè)置了動(dòng)態(tài)的自適應(yīng)災(zāi)變規(guī)模(即災(zāi)變算子)，使其能隨著遺傳種群迭代次數(shù)的改變而發(fā)生變化。災(zāi)變算子可表示為：

x=е-μr/Rx1

(15)

式中:μ為控制變量，1>μ>0；R為最大迭代次數(shù)；x1為初始設(shè)置的災(zāi)變規(guī)模。

設(shè)置災(zāi)變計(jì)數(shù)h′，用于記錄前一個(gè)種群最優(yōu)個(gè)體與后一個(gè)種群最優(yōu)個(gè)體相同時(shí)迭代的次數(shù)。如果h′達(dá)到了預(yù)設(shè)的最大災(zāi)變次數(shù)H，則需進(jìn)行災(zāi)變操作并啟用災(zāi)變算子。

災(zāi)變操作的具體步驟為：①針對(duì)遺傳種群內(nèi)所有個(gè)體，根據(jù)適應(yīng)度從小到大進(jìn)行排序；②計(jì)算當(dāng)前種群迭代次數(shù)下的災(zāi)變規(guī)模(即災(zāi)變的個(gè)體數(shù))x；③刪除當(dāng)前種群適應(yīng)度較低的前x個(gè)個(gè)體，而保留其他較優(yōu)秀的個(gè)體；④按隨機(jī)規(guī)則產(chǎn)生x個(gè)新個(gè)體，加入當(dāng)前種群，構(gòu)成災(zāi)變操作后的新種群。

3.7 算法停止

當(dāng)算法滿足迭代次數(shù)為200時(shí)，停止算法，得到最終結(jié)果。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

為了評(píng)估數(shù)學(xué)規(guī)劃模型與改進(jìn)遺傳算法的求解效率、最優(yōu)解質(zhì)量，本文進(jìn)行了相應(yīng)的實(shí)驗(yàn)和計(jì)算。實(shí)驗(yàn)數(shù)據(jù)包括機(jī)器參數(shù)、工件參數(shù)和PM參數(shù)等。其中：機(jī)器參數(shù)為機(jī)器的數(shù)量m;工件參數(shù)包括工件數(shù)量n、加工時(shí)間p[j]、到達(dá)時(shí)間r[j]；PM參數(shù)包括維護(hù)門(mén)檻Tu和維護(hù)作業(yè)所需時(shí)間t；災(zāi)變機(jī)制參數(shù)包括初始設(shè)置的災(zāi)變規(guī)模x1、預(yù)設(shè)的最大災(zāi)變次數(shù)H。

實(shí)驗(yàn)以中小規(guī)模問(wèn)題為例，工件數(shù)量n設(shè)置了7種，即n={6,7,9,10,11,12,15}；工件加工時(shí)間p[j]服從統(tǒng)計(jì)分布U[1,10];Tu設(shè)置了3個(gè)水平，即Tu={10,15,20}；t設(shè)置2個(gè)水平，即t={2,5}。機(jī)器數(shù)量m設(shè)置為3。Tu和t一共產(chǎn)生了6種組合。實(shí)驗(yàn)組合總共有42種，每種組合做10次實(shí)驗(yàn)，結(jié)果取平均值。

初始設(shè)置的災(zāi)變規(guī)模x1為50，預(yù)設(shè)的最大災(zāi)變次數(shù)H為5。k1=0.8,k2=0.6,k3=0.5,k4=0.2,k5=0.1,k6=0.05，k7=0.03，k8=0.01。

本文利用Dev-C++語(yǔ)言編寫(xiě)改進(jìn)遺傳算法的程序，并在IBM ILOG CPLEX Optimization Studio Ver. 12.7.1平臺(tái)上構(gòu)建了數(shù)學(xué)規(guī)劃模型；針對(duì)不同工件數(shù)量，采用數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法、改進(jìn)遺傳算法，分別求得最優(yōu)解，并統(tǒng)計(jì)了運(yùn)算時(shí)間。

4.2 結(jié)果分析

采用數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法、改進(jìn)遺傳算法求解的結(jié)果和平均運(yùn)算時(shí)間分別見(jiàn)表1、表2。表1中偏差程度的計(jì)算公式為：

表1 數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法和改進(jìn)遺傳算法的求解結(jié)果

表2 數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法和改進(jìn)遺傳算法的平均運(yùn)算時(shí)間

(16)

由表1可知：對(duì)于小規(guī)模問(wèn)題的求解來(lái)說(shuō)，數(shù)學(xué)規(guī)劃模型具有明顯的優(yōu)勢(shì)；從偏差程度來(lái)看，本文提出的改進(jìn)遺傳算法求解結(jié)果比傳統(tǒng)遺傳算法穩(wěn)定，且求解質(zhì)量?jī)?yōu)于傳統(tǒng)遺傳算法，具有更好的搜索能力。隨著工件數(shù)量的增大，改進(jìn)遺傳算法相對(duì)傳統(tǒng)遺傳算法的優(yōu)勢(shì)越來(lái)越明顯：當(dāng)工件為6件時(shí)，改進(jìn)遺傳算法與傳統(tǒng)遺傳算法的偏差程度都近似于0.00；當(dāng)工件為15件時(shí)，對(duì)于Tu和t的6種組合來(lái)說(shuō)，傳統(tǒng)遺傳算法的平均偏差程度是改進(jìn)遺傳算法平均偏差程度的21.01倍。

由表2可知，對(duì)于小規(guī)模問(wèn)題的求解來(lái)說(shuō)，數(shù)學(xué)規(guī)劃模型雖可得到最優(yōu)解，但隨著工件數(shù)量的增大，其運(yùn)算時(shí)間明顯增加。這是因?yàn)檎{(diào)度問(wèn)題的可行解空間隨著工件數(shù)量的增大呈指數(shù)型增加，而數(shù)學(xué)規(guī)劃模型的求解需要搜索全部可行解空間，所以運(yùn)算時(shí)間會(huì)急劇增加。而遺傳算法僅搜索其中一部分解即可，因此效率更高。對(duì)于中小規(guī)模問(wèn)題的求解來(lái)說(shuō)，改進(jìn)遺傳算法的災(zāi)變算子雖然會(huì)導(dǎo)致其運(yùn)算時(shí)間的增加，但改進(jìn)遺傳算法有更強(qiáng)的限制搜索空間的能力，因此總體上，改進(jìn)遺傳算法比傳統(tǒng)遺傳算法的運(yùn)算效率更高，且隨著工件數(shù)量的增大，兩種算法的平均運(yùn)算時(shí)間差異越來(lái)越大，從工件為6件的0.39 s增加到了工件為15件的2.30 s。

4.3 改進(jìn)遺傳算法再驗(yàn)證

為進(jìn)一步驗(yàn)證加入災(zāi)變機(jī)制的改進(jìn)遺傳算法的性能，選取n=15,m=3,t=2,Tu=10的實(shí)例,以最大完工時(shí)間為目標(biāo)函數(shù)，最大迭代次數(shù)為200進(jìn)行了實(shí)驗(yàn)。遺傳算法加入災(zāi)變機(jī)制前、后的收斂曲線如圖7所示。

圖7 遺傳算法加入災(zāi)變機(jī)制前、后的收斂曲線

從圖7可看出：在相同迭代次數(shù)下，加入災(zāi)變機(jī)制后遺傳算法的解質(zhì)量?jī)?yōu)于加入前；在目標(biāo)值相近的情況下，遺傳算法加入災(zāi)變機(jī)制后的迭代次數(shù)小于加入前的迭代次數(shù)，由此可認(rèn)為，迭代過(guò)程中加入災(zāi)變機(jī)制提高了算法的搜索能力；在目標(biāo)值相近的情況下，加入災(zāi)變機(jī)制前遺傳算法在115代收斂于目標(biāo)值30 min，而加入災(zāi)變機(jī)制后遺傳算法則在120代收斂于目標(biāo)值28 min。

5 結(jié) 語(yǔ)

本文針對(duì)預(yù)防性維修的等效并行機(jī)調(diào)度問(wèn)題，考慮工件的到達(dá)時(shí)間和維修策略約束，以最大完工時(shí)間的最小化為目標(biāo)，建立了相應(yīng)的數(shù)學(xué)規(guī)劃模型，并提出了基于災(zāi)變機(jī)制的改進(jìn)遺傳算法。通過(guò)改變初始種群的生成方式，利用自適應(yīng)災(zāi)變算子并引入災(zāi)變機(jī)制，大大提高了算法的搜索能力和求解質(zhì)量。實(shí)驗(yàn)證明，改進(jìn)遺傳算法用于求解等效并行機(jī)調(diào)度問(wèn)題是有效的。然而，本文只研究了單目標(biāo)的并行機(jī)調(diào)度問(wèn)題，并行機(jī)的實(shí)際調(diào)度問(wèn)題還存在工件投放時(shí)間、交貨期、交貨時(shí)間等諸多約束和目標(biāo)。因此，未來(lái)可根據(jù)解決實(shí)際調(diào)度問(wèn)題的需要進(jìn)行多目標(biāo)動(dòng)態(tài)調(diào)度方法的研究。