帶有并行機的混合Job Shop調度問題

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

[關鍵詞] 并行機;混合Job Shop;遺傳算法

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

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

1引 言

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

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

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

2帶有并行機的混合Job Shop調度問題的模型

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

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

n工件總數

w機器類型數目

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

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

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

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

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

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

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

Ci工件i 的完工時間

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

本文考慮的帶有并行機的混合Job Shop調度問題，滿足以下基本假設:

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

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

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

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

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

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

(7)設備調整時間和工件傳送時間忽略不計;

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

建立帶有并行機的混合Job Shop調度問題的模型如下:

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

3基于遺傳算法求解

3.1.染色體編碼

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

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

3.4解碼

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

(1)確定當前工序的加工機器:

① 根據染色體，確定該染色體對應的加工工序串。

② 根據染色體和該染色體對應的加工工序串，確定機器類型串。

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

(2)參照文獻[6]中活動調度的方法，根據確定的機器，確定當前工序的開始加工時間。

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

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

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

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

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

工序的完工時間為:

ETijkq=STijkq+pijkq

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

工序的完工時間為:

ETijkq=STijkq+pijkq

此時，k 類型機器q新的加工結束時間為:

ET*kq=ETijkq (11)

4仿真實驗

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

圖1中每個時間段代表一個工件，其中標明了工件號和工件的加工工序號，每臺機器加工的結束時間標注在每行的尾部，優化排序后的最大流水時間為240min。

5結 論

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

主要參考文獻

[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]張超勇，饒運清，李培根，等.柔性作業車間調度問題的兩級遺傳算法[J].機械工程學報，2007，43(4):119-124.

[4]孫志峻，朱劍英.具有柔性加工路徑的作業車間智能優化調度[J].機械科學與技術，2001，20(6):931-935.

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

[6]王凌.車間作業調度及其遺傳算法[M].北京:清華大學出版社，2003.