馬薇薇，張艷霞，鄭小金，程立強(qiáng)，秦圣坤

(同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 200092)

0 引言

混合流水車間(Hybrid Flow Shop，HFS)調(diào)度問題是由流水車間調(diào)度問題發(fā)展而來的，是流水車間調(diào)度問題和并行機(jī)調(diào)度問題的結(jié)合。混合流水車間廣泛地存在于各種生產(chǎn)制造行業(yè)中，如化工、石油、鋼鐵、機(jī)械加工等行業(yè)。因此，在過去的幾十年中，該問題備受學(xué)術(shù)界的關(guān)注。1988年JGUPTA[1]研究了以最小化最大完工時間為目標(biāo)函數(shù)的兩階段混合流水車間調(diào)度問題,發(fā)現(xiàn)該問題是NP-hard問題。RIBAS等[2]從求解方法的角度回顧了近年的混合流水車間調(diào)度文獻(xiàn)，系統(tǒng)地對該問題的不同求解方法進(jìn)行了綜述。混合流水車間調(diào)度問題的解法主要可以分為精確解法、啟發(fā)式解法和混合方法。啟發(fā)式方法又可以分為構(gòu)造啟發(fā)式(constructive)和優(yōu)化啟發(fā)式(improvement)，基于規(guī)則的優(yōu)先級調(diào)度就是一種常見的構(gòu)造啟發(fā)式方法。由于混合流水車間問題極高的復(fù)雜性，精確求解這類問題往往很困難。當(dāng)面對大規(guī)模的現(xiàn)實問題時，啟發(fā)式算法尤其是基于規(guī)則的優(yōu)先級調(diào)度方法，成為了解決該問題的有力工具。

首先，規(guī)則調(diào)度相對簡單，可以在短時間內(nèi)生成可行的調(diào)度方案；其次，規(guī)則調(diào)度可以很方便地應(yīng)用在實際的工業(yè)場景中。值得注意的是，在調(diào)度規(guī)則的研究中，使用仿真模型作為輔助工具是常用方法。在計算機(jī)建立的仿真程序中，研究者可以方便地測試各種規(guī)則，比較不同規(guī)則的性能。BRAH等[3]建立了一個流水車間的仿真模型，通過將不同調(diào)度規(guī)則應(yīng)用于仿真模型，研究了規(guī)則對調(diào)度效果的影響。他們分別應(yīng)用了9個規(guī)則，最終發(fā)現(xiàn)這些規(guī)則里只有最短作業(yè)優(yōu)先規(guī)則在各種條件下都表現(xiàn)良好。PAUL[4]在一項更早的研究中，通過計算機(jī)模擬玻璃容器行業(yè)的簡化兩階段混合流水車間調(diào)度問題，同樣指出了基于最短處理時間的調(diào)度規(guī)則可能會得到較優(yōu)的調(diào)度策略。NAWAZ等[5]基于已有的啟發(fā)式算法(給總處理時間較短的作業(yè)賦予更高的優(yōu)先級)提出一種新的NEH啟發(fā)式算法(Nawaz, Enscore, Ham)，得到了更優(yōu)的工件排序序列。THORNTON等[6]提出利用Johnson規(guī)則和先到先服務(wù)(First In First Out，F(xiàn)IFO)的調(diào)度規(guī)則來解決調(diào)度問題。DESSOUKY等[7]基于Johnson規(guī)則提出一種改進(jìn)的調(diào)度規(guī)則，并通過實驗證明該規(guī)則是有效的。KURZ[8]針對安裝時間依賴于順序的混合流水車間問題，在Johnson規(guī)則上提出2種擴(kuò)展規(guī)則。LOGENDRAN等[9]在Johnson規(guī)則基礎(chǔ)上提出了LN規(guī)則，具有更好的求解性能。KURZ等[10]針對混合流水車間調(diào)度問題提出了4種啟發(fā)式規(guī)則，其中一種就是與最短作業(yè)時間優(yōu)先(Shortest Process Time, SPT)規(guī)則的改進(jìn)，并獲得了更好的表現(xiàn)。屈國強(qiáng)[11]提出一種將機(jī)器布局和工件加工時間特征緊密結(jié)合的新的調(diào)度規(guī)則，并將結(jié)果與NEH算法進(jìn)行比較，兩者各有所長。TAKAKU等[12]針對在線混合流水車間調(diào)度問題，提出一種新的調(diào)度規(guī)則，通過數(shù)值實驗發(fā)現(xiàn)該規(guī)則比FIFO表現(xiàn)更好。JAYAMOHAN等[13]分析比較了在混合流水車間調(diào)度問題中，各個階段采用相同的調(diào)度規(guī)則和在各個階段采用不同的調(diào)度規(guī)則兩種方法的不同表現(xiàn)。KIA等[14]建立了混合流水車間的仿真模型，比較了7種排序規(guī)則和一種啟發(fā)式算法的效果。實驗結(jié)果表明，最小剩余工時優(yōu)先與Wilkerson和Irvin法則是幾種規(guī)則中最好的。鄭永前等[15]針對混合流水車間調(diào)度問題，利用禁忌搜索尋找最優(yōu)加工順序。

