混合多處理機(jī)任務(wù)作業(yè)車間調(diào)度問(wèn)題的仿真研究

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

0 引言

制造車間調(diào)度是排序問(wèn)題研究體系的一個(gè)重要組成部分，它關(guān)系到企業(yè)整個(gè)生產(chǎn)系統(tǒng)的正常運(yùn)轉(zhuǎn)，關(guān)系到制造企業(yè)的成本和利潤(rùn)，一直以來(lái)都是學(xué)者們研究的熱點(diǎn)問(wèn)題。其中，鋼結(jié)構(gòu)件制造車間，因其加工工藝的特殊性，使車間調(diào)度系統(tǒng)比典型的作業(yè)車間調(diào)度（Jobshop Scheduling Problem，JSP）更為復(fù)雜。其作業(yè)以組對(duì)、焊接為主，基本流程為：下料→組對(duì)→焊接→修整，每道工序都需多位技工共同加工完成。不同于傳統(tǒng)車間調(diào)度要求每個(gè)工件的每道工序只需在一臺(tái)處理器上加工，鋼結(jié)構(gòu)件制造車間需要多個(gè)處理機(jī)（機(jī)器或人）同時(shí)進(jìn)行加工，使得這類生產(chǎn)車間目前還主要根據(jù)調(diào)度人員的經(jīng)驗(yàn)來(lái)排產(chǎn)，嚴(yán)重企業(yè)影響生產(chǎn)效率。

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

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

隨著制造業(yè)市場(chǎng)的不斷發(fā)展，為提高生產(chǎn)效率，越來(lái)越多的企業(yè)對(duì)復(fù)雜工序采取多臺(tái)處理機(jī)同時(shí)加工以減少生產(chǎn)時(shí)間提高生產(chǎn)效率的生產(chǎn)方式，但是目前對(duì)于這種具有多處理機(jī)任務(wù)約束的混合作業(yè)車間調(diào)度的研究較少，而這類問(wèn)題也確實(shí)廣泛存在于鋼結(jié)構(gòu)制造企業(yè)的生產(chǎn)過(guò)程中。因此本文主要針對(duì)具有多處理機(jī)任務(wù)約束的混合作業(yè)車間調(diào)度建立仿真模型，并根據(jù)運(yùn)用遺傳算法進(jìn)行優(yōu)化求解，以獲得更有效率的生產(chǎn)調(diào)度方案。

1 HJSMT調(diào)度問(wèn)題建模

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

對(duì)于HJSMT模型有以下假設(shè)：

1）所有處理機(jī)在開始時(shí)都是可用的；

2）訂單情況已知，包括處理機(jī)數(shù)、工件數(shù)以及工件的加工工序和時(shí)間；

3）每道工序同一時(shí)刻需要不少于一臺(tái)處理機(jī)同時(shí)加工；

4）下一工序必須在上一工序完成后進(jìn)行；

5）每臺(tái)處理機(jī)同一時(shí)刻只能對(duì)一個(gè)工件進(jìn)行處理；

6）處理機(jī)加工過(guò)程不可打斷，不可插入其他工件。

為了便于問(wèn)題的討論和描述，對(duì)于HJSMT問(wèn)題的相關(guān)符號(hào)和參數(shù)進(jìn)行定義：

N：工件數(shù)量；

m：處理機(jī)數(shù)量；

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

|Ji|：工件i所包含的加工工序的數(shù)量；

Mk：處理機(jī)k，k=1,2,...,m；

tij：工件i的第j道工序的加工時(shí)間；

eij：工件i的第j道工序的完工時(shí)間；

Cmax：完成所有工件加工的最大完工時(shí)間。

根據(jù)優(yōu)化目標(biāo)，建立數(shù)學(xué)規(guī)劃模型：

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

約束條件：

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

2 遺傳算法優(yōu)化

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

圖1 混合遺傳算法構(gòu)成示意圖

在啟發(fā)式方法中調(diào)度規(guī)則由于簡(jiǎn)單易實(shí)施、花費(fèi)時(shí)間少等特點(diǎn)，更利用在實(shí)際生產(chǎn)中應(yīng)用，因此本研究將調(diào)度規(guī)則嵌入到GA中，GA負(fù)責(zé)種群的進(jìn)化，而調(diào)度規(guī)則根據(jù)GA得到的染色體構(gòu)造與之所對(duì)應(yīng)的解，設(shè)計(jì)出混合遺傳算法。

