帶有并行機(jī)的混合Job Shop調(diào)度問題

[摘 要] 本文分析帶有并行機(jī)的混合Job Shop調(diào)度問題并建立其模型，利用改進(jìn)的遺傳算法求解問題，在算法設(shè)計中，采用基于工序的編碼方式，分兩步進(jìn)行解碼，給出相關(guān)的遺傳操作，列舉實例說明帶有并行機(jī)的混合Job Shop調(diào)度問題，并針對實例進(jìn)行仿真實驗驗證算法和編碼方式的有效性和可行性，最后指出進(jìn)一步的研究方向。

[關(guān)鍵詞] 并行機(jī);混合Job Shop;遺傳算法

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2010 . 14. 025

[中圖分類號]F270.7;TP301.6 [文獻(xiàn)標(biāo)識碼]A [文章編號]1673 - 0194(2010)14 - 0065 - 03

1引 言

Job Shop調(diào)度是典型的調(diào)度問題，也是許多實際生產(chǎn)調(diào)度問題的簡化模型。Job Shop調(diào)度問題由n個工件在m臺不同功能的機(jī)器上加工，每個工件需要在每臺機(jī)器上加工，并允許每個工件具有不同的加工路徑。柔性Job Shop調(diào)度問題[1]是對Job Shop調(diào)度問題的拓展和延伸。目前，研究柔性Job Shop調(diào)度問題的文獻(xiàn)較多，大都假定柔性Job Shop調(diào)度問題具有以下特征:第一，工件具有柔性加工路徑，一道工序可以在多臺機(jī)器上加工，工序的加工時間可能隨著機(jī)器的性能不同而不同;第二，具有加工多種操作的多功能機(jī)器，即一臺機(jī)器可以加工多種不同類型的工序，一個工件的部分工序可能在同一臺機(jī)器上加工等[2-4]。

本文帶有并行機(jī)的混合Job Shop調(diào)度問題與柔性Job Shop調(diào)度問題有所區(qū)別。目前針對帶有并行機(jī)的混合Job Shop調(diào)度問題鮮有研究。文獻(xiàn)[5]用遺傳算法解決在并行機(jī)上的Job Shop調(diào)度問題，但問題假設(shè)一個工件的多道工序可以在同一臺機(jī)器上加工，與本文研究的問題也有所不同。

遺傳算法是一種模擬自然進(jìn)化過程的隨機(jī)性全局優(yōu)化方法，原理和操作簡單，通用性強，不受限制性條件的約束，具有全局解空間搜索能力，在生產(chǎn)調(diào)度領(lǐng)域得到了廣泛的應(yīng)用。本文首先描述帶有并行機(jī)的混合Job Shop調(diào)度問題并建立其模型，然后采用遺傳算法求解問題，并通過仿真實驗與分析，驗證了本文算法及編碼規(guī)則的可行性和有效性。

2帶有并行機(jī)的混合Job Shop調(diào)度問題的模型

帶有并行機(jī)的混合Job Shop調(diào)度問題是指n個工件在w個不同類型的機(jī)器上加工，每個類型機(jī)器有rk臺并行機(jī)，若工件的一道工序在該類型機(jī)器上加工，可以選擇并行機(jī)中任意一臺機(jī)器加工，每個工件具有自己的加工路線，并允許每個工件不必經(jīng)過每個類型的機(jī)器，假定每個工件不能在同一類型的機(jī)器上加工多次，所有工件的加工路線和每個工件每道工序在某類型機(jī)器上的加工時間事先確定，需要選擇在帶有并行機(jī)的某類型機(jī)器中哪臺機(jī)器上加工并使得工件的最大完工時間最小。

為了敘述方便，引入下列符號:

n工件總數(shù)

w機(jī)器類型數(shù)目