對于混合流水車間問題的研究方法大多都基于集中的模型，即利用一個集中的模型完成所有計算，所有工件和機(jī)器都是被動地接收計算結(jié)果，而不是真正參與到調(diào)度過程中來。但是實際的生產(chǎn)系統(tǒng)又是離散的、分布式的，更為復(fù)雜。并且生產(chǎn)環(huán)境隨著加工過程也在實時發(fā)生變化，因而一些基于簡單排序規(guī)則所得到的調(diào)度方案難以滿足實際生產(chǎn)需要。目前，基于多Agent的仿真系統(tǒng)已經(jīng)越來越受到關(guān)注。KOUIDER 等[16]設(shè)計了一種多Agent系統(tǒng)來求解車間調(diào)度問題。系統(tǒng)主要包含監(jiān)管Agent和資源Agent，各Agent之間相互協(xié)作，利用局部空閑時間最短的分布式方法來求解調(diào)度方案，并與一些靜態(tài)調(diào)度規(guī)則進(jìn)行了對比，證明該系統(tǒng)具有更好的性能。MARTIN等[17]將啟發(fā)式算法與多Agent系統(tǒng)相結(jié)合來求解置換流水車間調(diào)度問題和車輛路徑問題。李應(yīng)等[18]將模糊數(shù)學(xué)規(guī)劃與多Agent系統(tǒng)相結(jié)合來求解作業(yè)車間調(diào)度問題。王芊博等[19]設(shè)計了一種多Agent系統(tǒng)，系統(tǒng)由管理Agent、策略Agent、工件Agent和機(jī)器Agent構(gòu)成。并且設(shè)計了一種插值排序算法應(yīng)用于策略Agent之中，來求解混合流水車間調(diào)度問題。

AnyLogic是一款功能強(qiáng)大的仿真軟件，支持多種建模方法：離散、系統(tǒng)動力學(xué)、多智能體等[20]，應(yīng)用領(lǐng)域廣泛，包括疾病傳播[21-22]、供應(yīng)鏈[23]、服務(wù)系統(tǒng)[24]、行人交通仿真[25]等。但目前借助AnyLogic中基于多Agent的建模方法解決混合流水車間調(diào)度問題的研究并不多，因此本文借助AnyLogic仿真軟件，基于多Agent的建模方法來研究混合流水車間調(diào)度問題，根據(jù)實際生產(chǎn)流程搭建仿真模型，通過設(shè)計、對比不同的調(diào)度規(guī)則，獲得高效的調(diào)度方案，幫助企業(yè)提高生產(chǎn)效率。

1 問題描述

混合流水車間調(diào)度問題通?？梢悦枋鰹椋篘個 任務(wù)經(jīng)過相同的加工流程，通過T道加工工序的加工，每道工序有mt臺機(jī)器，從而完成特定的生產(chǎn)目標(biāo)。主要特點包括：

(1)加工工序的數(shù)量至少為2。

(2)每道工序至少有一臺并行機(jī)，并且至少有一道工序包含多個并行機(jī)。

(3)所有工件都遵循相同的加工流程。

1.1 參數(shù)設(shè)計與決策變量

為方便問題描述，引入以下符號：

N為生產(chǎn)任務(wù)集合；

j為生產(chǎn)任務(wù)索引；

t為生產(chǎn)階段索引，t=1,2,…,T；

mt為第t階段的機(jī)器數(shù)量；

決策變量包括：

1.2 問題建模

根據(jù)混合流水車間調(diào)度問題的特點，建立混合整數(shù)模型如下：

(1)

(2)

t=1,2,…,T,m=1,2,…,mt;

(3)

t=1,2,…,T,m=1,2,…,mt;

(4)

t=1,2,…,T,m=1,2,…,mt;

(5)

(6)

(7)

(8)

(9)

(10)

(11)

i,j∈N,t=1,2,…,T,m=1,2,…,mt。

(12)

其中:式(1)為目標(biāo)函數(shù)，即最小化最大完工時間。式(2)～式(7)是對機(jī)器上加工任務(wù)順序的約束。式(2)表示每個任務(wù)在任意加工階段只能在一臺機(jī)器上加工一次；式(3)～式(5)表示每個任務(wù)在機(jī)器上都有且僅有一個緊前任務(wù)和緊后任務(wù)，若任務(wù)在機(jī)器上第一個加工，則它沒有緊前任務(wù)；同理，若任務(wù)在機(jī)器上最后一個加工，則它沒有緊后任務(wù)。式(6)和式(7)表示機(jī)器上只有一個首位任務(wù)和一個末位任務(wù)。式(8)～式(11)是對機(jī)器上加工任務(wù)加工時間的約束。式(8)表示各機(jī)器上緊前任務(wù)完成加工之后，緊后任務(wù)才能開始加工；式(9)表示各機(jī)器上緊前任務(wù)進(jìn)入下一階段的機(jī)器，緊后任務(wù)才能在該機(jī)器上開始加工；式(10)表示任務(wù)需要完成上一階段的加工才能開始下一階段的加工；式(11)表示在第一個階段，任務(wù)能從零時刻開始加工。式(12)是對決策變量取值范圍的約束。