根據(jù)Gere[6]的定義，調(diào)度規(guī)則是一個(gè)或者多個(gè)優(yōu)先規(guī)則（啟發(fā)式規(guī)則）的組合，調(diào)度規(guī)則用來(lái)將工件按照一定的排序準(zhǔn)則或策略分配給機(jī)器。考慮實(shí)際生產(chǎn)排產(chǎn)的實(shí)施性，選取先到先服務(wù)調(diào)度規(guī)則（First In First Service，F(xiàn)IFS）進(jìn)行混合遺傳算法的設(shè)計(jì)。

2.1 編碼解碼策略

使用GA求解時(shí)，首先要選擇合適的編碼策略，將問(wèn)題的解用染色體表示出來(lái)。為便于調(diào)度員安排生產(chǎn)調(diào)度，采用基于工件的編碼方法。每個(gè)染色體都由n個(gè)代表工件編號(hào)的基因組成，所有工件的任意排列即構(gòu)成一個(gè)可行調(diào)度，表示工件排產(chǎn)的優(yōu)先次序。解碼過(guò)程則按照編碼中工件的先后次序進(jìn)行生產(chǎn)，當(dāng)一個(gè)處理機(jī)前有多個(gè)工件等待加工，采用FIFS規(guī)則進(jìn)行加工。

2.2 種群的設(shè)計(jì)

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

2.3 選擇操作

選擇算子通過(guò)淘汰劣質(zhì)個(gè)體，保證了種群在迭代過(guò)程中處于進(jìn)化的狀態(tài)。本文采用比例選擇算子，計(jì)算某代群體中個(gè)體染色體的適應(yīng)值在群體總適應(yīng)值中所占的比例，即為該個(gè)體被選中的概率，根據(jù)輪盤賭選擇方法進(jìn)行選擇，根據(jù)每輪產(chǎn)生的隨機(jī)數(shù)[0,1]，將多輪隨機(jī)數(shù)作為選擇指針來(lái)進(jìn)行個(gè)體的選擇，最后共同組成新種群。

2.4 交叉操作

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

交叉概率pc決定交叉操作的頻率，越大越易于收斂到最優(yōu)解區(qū)域，但太高則會(huì)導(dǎo)致早熟收斂，一般在0.4～0.9的范圍內(nèi)進(jìn)行取值[8]。

2.5 變異操作

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

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

3 鋼結(jié)構(gòu)車間HJSMT問(wèn)題仿真研究

3.1 仿真流程設(shè)計(jì)

HJSMT是MTS問(wèn)題和JSP問(wèn)題的組合，既要求每道工序同時(shí)需要多臺(tái)處理機(jī)進(jìn)行加工（MTS問(wèn)題的特點(diǎn)），又必須按照既定的加工先后順序來(lái)進(jìn)行（JSP問(wèn)題的特點(diǎn)）。對(duì)于HJSMT問(wèn)題的仿真，由于在仿真的過(guò)程中，工件使用移動(dòng)對(duì)象MU進(jìn)行表示，處理機(jī)使用SingleProc對(duì)象來(lái)表示，而要求一個(gè)實(shí)體同時(shí)占用多個(gè)處理機(jī)，這在仿真過(guò)程中是無(wú)法實(shí)現(xiàn)的。因此，如何實(shí)現(xiàn)一個(gè)實(shí)體同時(shí)占用多臺(tái)處理機(jī)成為了HJSMT問(wèn)題的仿真難點(diǎn)。

Yang, Pulat & Guan在對(duì)于MTS問(wèn)題進(jìn)行仿真求解的過(guò)程中，針對(duì)MTS問(wèn)題需要同時(shí)占用多臺(tái)處理器的問(wèn)題，設(shè)計(jì)了通過(guò)復(fù)制實(shí)體的方法進(jìn)行處理機(jī)的占用[9]。

但是對(duì)于MTS問(wèn)題的研究都只有一道加工工序，而HJSMT問(wèn)題則是有序的多道加工工序，因此在每道加工工序結(jié)束后，增加刪除復(fù)制實(shí)體創(chuàng)建原實(shí)體的操作，以便根據(jù)作業(yè)實(shí)體完成有序的多道工序的加工。

流程圖如圖2所示。

圖2 HJSMT問(wèn)題仿真流程

3.2 仿真模型建立

1）規(guī)劃項(xiàng)目的組織結(jié)構(gòu)

新建仿真項(xiàng)目和HJSMT文件夾。如圖，在文件夾中復(fù)制JOB對(duì)象，來(lái)定義JOBList中Job的類型。對(duì)JOB增加自定義屬性Mnum，記錄每道工序所需的處理機(jī)數(shù)量；Numorders屬性記錄每個(gè)工件的總的工序數(shù)量；step屬性記錄工件的工序；start屬性則用來(lái)記錄工序開始加工的時(shí)間。