I工件集合I = {1，2，…，i，…，n｝

Oi工件i包含的工序集合 Oi={1，2，…，j，…，Oi｝即工件i有Oi道工序

M機(jī)器類型集合M={1，2，…，k，…，w｝，即機(jī)器類型為w種

Rk k類型機(jī)器集合 Rk={1，2，…，q，…，rk｝，即k類型機(jī)器有rk臺，其中k=1，…，w

STijkq工件i的第j道工序在k類型機(jī)器的第q臺機(jī)器上加工的開始時間

pijkq工件i的第j道工序在k類型機(jī)器的第q臺機(jī)器上加工的時間

ETijkq工件i的第j道工序在k類型機(jī)器的第q臺機(jī)器上加工的結(jié)束時間

Ci工件i 的完工時間

mijk工件i 第j 道工序的加工機(jī)器

本文考慮的帶有并行機(jī)的混合Job Shop調(diào)度問題，滿足以下基本假設(shè):

(1)所有工件的加工路線已知，每個工件有特定的加工路線，可能與其他工件加工路線不同;

(2) 每個工件每道工序在某類型機(jī)器上的加工時間已知并相同，但在帶有并行機(jī)的某類型機(jī)器中哪臺機(jī)器上加工未知;

(3)每一時刻，某一種類型機(jī)器的某一臺機(jī)器只能加工一個工件;

(4)每一時刻，每個工件只能被一臺機(jī)器加工，同時加工過程不可中斷;

(5)整個加工過程中，每個工件不能在同一類型的機(jī)器上加工多次;

(6)在零時刻，所有的機(jī)器都空閑，所有的工件都可被加工，在加工過程中，機(jī)器不發(fā)生故障;

(7)設(shè)備調(diào)整時間和工件傳送時間忽略不計;

(8)不同工件具有相同的優(yōu)先級，不同工件的工序之間沒有先后約束。

建立帶有并行機(jī)的混合Job Shop調(diào)度問題的模型如下:

STijkq≥0;i∈I，j∈Oi，k∈Rk，q∈rk (5)

mijk∈rk={r1，r2，…，rw｝，i∈I，j∈Oi，k∈rk(6)

模型[P]中，式(1)表示目標(biāo)函數(shù)，即最小化工件的最大完工時間;式(2)表示不可中斷約束，即工件一旦開始加工就不允許中斷;式(3)表示操作的時序約束，即工件i的第j道工序必須在第(j-1)道工序完成后才能開始加工;式(4)表示操作的析取約束，即任一確定時刻， k類型機(jī)器的第q臺機(jī)器不能同時加工任意兩個工件o和i ;式(5)、式(6)定義了操作的開工時間變量和加工機(jī)器變量的值域。

3基于遺傳算法求解

3.1.染色體編碼

(2) 交叉:采用兩點段交叉法，按交叉概率Pc在臨時種群中選擇數(shù)對個體，在每對個體上隨機(jī)確定兩個固定的點，若這兩個點之間的相同工件的工件數(shù)目相同，則把兩個固定的點之間的基因進(jìn)行交叉;否則不進(jìn)行交叉。

(3) 變異:為了保證種群的穩(wěn)定性，選擇變異發(fā)生概率Pm≤0.001 選擇個體，然后在選擇的個體上隨機(jī)選擇兩個點，再將這兩個點的基因交換。

3.4解碼

針對帶有并行機(jī)的混合Job Shop調(diào)度問題的解碼操作有兩個關(guān)鍵點:第一，確定當(dāng)前工序在哪臺機(jī)器上加工;第二，確定當(dāng)前工序的開始加工時間和完成時間。

(1)確定當(dāng)前工序的加工機(jī)器:

① 根據(jù)染色體，確定該染色體對應(yīng)的加工工序串。

② 根據(jù)染色體和該染色體對應(yīng)的加工工序串，確定機(jī)器類型串。

③ 根據(jù)工件i所對應(yīng)的工序 j和加工機(jī)器類型k，同時考慮當(dāng)前工序允許加工的最早開工時間和機(jī)器當(dāng)前空閑時間兩種因素選擇機(jī)器。在k類型的rk臺機(jī)器中，找出結(jié)束時間最小的機(jī)器q，并在其上安排工件i的第j道工序的加工操作。如果存在優(yōu)先順序相同的機(jī)器，則從中隨機(jī)選擇機(jī)器。

(2)參照文獻(xiàn)[6]中活動調(diào)度的方法，根據(jù)確定的機(jī)器，確定當(dāng)前工序的開始加工時間。

將當(dāng)前工序Oijkq以在機(jī)器q上的最早允許加工時間加工，即從零時刻到當(dāng)前時刻對該機(jī)器上的加工空閑依次判斷能否將此工序插入加工。若能，則在空閑中插入加工，并修改該機(jī)器上的加工隊列;否則，以當(dāng)前時刻加工該工序，將此工序排在機(jī)器當(dāng)前隊列的隊尾。

工序Oijkq能在空閑時間段[ta，tb]中插入的條件是:用ETi(j-1)* 表示工件i的第(j-1)道工序加工結(jié)束時間。

max(ETi(j-1)*，ta)+pijkq≤tb (8)

①如果工序Oijkq在空閑中插入，則工序開始加工時間為:

STijkq=max(ETi(j-1)*，ta) (9)

工序的完工時間為:

ETijkq=STijkq+pijkq

②如果工序Oijkq在機(jī)器當(dāng)前隊列的末尾插入，ET*kq表示k類型q機(jī)器原加工結(jié)束時間，則工序的開工時間為:STijkq = ETi(j-1)*，ET*kq≤ETi(j-1)*ET*kq ， ET*kq>ETi(j-1)* (10)

工序的完工時間為:

ETijkq=STijkq+pijkq

此時，k 類型機(jī)器q新的加工結(jié)束時間為:

ET*kq=ETijkq (11)

4仿真實驗

采用Visual C++語言實現(xiàn)本文遺傳算法，實驗在配置為Pentium4/CPU3.00GHz/ RAM1GB的臺式機(jī)上進(jìn)行。表1給出了工件、工序?qū)?yīng)的機(jī)器類型以及在該類型機(jī)器上加工所需的時間。表2給出了不同類型機(jī)器對應(yīng)的并行機(jī)數(shù)量。取交叉概率Pc= 0.60，變異概率Pm= 0.001，種群規(guī)模為100，最大迭代次數(shù)設(shè)為500，經(jīng)過約50s后得到較滿意的目標(biāo)函數(shù)值，排序過程如圖1所示。

圖1中每個時間段代表一個工件，其中標(biāo)明了工件號和工件的加工工序號，每臺機(jī)器加工的結(jié)束時間標(biāo)注在每行的尾部，優(yōu)化排序后的最大流水時間為240min。

5結(jié) 論

本文針對帶有并行機(jī)的混合Job Shop調(diào)度問題進(jìn)行描述并建立模型，利用改進(jìn)遺傳算法求解問題，采用基于工序的編碼方式，解碼分兩步:第一步確定當(dāng)前工序的加工機(jī)器;第二步確定當(dāng)前工序的開工時間。給出實例說明帶有并行機(jī)的混合Job Shop調(diào)度問題并對實例進(jìn)行仿真實驗，實驗結(jié)果驗證了該算法的有效性和可行性。實際生活中，鋼鐵生產(chǎn)的調(diào)度問題可以轉(zhuǎn)化為該問題，下一步將針對鋼鐵生產(chǎn)背景的混合Job Shop調(diào)度問題展開研究。

主要參考文獻(xiàn)

[1]P Bruker，R Schlie. Job-Shop Scheduling with Multi-Purpose Machines[J]. Computing，1990，45(4):369-375.

[2]I Kacem，S Hsmmadi，P Borne.Approach by Localization and Multi-Objective Evolutionary Optimization for Flexible Job Shop Scheduling Problems[C]. IEEE Transaction on Systems，Man and Cybernetics， Part C，2002，32(1):1-13.

[3]張超勇，饒運清，李培根，等.柔性作業(yè)車間調(diào)度問題的兩級遺傳算法[J].機(jī)械工程學(xué)報，2007，43(4):119-124.

[4]孫志峻，朱劍英.具有柔性加工路徑的作業(yè)車間智能優(yōu)化調(diào)度[J].機(jī)械科學(xué)與技術(shù)，2001，20(6):931-935.

[5]童剛，李光泉，劉寶坤.用遺傳算法解決在并行機(jī)上帶有不同交貨期窗口的Job-Shop調(diào)度問題[J].系統(tǒng)工程，2000，18(3):37-42.

[6]王凌.車間作業(yè)調(diào)度及其遺傳算法[M].北京:清華大學(xué)出版社，2003.