本文利用Cplex求解器求解模型。但是因為該問題是一個NP-hard問題，當(dāng)問題規(guī)模較大時，難以求得最優(yōu)解。因此，利用基于Agent的建模方法，通過調(diào)度規(guī)則的設(shè)計與應(yīng)用，來求解混合流水車間調(diào)度問題。

2 仿真模型建立

本文的研究對象是某液體日用品生產(chǎn)企業(yè)。該企業(yè)的產(chǎn)品生產(chǎn)主要經(jīng)過3個階段(如圖1)：物料燒制、臨時存儲和產(chǎn)品灌裝。其中物料燒制為第一生產(chǎn)階段，產(chǎn)品灌裝為第二生產(chǎn)階段。該生產(chǎn)車間一共有8個鍋爐，18個存儲罐和10條灌裝線。相鄰兩個階段的機(jī)器用管道進(jìn)行連接，機(jī)器間存在著連接限制，其中三號鍋爐連通4個存儲罐，剩余7臺鍋爐各自連通2個存儲罐。各存儲罐也連通著數(shù)量不等的灌裝線。

生產(chǎn)任務(wù)是將不同的物料加工成對應(yīng)的產(chǎn)品。若同一個鍋爐內(nèi)連續(xù)燒制的兩個任務(wù)所屬物料不同，則在燒制不同種類的物料前，首先需要對鍋爐進(jìn)行清洗；同理，若同一條灌裝線上連續(xù)灌裝的是兩種不同種類的產(chǎn)品，則灌裝線也需要一定時間切換灌裝工具。

每個生產(chǎn)任務(wù)并非在所有鍋爐或者生產(chǎn)線上都可以加工，能加工的機(jī)器也存在著限制。相同物料在不同鍋爐上的燒制時間可能會不同，不同物料在相同鍋爐上的燒制時間也會不同。相同產(chǎn)品在不同灌裝線上的灌裝時間可能會不同，不同產(chǎn)品在相同灌裝線上的灌裝時間也會不同。

本文借助AnyLogic軟件，采用基于Agent的建模方法，將生產(chǎn)任務(wù)、鍋爐、存儲罐和灌裝線均看作智能體，系統(tǒng)結(jié)構(gòu)如圖2表示。首先，當(dāng)鍋爐智能體處于空閑狀態(tài)時，會根據(jù)一定的調(diào)度規(guī)則，從任務(wù)集合中尋找合適的任務(wù)進(jìn)行加工。當(dāng)該任務(wù)在鍋爐上完成第一階段的加工后，會將其轉(zhuǎn)移至與該鍋爐相連通的第一個可用存儲罐。當(dāng)存儲罐中存儲有物料時，會根據(jù)一定的調(diào)度規(guī)則，從灌裝線智能體中尋找合適的灌裝線進(jìn)行任務(wù)的第二階段加工。

2.1 數(shù)據(jù)輸入

在建立仿真模型時，需要將真實車間的生產(chǎn)數(shù)據(jù)輸入到仿真模型數(shù)據(jù)庫中，主要包括生產(chǎn)任務(wù)數(shù)據(jù)和車間結(jié)構(gòu)數(shù)據(jù)。

(1)生產(chǎn)任務(wù)數(shù)據(jù)包含所有待生產(chǎn)任務(wù)的相關(guān)信息，例如任務(wù)編號、物料編號、產(chǎn)品編號、在各鍋爐上的加工時間、在各灌裝線上的加工時間等。在仿真模型運行之前，將所有數(shù)據(jù)輸入到數(shù)據(jù)庫中。數(shù)據(jù)庫中的一條數(shù)據(jù)就對應(yīng)一個生產(chǎn)任務(wù)。在仿真模型運行時，系統(tǒng)會根據(jù)數(shù)據(jù)庫中的生產(chǎn)任務(wù)數(shù)據(jù)，動態(tài)地生成任務(wù)智能體群。

(2)車間結(jié)構(gòu)數(shù)據(jù)主要包括各機(jī)器的信息以及相鄰生產(chǎn)階段機(jī)器之間的連接關(guān)系。已知在物料燒制階段有8臺鍋爐，則相應(yīng)生成8個鍋爐智能體；在臨時存儲階段有18個存儲罐，則相應(yīng)生成18個存儲罐智能體；在產(chǎn)品灌裝階段有10條灌裝線，則相應(yīng)生成10個灌裝線智能體。由于生產(chǎn)的是液體日用品，相鄰生產(chǎn)階段的機(jī)器之間利用管道進(jìn)行連接，但并不是全連通的。根據(jù)外部數(shù)據(jù)庫中的相鄰生產(chǎn)階段機(jī)器間的連接關(guān)系，建立相應(yīng)機(jī)器智能體之間的連接關(guān)系。

