混合多處理機任務作業車間調度問題的仿真研究

（北京林業大學 經濟管理學院，北京 100083）

0 引言

制造車間調度是排序問題研究體系的一個重要組成部分，它關系到企業整個生產系統的正常運轉，關系到制造企業的成本和利潤，一直以來都是學者們研究的熱點問題。其中，鋼結構件制造車間，因其加工工藝的特殊性，使車間調度系統比典型的作業車間調度（Jobshop Scheduling Problem，JSP）更為復雜。其作業以組對、焊接為主，基本流程為：下料→組對→焊接→修整，每道工序都需多位技工共同加工完成。不同于傳統車間調度要求每個工件的每道工序只需在一臺處理器上加工，鋼結構件制造車間需要多個處理機（機器或人）同時進行加工，使得這類生產車間目前還主要根據調度人員的經驗來排產，嚴重企業影響生產效率。

從上世紀90年代末開始出現了專門針對車間調度中的多處理機任務問題（Multiprocessor Task Scheduling,MTS）的研究[1]。研究初期還是主要集中于針對只有一道加工工序的工件的MTS問題，Drozdowski[2]根據機器有無差異對MTS問題從無差異的并行機和有差異的專用機這兩方面進行了詳盡的綜述。

進入21世紀后，逐漸出現了一些針對工件具有多道加工工序的多處理機任務調度方面的研究，并逐漸成為研究者關注的熱點，其中流水車間涉及的比較多（可看作是JSP問題的特例）。但由于作業車間相對于流水車間來說更加復雜，有關具有多處理機任務約束的混合作業車間調度（Hybrid Job-Shop Scheduling with Multiprocessor Task, HJSMT）問題的研究成果仍然很少。Brucker & Kramer[1]證明了即使只有兩臺處理機的HJSMT問題也為NP-hard難題。Huang 等[3]針對四臺處理機只考慮一道加工工序，即HJSMT的簡化MTS問題，提出一種線性時間內的近似算法。Gr?flin等[4]對具有工件插入的多處理機任務作業車間調度進行了研究，但該研究是基于已有可行的調度策略的假設，只對插入策略進行研究，并沒有實現對于HJSMT的調度方案設計。

隨著制造業市場的不斷發展，為提高生產效率，越來越多的企業對復雜工序采取多臺處理機同時加工以減少生產時間提高生產效率的生產方式，但是目前對于這種具有多處理機任務約束的混合作業車間調度的研究較少，而這類問題也確實廣泛存在于鋼結構制造企業的生產過程中。因此本文主要針對具有多處理機任務約束的混合作業車間調度建立仿真模型，并根據運用遺傳算法進行優化求解，以獲得更有效率的生產調度方案。

1 HJSMT調度問題建模

不同于JSP問題每道工序只需一臺處理機進行加工操作，HJSMT問題每道工序都需要不少于一臺處理機同時進行加工操作，即相當于對JSP問題增加了MTS問題的約束，故對于HJSMT問題的一般性描述如下：有n個工件通過m臺處理機進行制作，每個工件都需多道工序，同一工件的各工序間存在先后順序，且必須按照該順序生產（工藝路線約束）。每道工序都需不少于一臺處理機同時進行加工操作，每臺處理機同一時刻也只能進行一項加工工作（有限資源約束）。目標是找到一種調度方案，將所有工序在滿足工藝路線和有限資源約束的前提下，分派到各處理機上處理加工，并且總加工時間Cmax最小。

對于HJSMT模型有以下假設：

1）所有處理機在開始時都是可用的；

2）訂單情況已知，包括處理機數、工件數以及工件的加工工序和時間；

3）每道工序同一時刻需要不少于一臺處理機同時加工；

4）下一工序必須在上一工序完成后進行；

5）每臺處理機同一時刻只能對一個工件進行處理；

6）處理機加工過程不可打斷，不可插入其他工件。

為了便于問題的討論和描述，對于HJSMT問題的相關符號和參數進行定義：

N：工件數量；

m：處理機數量；

Ji：工件i，i = 1, 2, ..., n；

|Ji|：工件i所包含的加工工序的數量；

Mk：處理機k，k=1,2,...,m；

tij：工件i的第j道工序的加工時間；

eij：工件i的第j道工序的完工時間；

Cmax：完成所有工件加工的最大完工時間。

根據優化目標，建立數學規劃模型：

目標函數：

約束條件：

其中，式(2)表示工藝約束，第j+1道工序必須在第j道工序結束后進行，保證各工件可以按照既定的加工先后順序進行加工；式(3)表示機器約束，確保每臺處理機在同一時刻只能對一個工件進行加工，并且安排了各工件在同一處理機上的加工順序。

2 遺傳算法優化

1975年，Holland J H通過模擬生物進化的機制，提出了遺傳算法（Genetic Algorithm，GA）框架[5]。GA是一種群智能算法，通過隨機化搜索過程在解空間中進行最優解搜尋。在搜尋最優解時，要求搜尋過程不僅要盡可能覆蓋全局最優解（求泛能力），還要能夠不斷向當前局部最優解逼近（求精能力），而GA在求解過程中，并不擅長微調搜尋，故在GA中嵌套啟發式算法，形成混合遺傳算法。