圖3 HJSMT仿真組織結(jié)構(gòu)設(shè)計(jì)

2）建立仿真模型

仿真模型包含控制區(qū)和模型區(qū)?？刂茀^(qū)用來(lái)控制整個(gè)模型的運(yùn)行，在Frame中插入一個(gè)用來(lái)繪制模型外觀的DrawRect方法，完成模型的外觀繪制，同時(shí)添加控制區(qū)所需對(duì)象。模型區(qū)由CreateMode方法根據(jù)numMachines快速建立。

由于HJSMT的仿真過(guò)程存在多處理機(jī)任務(wù)問(wèn)題，需要復(fù)制實(shí)體和刪除復(fù)制體，因此根據(jù)零件的名字，由程序Init方法建立創(chuàng)建復(fù)制體的BFJi和刪除復(fù)制體創(chuàng)建原實(shí)體的TMJi，加工時(shí)間均設(shè)置為0，BFJi的出口有方法PutA進(jìn)行控制；當(dāng)仿真結(jié)束后，由EndSim方法刪除BFJi和TMJi。故BFJi和TMJi只在模型運(yùn)行中出現(xiàn)，運(yùn)行結(jié)束后刪除。以numMachines=5為例，其仿真模型運(yùn)行如圖4所示。

圖4 HJSMT問(wèn)題仿真模型

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

工序加工結(jié)束后，處理機(jī)Mi在出口控制處調(diào)用Leave方法，復(fù)制實(shí)體前往對(duì)應(yīng)的TMJi中，刪除復(fù)制實(shí)體同時(shí)創(chuàng)建原實(shí)體，判斷工件的下道工序。

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

圖5 Proc表設(shè)計(jì)

4 實(shí)驗(yàn)仿真與分析

4.1 算例驗(yàn)證

以一個(gè)n=5，m=5的HJSMT問(wèn)題為例，其加工工序和所需加工時(shí)間如表1所示，括號(hào)中的數(shù)值即為該道工序所需加工時(shí)間，通過(guò)該算例對(duì)模型的有效性進(jìn)行驗(yàn)證。

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

圖6 初始調(diào)度甘特圖

表1 n=5，m=5的HJSMT問(wèn)題示例

圖7 優(yōu)化后甘特圖

實(shí)驗(yàn)表明，該模型可以模擬具有多處理機(jī)任務(wù)約束的混合作業(yè)車間的生產(chǎn)過(guò)程，且可以利用遺傳算法提供合理的優(yōu)化調(diào)度。

4.2 實(shí)例模擬

T制造企業(yè)是一家以生產(chǎn)鋼結(jié)構(gòu)產(chǎn)品為主的制造企業(yè)，其結(jié)構(gòu)車間以工人加工為主，生產(chǎn)中一般采用班組的劃分形式，每個(gè)班組一般由6～8人組成，主要為焊工和鉚工，也會(huì)增加1～2個(gè)打砂噴漆工，在實(shí)際生產(chǎn)中，車間會(huì)根據(jù)訂單的數(shù)量、工作量的大小來(lái)調(diào)整運(yùn)行的處理機(jī)的數(shù)量。

以吊梁機(jī)金屬結(jié)構(gòu)的部分零件為例，表2給出了其零件加工工藝信息。

表2 金屬結(jié)構(gòu)部分零件加工工藝信息

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

表3 金屬結(jié)構(gòu)大型零件工藝信息表

按照企業(yè)原來(lái)順序生產(chǎn)計(jì)劃，其時(shí)間安排為3月17日～3月29日，共13天完成生產(chǎn)。按照每天工作時(shí)間8小時(shí)，完成這3個(gè)零件的制作共需104小時(shí)，而采用本文的仿真優(yōu)化模型，得到新的調(diào)度安排為：2 3 1，調(diào)度甘特圖如圖8所示，總完工時(shí)間為95.5小時(shí)，生產(chǎn)時(shí)間縮短8.2%。

圖8 調(diào)度甘特圖

5 結(jié)束語(yǔ)

隨著越來(lái)越多的制造企業(yè)通過(guò)采用多處理機(jī)任務(wù)的生產(chǎn)方式來(lái)提高生產(chǎn)效率的車間制造，對(duì)于混合多處理任務(wù)的作業(yè)車間調(diào)度研究具有十分重要的意義，而多處理機(jī)任務(wù)作業(yè)車間調(diào)度是多處理機(jī)任務(wù)調(diào)度和作業(yè)車間調(diào)度問(wèn)題的結(jié)合，由于問(wèn)題的復(fù)雜性導(dǎo)致直至目前研究成果仍然較少。

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