2.2 任務(wù)智能體

任務(wù)智能體代表待生產(chǎn)的任務(wù)，記錄每個任務(wù)的生產(chǎn)過程與數(shù)據(jù)，包含數(shù)據(jù)模塊和行為模塊。

(1)數(shù)據(jù)模塊包含靜態(tài)屬性和動態(tài)變量。靜態(tài)屬性即每個生產(chǎn)任務(wù)的基本信息，例如任務(wù)編號、物料編號、產(chǎn)品編號、在各機(jī)器上的加工時間等，這些屬性通過外部數(shù)據(jù)庫的數(shù)據(jù)為其賦值。動態(tài)變量主要包括：選擇加工的鍋爐、開始燒制物料的時間、物料燒制時長、鍋爐清洗時長、結(jié)束燒制物料的時間、離開鍋爐的時間、臨時存儲罐、進(jìn)入存儲罐的時間、離開存儲罐的時間、選擇加工的灌裝線、開始灌裝的時間、灌裝時長、切換灌裝工具的時長、結(jié)束灌裝的時間等。這些變量根據(jù)各任務(wù)智能體在仿真運行過程中的實時生產(chǎn)信息獲得相應(yīng)變量值，而不是模型運行前就決定好的。

(2)行為模塊主要通過狀態(tài)圖來展示任務(wù)智能體的狀態(tài)變化過程以及與其他智能體之間的協(xié)調(diào)邏輯。如圖3所示，當(dāng)鍋爐智能體處于空閑狀態(tài)時，會根據(jù)一定的調(diào)度規(guī)則選取生產(chǎn)任務(wù)進(jìn)行加工。當(dāng)某個任務(wù)被鍋爐智能體選取，會觸發(fā)該任務(wù)智能體從初始狀態(tài)進(jìn)入加工狀態(tài)。當(dāng)該任務(wù)在灌裝線上完成灌裝操作后，會向該任務(wù)智能體發(fā)送特定消息，任務(wù)智能體接收到該消息后，會觸發(fā)該任務(wù)智能體從加工狀態(tài)進(jìn)入最終狀態(tài)，即該任務(wù)的加工已經(jīng)全部完成。

2.3 鍋爐智能體

物料首先在鍋爐上進(jìn)行燒制，將所有鍋爐設(shè)置成鍋爐智能體，每個鍋爐智能體同樣包含數(shù)據(jù)模塊和行為模塊。

(1)數(shù)據(jù)模塊主要為靜態(tài)屬性和動態(tài)變量。靜態(tài)屬性主要包括：鍋爐編號、與之相連通的存儲罐集合等。動態(tài)變量主要包括：加工的生產(chǎn)任務(wù)、開始燒制的時間、物料編號、上一個任務(wù)的物料編號、鍋爐清洗時間、開始燒制時間、物料燒制時長、燒制完成時間等。

(2)行為模塊主要通過狀態(tài)圖來展示鍋爐智能體的狀態(tài)變化過程以及與其他智能體之間的協(xié)調(diào)邏輯。如圖4所示。

1)初始化操作，因為任務(wù)只能在部分鍋爐和部分生產(chǎn)線上加工，并且鍋爐、存儲罐和生產(chǎn)線之間存在著連接限制，所以當(dāng)任務(wù)處于某個加工階段時，需要對下一階段可進(jìn)行加工的機(jī)器動態(tài)更新。例如任務(wù)2可以在1號、2號、4號、6號、7號和8號鍋爐上進(jìn)行燒制，這些鍋爐各自連通著2個存儲罐；如果當(dāng)任務(wù)2被安排在鍋爐8上進(jìn)行燒制時，那么下一階段它只能在17號和18號存儲罐進(jìn)行臨時存儲；因為17號和18號存儲罐連接著2號、8號和10號灌裝線，盡管任務(wù)2能夠在2號、3號、8號和10號灌裝上進(jìn)行灌裝，但當(dāng)它被安排在8號鍋爐上燒制時，只能選擇2號、8號和10號灌裝線進(jìn)行灌裝。

2)鍋爐選擇未加工的任務(wù)進(jìn)行加工，若所有可以在這臺鍋爐上進(jìn)行加工的任務(wù)均已完成加工，則該鍋爐進(jìn)入最終狀態(tài)(完成)。

3)當(dāng)鍋爐找到需要加工的任務(wù)后，若這個任務(wù)的物料種類與緊前任務(wù)的物料種類不同，則需要在加工前清洗鍋爐。

4)鍋爐對物料進(jìn)行燒制。

5)物料燒制完成后，鍋爐將燒制好的物料轉(zhuǎn)移至可以連接的存儲罐中進(jìn)行臨時存儲，若不存在空置的存儲罐，則等待存儲罐空置；待物料轉(zhuǎn)移完成，再次回到第2)步，選擇可以加工的任務(wù)。