圖1 混合遺傳算法構成示意圖

在啟發式方法中調度規則由于簡單易實施、花費時間少等特點，更利用在實際生產中應用，因此本研究將調度規則嵌入到GA中，GA負責種群的進化，而調度規則根據GA得到的染色體構造與之所對應的解，設計出混合遺傳算法。

根據Gere[6]的定義，調度規則是一個或者多個優先規則（啟發式規則）的組合，調度規則用來將工件按照一定的排序準則或策略分配給機器?？紤]實際生產排產的實施性，選取先到先服務調度規則（First In First Service，FIFS）進行混合遺傳算法的設計。

2.1 編碼解碼策略

使用GA求解時，首先要選擇合適的編碼策略，將問題的解用染色體表示出來。為便于調度員安排生產調度，采用基于工件的編碼方法。每個染色體都由n個代表工件編號的基因組成，所有工件的任意排列即構成一個可行調度，表示工件排產的優先次序。解碼過程則按照編碼中工件的先后次序進行生產，當一個處理機前有多個工件等待加工，采用FIFS規則進行加工。

2.2 種群的設計

每個染色體由n個代表工件編號的基因組成，解空間即為所有工件任意排列組成的序列。從這有n個基因組成的染色體中，隨機生成一定數目的個體，選擇表現較好的個體構成初始種群。對于種群規模的設置，太小會導致形成欺騙問題或陷入局部最優；而過大，雖然可以防止局部最優，但也會導致計算量的增加，降低算法效率。王小平和曹立明提出根據實際個體數量將種群規模設置為[20,100][7]。

2.3 選擇操作

選擇算子通過淘汰劣質個體，保證了種群在迭代過程中處于進化的狀態。本文采用比例選擇算子，計算某代群體中個體染色體的適應值在群體總適應值中所占的比例，即為該個體被選中的概率，根據輪盤賭選擇方法進行選擇，根據每輪產生的隨機數[0,1]，將多輪隨機數作為選擇指針來進行個體的選擇，最后共同組成新種群。

2.4 交叉操作

交叉算子體現了生物進化過程中的基因重組過程，該過程保證群體中個體的品質得以提高。根據基于工件的編碼策略，一個個體的染色體中不允許有相同的基因碼，而基本遺傳算法的交叉操作生成的個體一般不能滿足約束，故采用部分匹配交叉的方法。

交叉概率pc決定交叉操作的頻率，越大越易于收斂到最優解區域，但太高則會導致早熟收斂，一般在0.4～0.9的范圍內進行取值[8]。

2.5 變異操作

在GA進化過程中，變異算子在一定程度上保證了種群的多樣性。變異算子是一個單個體遺傳操作算子，根據選定的變異概率pm對交叉后代集中的每個后代的每一位基因都進行變異操作，一般隨機生成隨機數r∈[0,1]，根據r的取值將基因進行變異操作。

變異概率pm的選取可以增加樣本模式的多樣性，但是不能過高，以防退化為隨機搜索，引發不穩定，所以通常設置較小，取值范圍在0.001～0.1[8]。

3 鋼結構車間HJSMT問題仿真研究

3.1 仿真流程設計

HJSMT是MTS問題和JSP問題的組合，既要求每道工序同時需要多臺處理機進行加工（MTS問題的特點），又必須按照既定的加工先后順序來進行（JSP問題的特點）。對于HJSMT問題的仿真，由于在仿真的過程中，工件使用移動對象MU進行表示，處理機使用SingleProc對象來表示，而要求一個實體同時占用多個處理機，這在仿真過程中是無法實現的。因此，如何實現一個實體同時占用多臺處理機成為了HJSMT問題的仿真難點。

Yang, Pulat & Guan在對于MTS問題進行仿真求解的過程中，針對MTS問題需要同時占用多臺處理器的問題，設計了通過復制實體的方法進行處理機的占用[9]。

但是對于MTS問題的研究都只有一道加工工序，而HJSMT問題則是有序的多道加工工序，因此在每道加工工序結束后，增加刪除復制實體創建原實體的操作，以便根據作業實體完成有序的多道工序的加工。

流程圖如圖2所示。

圖2 HJSMT問題仿真流程

3.2 仿真模型建立

1）規劃項目的組織結構

新建仿真項目和HJSMT文件夾。如圖，在文件夾中復制JOB對象，來定義JOBList中Job的類型。對JOB增加自定義屬性Mnum，記錄每道工序所需的處理機數量；Numorders屬性記錄每個工件的總的工序數量；step屬性記錄工件的工序；start屬性則用來記錄工序開始加工的時間。

圖3 HJSMT仿真組織結構設計

2）建立仿真模型

仿真模型包含控制區和模型區?？刂茀^用來控制整個模型的運行，在Frame中插入一個用來繪制模型外觀的DrawRect方法，完成模型的外觀繪制，同時添加控制區所需對象。模型區由CreateMode方法根據numMachines快速建立。