2.4 存儲罐智能體

任務(wù)在鍋爐上完成第一階段物料的燒制后，鍋爐將燒制好的物料轉(zhuǎn)移至空置且可連通的存儲罐中進(jìn)行臨時存儲。每個存儲罐智能體包含數(shù)據(jù)模塊和行為模塊。

(1)數(shù)據(jù)模塊包含靜態(tài)屬性和動態(tài)變量。存儲罐智能體的靜態(tài)屬性包括：存儲罐編號、存儲罐容量、與之相連通的灌裝線集合等。動態(tài)變量包括：存儲罐是否空置、物料進(jìn)入存儲罐的時間、物料離開存儲罐的時間等。

(2)行為模塊主要通過狀態(tài)圖來展示存儲罐智能體的狀態(tài)變化過程以及與其他智能體之間的協(xié)調(diào)邏輯。如圖5所示，當(dāng)鍋爐將燒制完的物料轉(zhuǎn)移至空置的存儲罐，觸發(fā)該存儲罐智能體由“空閑”狀態(tài)進(jìn)入“忙碌”狀態(tài)，鍋爐智能體也會再次返回到空閑狀態(tài)，尋找可以加工的任務(wù)。同時，該存儲罐Agent會根據(jù)一定的調(diào)度規(guī)則尋找可以對該任務(wù)進(jìn)行產(chǎn)品灌裝的灌裝線，并向該灌裝線智能體發(fā)送特定消息，從而觸發(fā)該灌裝線離開空閑狀態(tài)，進(jìn)行加工。等到灌裝完成之后，該存儲罐智能體由“忙碌”狀態(tài)再次回到“空閑”狀態(tài)。

2.5 灌裝線智能體

將每個灌裝線也設(shè)置成智能體，同樣包含數(shù)據(jù)模塊和行為模塊。

(1)數(shù)據(jù)模塊主要為靜態(tài)屬性和動態(tài)變量。靜態(tài)屬性主要包括：灌裝線編號、與之相連通的存儲罐集合等。動態(tài)變量主要包括：加工的生產(chǎn)任務(wù)、開始灌裝的時間、產(chǎn)品編號、上一個任務(wù)的產(chǎn)品編號、切換灌裝工具時間、開始灌裝時間、灌裝時長、灌裝完成時間等。

(2)行為模塊主要通過狀態(tài)圖來展示灌裝線智能體的狀態(tài)變化過程以及與其他智能體之間的協(xié)調(diào)邏輯。如圖6所示。

1)當(dāng)灌裝線智能體接收到存儲罐向其發(fā)送的特定消息時，表示需要開始灌裝任務(wù)，則離開閑置狀態(tài)。

2)生產(chǎn)線得到需要進(jìn)行灌裝操作的任務(wù)。

3)若該任務(wù)的產(chǎn)品種類與緊前任務(wù)的產(chǎn)品種類不同，則需要在加工前切換灌裝工具。

4)生產(chǎn)線對產(chǎn)品進(jìn)行灌裝。

5)灌裝完成后，該灌裝線智能體會向?qū)?yīng)的任務(wù)智能體發(fā)送特定消息，表示該任務(wù)已經(jīng)完成加工。任務(wù)智能體接收到灌裝線智能體發(fā)送的消息后，觸發(fā)該任務(wù)智能體從加工狀態(tài)進(jìn)入最終狀態(tài)。同時灌裝線智能體也會再次回到閑置狀態(tài)。

2.6 智能體間的協(xié)調(diào)機(jī)制

圖7展示了一個生產(chǎn)任務(wù)的加工過程中，4種智能體間的協(xié)調(diào)機(jī)制具體描述如下:

(1)外部數(shù)據(jù)輸入。調(diào)度開始時，根據(jù)數(shù)據(jù)庫中的生產(chǎn)任務(wù)數(shù)據(jù)，動態(tài)地生成相應(yīng)任務(wù)智能體群，一條生產(chǎn)任務(wù)數(shù)據(jù)源對應(yīng)一個任務(wù)智能體。根據(jù)數(shù)據(jù)庫中車間結(jié)構(gòu)數(shù)據(jù)，對相應(yīng)的鍋爐、存儲罐、灌裝線智能體的靜態(tài)屬性賦值。

(2)在調(diào)度開始后，各任務(wù)、鍋爐、存儲罐和灌裝線智能體獨立工作，但是相互之間又存在著協(xié)調(diào)機(jī)制，具體如下：①首先空閑的鍋爐智能體會按照一定的調(diào)度規(guī)則選擇可以加工的生產(chǎn)任務(wù)。當(dāng)鍋爐開始對該任務(wù)進(jìn)行生產(chǎn)時，會觸發(fā)該任務(wù)智能體從初始狀態(tài)進(jìn)行加工狀態(tài)。②當(dāng)任務(wù)在鍋爐上完成生產(chǎn)之后，會進(jìn)入與該鍋爐相連通的空置的存儲罐中。該鍋爐智能體重新返回到空閑狀態(tài)，再次尋找可以加工的任務(wù)。同時存儲罐智能體由空閑狀態(tài)進(jìn)入忙碌狀態(tài)。③此時，存儲罐智能體會按照一定的調(diào)度規(guī)則尋找可以為任務(wù)進(jìn)行第三階段加工的灌裝線，從而觸發(fā)該灌裝線智能體離開閑置狀態(tài)，開始加工。④當(dāng)灌裝線上完成產(chǎn)品的灌裝之后，該灌裝線智能體會向該任務(wù)智能體發(fā)送特定消息，從而觸發(fā)該任務(wù)智能體進(jìn)入最終狀態(tài)，即所有生產(chǎn)階段都已完成。灌裝線智能體也同時返回到閑置狀態(tài)。

3 調(diào)度規(guī)則簡介

由于實際生產(chǎn)環(huán)境中，受到各種加工條件的制約，伴隨著復(fù)雜的資源約束、工藝約束等,數(shù)學(xué)建模方法較難解決這類實際生產(chǎn)問題，能夠處理的問題規(guī)模也較小。而按照一定的調(diào)度規(guī)則將任務(wù)分配到各階段的機(jī)器上進(jìn)行加工，即使針對復(fù)雜的生產(chǎn)環(huán)境和較大規(guī)模的求解問題，也能夠快速生成合理的調(diào)度方案。

在仿真模型中，兩個生產(chǎn)階段的生產(chǎn)安排需要使用到調(diào)度規(guī)則。第一生產(chǎn)階段：將任務(wù)分配給鍋爐進(jìn)行物料的燒制；第二生產(chǎn)階段：將燒制好的任務(wù)分配給灌裝線進(jìn)行產(chǎn)品的灌裝。

SANTOS等[26]介紹了最短作業(yè)時間優(yōu)先(Shortest Process Time, SPT)規(guī)則和最長作業(yè)時間優(yōu)先(Longest Process Time, LPT)規(guī)則,SPT規(guī)則即作業(yè)時間最短的工件優(yōu)先,LPT規(guī)則即作業(yè)時間最長的工件優(yōu)先。這種基于優(yōu)先度的調(diào)度規(guī)則具有較強(qiáng)的通用性，經(jīng)常被用于求解大規(guī)模的現(xiàn)實調(diào)度問題，求解效率高且很容易實現(xiàn)，是混合流水車間調(diào)度問題的經(jīng)典調(diào)度規(guī)則。

基于此，在SPT和LPT規(guī)則基礎(chǔ)上，結(jié)合所研究工廠的現(xiàn)實約束，提出循環(huán)遍歷最短作業(yè)時間(Circle for Shortest Process Time,CSPT)規(guī)則和循環(huán)遍歷最長作業(yè)時間(Circle for Longest Process Time,CLPT)規(guī)則，應(yīng)用于第一生產(chǎn)階段；提出機(jī)器免切換且最短作業(yè)時間優(yōu)先(Free change machine and Shortest Process Time first, FSPT)規(guī)則和機(jī)器免切換且最長作業(yè)時間優(yōu)先(Free change machine and Longest Process Time first, FLPT)規(guī)則，應(yīng)用于第二生產(chǎn)階段。CSPT/CLPT和FSPT/FLPT在3.1和3.2節(jié)中進(jìn)行具體說明。

3.1 第一生產(chǎn)階段

第一生產(chǎn)階段為將任務(wù)分配給鍋爐進(jìn)行物料的燒制。在這一階段，提出了CSPT規(guī)則和CLPT規(guī)則；

(1)CSPT規(guī)則 當(dāng)鍋爐空閑時，會去尋找未加工且可以在這臺鍋爐上加工的任務(wù)，選擇邏輯為：首先遍歷任務(wù)列表，尋找在可加工的鍋爐中，在該鍋爐上加工時間最短的任務(wù)。若不存在這樣的任務(wù)，則選擇倒數(shù)第二短的，依次類推，直到不存在可以在該鍋爐上加工的任務(wù)。

(2)CLPT規(guī)則 當(dāng)鍋爐空閑時，會去尋找未加工且可以在這臺鍋爐上加工的任務(wù)，選擇邏輯為：首先遍歷任務(wù)列表，尋找在可加工的鍋爐中，在該鍋爐上加工時間最長的任務(wù)。若不存在這樣的任務(wù)，則選擇倒數(shù)第二長的，依次類推，直到不存在可以在該鍋爐上加工的任務(wù)。

3.2 第二生產(chǎn)階段

第二生產(chǎn)階段為將燒制好的任務(wù)分配給灌裝線進(jìn)行產(chǎn)品的灌裝。由于灌裝線上灌裝不同種類的產(chǎn)品需要先切換灌裝工具，而SPT和LPT規(guī)則都只是考慮了加工時間，沒有考慮切換時間。將切換時間考慮在內(nèi)，基于SPT、LPT規(guī)則提出了FSPT和FLPT規(guī)則：