由于HJSMT的仿真過程存在多處理機任務問題，需要復制實體和刪除復制體，因此根據零件的名字，由程序Init方法建立創建復制體的BFJi和刪除復制體創建原實體的TMJi，加工時間均設置為0，BFJi的出口有方法PutA進行控制；當仿真結束后，由EndSim方法刪除BFJi和TMJi。故BFJi和TMJi只在模型運行中出現，運行結束后刪除。以numMachines=5為例，其仿真模型運行如圖4所示。

圖4 HJSMT問題仿真模型

Ready方法控制BF0的輸出，目的是將Source產生的工件對象送到對應的BFJi中，根據其加工所需的機器數量進行實體的復制；PutA則是判斷是否所需處理機集合可用，然后將復制實體送到對應的處理機，完成工序的加工操作，同時將加工信息記錄到scheduledOrders中。

工序加工結束后，處理機Mi在出口控制處調用Leave方法，復制實體前往對應的TMJi中，刪除復制實體同時創建原實體，判斷工件的下道工序。

JOBList表用來記錄訂單信息，即所需加工的零件信息，包含零件的類別、數量、名稱等。Proc表用來記錄零件的加工信息，包括每個零件的加工順序、所需加工處理機、以及所需加工時間等。由于HJSMT問題每道工序需要多臺處理機同時進行加工，且根據仿真流程，需要在加工前判斷所有處理機是否可用，故Proc表設計如圖5所示：第一列記錄工件信息，第二列使用table類型來記錄具體加工信息。加工信息表包含工序步驟、加工時間、加工所需處理機數量以及加工所需的具體處理機。

圖5 Proc表設計

4 實驗仿真與分析

4.1 算例驗證

以一個n=5，m=5的HJSMT問題為例，其加工工序和所需加工時間如表1所示，括號中的數值即為該道工序所需加工時間，通過該算例對模型的有效性進行驗證。

得到未進行優化前，即這5個工件按照順序生產時，總的加工完成時間為340，調度甘特圖如圖6所示，利用本文提出的混合遺傳算法，種群代數設置為100，采用De Jong[10]的經驗數據對相關參數進行設置：種群規模為50，交叉概率pc為0.6，變異概率pm為0.001，對HJSMT問題進行優化求解。得到調度優化后總的加工時間為270，比優化前縮短了20.1%，得到新的生產順序為：3 4 5 2 1，此時調度甘特圖如圖7所示。優化前后各處理機的設備利用率也都明顯提高。

圖6 初始調度甘特圖

表1 n=5，m=5的HJSMT問題示例

圖7 優化后甘特圖

實驗表明，該模型可以模擬具有多處理機任務約束的混合作業車間的生產過程，且可以利用遺傳算法提供合理的優化調度。

4.2 實例模擬

T制造企業是一家以生產鋼結構產品為主的制造企業，其結構車間以工人加工為主，生產中一般采用班組的劃分形式，每個班組一般由6～8人組成，主要為焊工和鉚工，也會增加1～2個打砂噴漆工，在實際生產中，車間會根據訂單的數量、工作量的大小來調整運行的處理機的數量。

以吊梁機金屬結構的部分零件為例，表2給出了其零件加工工藝信息。

表2 金屬結構部分零件加工工藝信息

根據車間生產情況，令仿真模型numMachines=6，即班組工人為M1-M6。這3個零件記為J1-J3，其加工工藝路線如表3所示，括號內的數字代表其加工時間（單位：h），將其輸入本文建立的仿真模型中。

表3 金屬結構大型零件工藝信息表

按照企業原來順序生產計劃，其時間安排為3月17日～3月29日，共13天完成生產。按照每天工作時間8小時，完成這3個零件的制作共需104小時，而采用本文的仿真優化模型，得到新的調度安排為：2 3 1，調度甘特圖如圖8所示，總完工時間為95.5小時，生產時間縮短8.2%。

圖8 調度甘特圖

5 結束語

隨著越來越多的制造企業通過采用多處理機任務的生產方式來提高生產效率的車間制造，對于混合多處理任務的作業車間調度研究具有十分重要的意義，而多處理機任務作業車間調度是多處理機任務調度和作業車間調度問題的結合，由于問題的復雜性導致直至目前研究成果仍然較少。

本文針對鋼結構車間具有多處理機任務約束的混合作業車間調度（HJSMT）問題進行仿真研究，對JSP問題增加多處理機任務（MTS）的約束，針對HJSMT問題進行抽象，建立數學規劃模型，然后結合JSP和MTS問題的特點，建立HJSMT仿真優化模型，并通過算例對模型的有效性進行驗證。結果表明，該優化模型能對HJSMT問題進行有效排產，提高企業生產效率。同時，為了適應制造企業車間變化的生產環境，設計快速建模方法，根據處理機數量快速生成問題的仿真模型，模型使用操作簡單，且基于工件編碼的調度結果便于理解與實施。本文的仿真模型基于特定假設，然而實際生產中往往會有各種不確定因素，如機器故障、工件插入等，后續也將不斷完善模型，更好地服務制造生產。