(1)FSPT規(guī)則 在當(dāng)時處于空閑狀態(tài)的灌裝線中首先選擇不需要進(jìn)行切換工具的灌裝線，在其中選擇加工時間最短的；若空閑的灌裝線均需要切換工具，則選擇加工時間和切換時間的和最短的灌裝線。

(2)FLPT規(guī)則 在當(dāng)時處于空閑狀態(tài)的灌裝線中首先選擇不需要進(jìn)行切換工具的灌裝線，在其中選擇加工時間最長的；若空閑的灌裝線均需要切換工具，則選擇加工時間和切換時間的和最長的灌裝線。

4 仿真結(jié)果分析

采用AnyLogic 8.5 Professional作為多智體(multi-Agent)建模工具，根據(jù)某液體洗護(hù)用品生產(chǎn)廠商實際生產(chǎn)過程建立仿真模型，并選用了實際生產(chǎn)中的443個生產(chǎn)任務(wù)進(jìn)行仿真分析。

在仿真模型中，兩個生產(chǎn)階段的生產(chǎn)安排需要使用到調(diào)度規(guī)則。在兩個生產(chǎn)階段分別應(yīng)用SPT規(guī)則和LPT規(guī)則，得到4種調(diào)度方案：SPT-SPT,SPT-LPT,LPT-SPT和LPT-LPT。

在SPT和LPT規(guī)則基礎(chǔ)上，結(jié)合所研究工廠的現(xiàn)實約束，針對第一生產(chǎn)階段提出了CSPT和CLPT規(guī)則，針對第二生產(chǎn)階段提出了FSPT和FLPT規(guī)則，從而得到了4種新的調(diào)度方案：“CSPT-FSPT”,“CSPT-FLPT”,“CLPT-FSPT”和“CLPT-FLPT”。將這4種新的調(diào)度方案與基于SPT和LPT規(guī)則得到的四種調(diào)度方案進(jìn)行比較。

基于某液體洗護(hù)用品生產(chǎn)企業(yè)實際生產(chǎn)任務(wù)，隨機(jī)抽取其中的100個、200個、300個和400個生產(chǎn)任務(wù)，進(jìn)行仿真實驗。實驗結(jié)果主要以最大完工時間這一指標(biāo)作為衡量標(biāo)準(zhǔn)，并結(jié)合相應(yīng)的生產(chǎn)數(shù)據(jù)分析調(diào)度規(guī)則使用效果，生產(chǎn)數(shù)據(jù)包括：鍋爐總閑置時間、灌裝線總等待時間、灌裝線總閑置時間。針對不同規(guī)模的實驗各重復(fù)5次，并計算相應(yīng)實驗數(shù)據(jù)的平均值和標(biāo)準(zhǔn)差。實驗結(jié)果如表1～表4所示。

表1 各組實驗的最大完工時間的平均值和標(biāo)準(zhǔn)差

表2 各組實驗的鍋爐總閑置時間的平均值和標(biāo)準(zhǔn)差

表3 各組實驗的灌裝線總等待時間的平均值和標(biāo)準(zhǔn)差

表4 各組實驗的灌裝線總閑置時間的平均值和標(biāo)準(zhǔn)差

表1主要以最大完工時間為衡量標(biāo)準(zhǔn)，對比了不同調(diào)度規(guī)則的使用效果。從表1可以看出，在第一生產(chǎn)階段采用新調(diào)度規(guī)則CSPT和CLPT規(guī)則，在第二生產(chǎn)階段采用新調(diào)度規(guī)則FSPT和FLPT規(guī)則，所產(chǎn)生的4種新的調(diào)度方案“CSPT-FSPT”,“CSPT-FLPT”,“CLPT-FSPT”和“CLPT-FLPT”。相比于基于SPT和LPT規(guī)則產(chǎn)生的4種調(diào)度方案“SPT-SPT”,“SPT-LPT”,“LPT-SPT”和“LPT-LPT”，這4種調(diào)度方案的最大完工時間都大大降低。并且基于新規(guī)則所得到的“CSPT-FSPT”調(diào)度方案的最大完工時間最短，明顯優(yōu)于基于SPT和LPT規(guī)則所產(chǎn)生的4種調(diào)度方案的最大完成加工時間。這說明了基于SPT和LPT規(guī)則，結(jié)合所研究的實際生產(chǎn)調(diào)度問題的生產(chǎn)工藝和加工約束等條件，提出的CSPT/CLPT和FSPT/FLPT規(guī)則對于降低總生產(chǎn)時間是有效的。

由于當(dāng)鍋爐完成緊前任務(wù)的加工后，會立即進(jìn)入緊后任務(wù)的加工，緊前任務(wù)與緊后任務(wù)之間不存在等待。只有當(dāng)鍋爐完成了安排在該鍋爐上的所有加工任務(wù)，而其他鍋爐仍處于加工狀態(tài)時，該鍋爐才會閑置?！板仩t總閑置時間”就是指鍋爐處于閑置狀態(tài)時，等待這一階段的所有鍋爐完成加工任務(wù)的時間之和。但是在灌裝線上，任務(wù)的灌裝并不一定是連續(xù)進(jìn)行的。緊前任務(wù)完成灌裝時，該灌裝線上的緊后任務(wù)并不一定完成了上一階段的加工，因而需要等待緊后任務(wù)在上一階段的加工任務(wù)完成之后，才能在該灌裝線上進(jìn)行下一階段的加工，從而產(chǎn)生了灌裝線上的等待時間。因此“灌裝線總等待時間”為10條灌裝線上緊前任務(wù)與緊后任務(wù)之間的等待時間之和；“灌裝線總閑置時間”是指灌裝線處于閑置狀態(tài)時，等待這一階段的所有灌裝線完成加工任務(wù)的時間之和。

從表2～表4可以看出，采用這4種新的調(diào)度方案“CSPT-FSPT”,“CSPT-FLPT”,“CLPT-FSPT”和“CLPT-FLPT”，鍋爐上的總閑置時間降低了，灌裝線上的總等待時間和總閑置時間也降低了。說明提出的CSPT/CLPT和FSPT/FLPT規(guī)則對于均衡各機(jī)器上的工作量也是有效的。

通過上述實驗數(shù)據(jù)對比發(fā)現(xiàn)，無論是以最大完工時間作為衡量指標(biāo)還是以各機(jī)器的利用率作為衡量指標(biāo)，本文所提出的新的調(diào)度規(guī)則與SPT規(guī)則和LPT規(guī)則相比都具有更好的表現(xiàn)。這是因為基于SPT和LPT規(guī)則所制定的調(diào)度方案，是一種按照工件加工時長進(jìn)行排序所形成的一種固定的、靜態(tài)的方案。這種靜態(tài)的分配法則，可能會出現(xiàn)一個任務(wù)完成了某一階段的加工之后，由于在下一階段機(jī)器上的排序靠后而需要等待的情況；也可能會出現(xiàn)一個機(jī)器上分配的任務(wù)較多，一個機(jī)器上分配任務(wù)較少，任務(wù)量的不均衡導(dǎo)致的機(jī)器產(chǎn)能浪費的情況等。而本文提出的調(diào)度規(guī)則利用多智能體建模的仿真技術(shù)，可以模擬現(xiàn)實中實時的生產(chǎn)情況，根據(jù)實時信息，在機(jī)器空閑時為其選擇合適的生產(chǎn)任務(wù)，是一個動態(tài)選擇的過程。這種動態(tài)選擇過程能夠規(guī)避基于SPT和LPT規(guī)則制定的靜態(tài)排序方案所帶來的弊端，更好地均衡機(jī)器上的任務(wù)量，能夠更好地銜接任務(wù)在不同加工階段上生產(chǎn)的連續(xù)性，因而表現(xiàn)出更好的性能。

5 結(jié)束語

本文利用仿真的方法來研究混合流水車間調(diào)度問題，研究對象是某液體洗護(hù)用品生產(chǎn)企業(yè)。利用AnyLogic中基于智能體的建模方法，將生產(chǎn)任務(wù)、鍋爐、存儲罐和灌裝線均視為參與調(diào)度過程的Agent實體。根據(jù)生產(chǎn)流程建立了仿真模型，可以有效地模擬工廠的實際生產(chǎn)流程。

在仿真模型中，兩個生產(chǎn)階段的生產(chǎn)安排需要使用到調(diào)度規(guī)則。第一生產(chǎn)階段：將任務(wù)分配給鍋爐進(jìn)行物料的燒制；第二生產(chǎn)階段：將燒制好的任務(wù)分配給灌裝線進(jìn)行產(chǎn)品的灌裝。

由于實際生產(chǎn)問題帶有各種復(fù)雜的限制條件，一些傳統(tǒng)的調(diào)度規(guī)則很難直接運用于該問題之中。本文基于SPT規(guī)則和LPT規(guī)則提出了新的調(diào)度規(guī)則，CSPT/CLPT規(guī)則(應(yīng)用于第一生產(chǎn)階段)和FSPT/FLPT規(guī)則(應(yīng)用于第二生產(chǎn)階段)。

通過實驗發(fā)現(xiàn)，基于CSPT/CLPT規(guī)則和FSPT/FLPT規(guī)則的調(diào)度方案相比于基于SPT/LPT規(guī)則的調(diào)度方案，最大完工時間得到了大幅度減少，并且機(jī)器上的任務(wù)量也更為均勻。其中“CSPT-FSPT”調(diào)度方案，即第一生產(chǎn)階段采用CSPT規(guī)則，第二生產(chǎn)階段采用FSPT規(guī)則的調(diào)度方案的最大完工時間最短。

在未來的研究中，可以進(jìn)一步將諸如機(jī)器損壞等的動態(tài)事件考慮到調(diào)度問題中，使得對該問題的研究更加貼合實際生產(chǎn)情況。