考慮人員裝卸時間的作業車間調度問題

張維存，李悅悅，左天帥

（河北工業大學 經濟管理學院，天津 300401）

0 引言

隨著市場競爭的加劇，產品需求趨于多樣化，現代制造正面臨單件、小批量混合生產類型的挑戰[1]。為滿足需求，智能制造逐漸被引入到復雜的作業車間調度問題中，工業機器人與自動化設備的應用已經成為未來制造業的發展趨勢[2]，但是人類仍具有不可替代的解決突發問題的能力和柔性，所以我們應該重新審視人員與自動化設備之間的合作關系[3]。在此背景下，研究具備自動化設備生產條件下的人員調度問題依然具有重要的現實意義。

在作業車間生產環境下，加工設備的自動化可以實現“一人多機”的并行工作方式，即人員只參與工件的裝卸過程而設備自動對工件進行加工。這種模式使人機配比更加靈活，有利于縮短產品生產周期、降低總成本和提高資源利用率。

在具備自動化設備條件下的人員調度問題方面，學者們做了相應的研究。Khintchine A[4]基于排隊論中G/G/1模型對一人多機問題進行了建模，并分析了基本的人機干涉問題。Yang等[5]研究了一人服務多臺并行機器的一人多機模型，并分別基于閉環排隊網絡和開環排隊網絡模型進行建模求解。楊軍等[6]研究了一人多機看管問題中的人員調度問題，并采用層次序列法對人員調度數學模型進行了求解。Sabar M等[7]研究了一種基于多智能體的多產品裝配中心動態環境下的人員調度問題，并通過模擬退火算法求解。BZ Xu等[8]提出了一種考慮并行性的以交貨期為目標的人員調度模型，證明了在人員調度中考慮機器自動能力和人員靈活性可以有效地提高車間調度效率。總的來說，國內外學者們對考慮設備自動化的人員優化調度問題進行了許多前沿性的研究，但是考慮人員參與裝卸操作的作業車間調度問題卻沒有相關的文獻。

在解決生產系統中的人員調度問題方面，眾多專家學者也做了廣泛的研究。Pan Q K等[9]提出了兩階段啟發式算法來解決人員調度問題。SY Lin等[10]提出了一種混合粒子群優化算法，用于求解流水車間雙目標人員分配問題。Shahnazari P等[11]采用粒子群優化和精英禁忌搜索兩種啟發式算法求解多技能人員調度問題。Azadeh等[12]利用模糊數據包絡分析和模糊計算機仿真方法優化作業車間中的人員調度問題。Alexander等[13]提出了一種基于分散搜索和路徑重新鏈接的啟發式算法來解決流水車間的人員調度與作業調度問題。Park J等[14]利用一種將遺傳算法、仿真和數據包絡分析結合來選擇最優算子分配方案的綜合方法來解決制造系統中人員調度問題。Behnamian等[15]提出一種基于可變鄰域搜索的群體競爭算法，用于解決混合流水車間人員調度問題。林仁等[16]在分析復雜制造任務特點的基礎上，利用自適應非支配排序遺傳算法求解考慮人員柔性的人員調度模型。Mencia等[17]等利用局部搜索和禁忌搜索算法求解多人員附加資源類型的作業車間調度模型?？梢?，國內外學者對人員調度問題的解決方法做了大量的研究，但是運用人工蜂群算法解決人員調度問題的文獻卻很少見。另一方面，人工蜂群算法已廣泛應用于生產調度領域[18～20]，并被證明是一種求解作業車間調度問題的有效方法[21]。

本文在考慮人員執行裝卸作業的基礎上，建立了自動化作業車間環境下“一人多機”的人員與作業并行集成調度模型，并設計了改進人工蜂群算法，以克服標準人工蜂群算法參數設置復雜、易早熟、局部搜索能力弱等缺點。

1 數學模型與問題分析

1.1 問題描述

n個工件{J1，J2，…，Jn}在m臺自動化機床{M1，M2，…，Mm}上加工，由w個人員{P1，P2，…，Pw}完成工件的裝、卸作業。工件Ji包括ni道工序Oij（j=1，2，…，ni），每道工序Oij對應一臺機床Mk（k=1，2，…，m）。人員Pa（a=1，2，…，w）在設備Mk和設備Mh之間的移動時間為tPkh。調度過程為，人員Pa對工序Oij進行裝載，設備Mk對工序Oij的自動化加工緊隨其后，加工完成后人員Pγ對工序Oij進行卸載，直到最后一項作業完成。每個工序包含裝載-加工-卸載三道作業，所以Z11＜V11＜X11＜...＜Zij＜Vij＜Xij＜...＜Znni＜Vnni＜Xnni為工件Ji的實際作業順序，其中Zij、Vij、Xij分別代表工序Oij的裝、卸、加工作業，Zij＜Vij表示Zij在Vij之前完成。調度的總目標為分配對裝卸作業進行操作的人員及加工作業在設備上執行的先后順序，使最大完工時間最小化。

假設條件：1）每臺機床的緩沖區足夠大；2）不考慮工件搬運時間；3）每個人員、每臺機床只能同時處理一個工件；4）工件在機床上被處理時不允許中斷；5）工件無優先級限制；6）不考慮機床故障情況；7）所有機床、人員零時刻可用。

1.2 數學模型

式(1)表示目標是最小化所有工件尾工序卸載結束時間的最大值；式(2)表示工序裝載后馬上進行加工；式(3)工序的裝載開始時間為人員到達時間、上一工序卸載完成時間和對應設備最早可用時間中的最大值；式(4)表示工序的開始卸載時間為設備加工完成時間和人員最早到達時間中的最大值；式(5)～式(8)表示人員先后對不同設備進行操作的時間關系。

2 改進的人工蜂群算法

2.1 問題與算法分析

由1.1節問題可知，在考慮人員裝卸時間的人員調度及作業車間調度問題中，每個工序存在裝載、加工和卸載三項作業，且加工作業緊隨裝載作業后，所以，分配各裝、卸作業人員及確定裝、卸作業執行的先后順序是解決該問題的關鍵。在此基礎上根據相應的時間信息計算各工序相應操作的開始和結束時間，并尋求最大完工時間最小的調度方案。因此，可以將本文研究的問題整理成兩個相關的子問題：1）分配裝、卸作業的人員；2）確定各裝、卸作業的先后順序。

人工蜂群算法[22]（Artificial Bee Colony algorithm，ABC）是將待優化問題編碼成蜜源位置，并基于蜂群智能搜索行為的優化算法。ABC算法結構簡單，對解空間的搜索和開發能力強，收斂速度快，受到很多學者的研究和關注，已成功應用于作業車間調度問題。為解決標準ABC算法在復雜問題優化方面易陷入局部最優、參數設置過多和搜索效率低等問題，本文僅引入引領蜂與跟隨蜂兩種蜂群，并利用兩種蜂群的位置信息共享和身份轉換的方式尋優，在減少參數設置的基礎上提高了算法的求解精度和搜索效率。

2.2 算法過程

算法運行前，只需設定唯一參數種群規模為N，并令引領蜂規模和跟隨蜂規模均為N/2，之后進入算法過程。

步驟1：初始化種群。采用二維蜂群數組，種群規模為第一維數組，第二維數組存儲操作作業，操作作業針對裝、卸兩種類型。給每一個引領蜂個體中的作業優先權值賦隨機數（詳見2.3節）。

步驟2：解碼每一只引領蜂的位置信息，將對應的最優目標函數值fbi傳遞給相應的引領蜂個體，并利用公式(9)計算每只引領蜂對應的適應值fitbi。

步驟3：利用式(10)計算Nb只引領蜂的累計適應值fitb，再利用式(11)根據每只引領蜂個體適應值在累計適應值中的占比分配Nb只引領蜂對應的跟隨蜂數量Nub。

步驟4：Nb只引領峰通過與其對應的跟隨蜂之間的協調進化得到自身新的適應值，具體過程如下（令引領蜂計數器b和跟隨蜂計數器u初值為1）：

步驟4.1：更新下層跟隨蜂位置。選定一只引領蜂cb，將位置共享給其下層跟隨蜂cbu即第b只引領蜂的第u只跟隨蜂根據式(12)更新位置位置；

其中，L為個體編碼長度

步驟4.2：更新引領蜂適應值。解碼跟隨蜂cbu的位置信息并得出相應的適應值fitui。判斷引領蜂cb適應值fitbi與跟隨蜂cbu適應值fitui的大小，若fitui＞fitbi，則令fitui=fitbi，并用跟隨蜂cbu位置更新引領蜂cb的位置，否則和引領蜂cb的位置不變。

步驟4.4：若b=Nb，表示Nb只引領蜂位置更新完成，轉入步驟5，否則b=b+1，轉入步驟4.1。

步驟5：引領蜂群進化，并根據最優適應值更新狀態調整引領蜂和跟隨蜂種群規模，具體過程如下：

步驟5.1：將Nb只引領蜂的適應值按照大小進行排序，得到最優適應值fit'；

步驟5.2：利用式(13)，將引領蜂（b=2，3，…，Nb）的位置與最優引領蜂位置進行差分計算，調整當前引領蜂向最優引領鋒位置靠近。

步驟5.3：比較最優適應值fit'與全局最優適應值fit。若fit'＞=fit，將適應值最差的引領蜂轉化成跟隨蜂，即Nb=Nb-1且Nu=Nu+1，此時若Nb=1算法結束，輸出最優結果和調度方案，否則轉入步驟2。若fit'＜fit。令fit=fit'并更新最優引領蜂位置qlbest（l=1，2，…，L），將引領蜂和跟隨蜂恢復到原有規模，即Nb=Nu=N/2，轉入步驟2。

2.3 編碼設計

編碼采用基于裝、卸兩種操作的方式，個體中的每個基因位代表裝、卸作業。個體長度是每個基因位包含的信息有工件號i、工序號j、裝卸作業標識β（β=0時標示裝載作業，β=1時標示卸載作業）、作業執行人員pa、作業優先權值ql、作業開始時間和作業結束時間。如圖1所示。

圖1 基因編碼設計圖

其中工件號i、工序號j、裝卸作業標識β作為基因位的標識，可以對個體中基因進行定位。作業執行人員Pa是解碼中進行人員調度的結果，作業開始時間和作業結束時間是作業排序后依據作業執行時間計算的結果。作業優先權值ql采用賦實數方式，是解碼過程中確定裝卸任務排序的依據，也是人工蜂群算法進化處理的對象。這種編碼方式更有利于算法運行過程中的進化計算，進而提高解決問題的效率。

2.4 解碼過程

解碼過程依據作業優先權值ql選擇作業對象，作業針對裝、卸兩種形式，自動化加工緊隨裝載作業之后。解碼開始前，所有人員初始位置固定且相同。解碼過程中依次得到對作業進行操作的人員與各設備上作業的先后順序，最終得到總完工時間最小的作業排序方案。

裝載作業被選為可解碼對象需要滿足以下條件：1）上道工序卸載作業Xi（j-1）已被解碼；2）作業Zij未被解碼。卸載作業被選為可解碼對象需要滿足以下條件：1）工序Oij已被加工完成；2）作業Xij未被解碼。滿足以上條件的裝卸作業構成可解碼作業集合Ω。具體解碼步驟如下：

步驟1：逐步遍歷各基因位，將可解碼的裝卸作業放入可解碼作業集合Ω，可解碼作業集合包括裝、卸兩種作業形式。

步驟2：判斷可解碼集合Ω是否為空，若為空，則進入步驟5。若不為空，選擇優先權值最小的作業作為解碼對象。若選中的作業需要執行裝載作業則進入步驟3，否則進入步驟4。

步驟3：選擇工序裝載作業的人員，計算工序裝載及加工的開始和完成時間。

步驟3.1：選擇作業人員。遍歷所有人員，選擇到達設備Mk對工序（i*，j*）裝載作業（i*，j*，0）時間最早的人員對該工序執行裝載作業，即，并同時更新該人員的位置信息為Mk。

步驟3.2：根據式(3)和式(13)分別計算工序Oij裝載開始時間和結束時間。

步驟3.3：根據式(2)和式(14)分別計算工序Oij的加工開始時間和結束時間。

步驟4：選擇工序卸載作業的人員，計算工序卸載的開始和結束時間。

步驟4.1：選擇作業人員。遍歷所有人員，選擇到達設備Mk對工序（i*，j*）卸載作業（i*，j*，1）時間最早的人員對該工序執行裝載作業，即，并同時更新該人員的位置信息為Mk。

步驟4.2：根據式(4)和式(14)分別計算工序Oij的卸載開始時間和結束時間。

步驟5：根據式(1)計算調度方案的目標值，并輸出最優調度方案。

3 應用實例

3.1 并行工作調度模型的有效性分析

為說明并行工作調度模式的有效性，選擇文獻[23]中的工作模式進行比較。文獻[23]以總調度時間最小為目標，建立了每個設備加工過程均由人員協助完成的具有附加資源類型的車間調度問題，擴展了經典的作業車間問題。以加工5種工件為例進行說明。

某機械加工廠在期初有2名工人、5臺不同類型的自動化設備可供調度，人員在設備間移動時間如表1所示（其中M0表示人員的初始位置）。該工廠有一個需加工5種不同類型工件的訂單，物料加工信息如表2（其中Ji：工件號，Oij：工序號，M：設備，t：加工時間，Zt：裝載時間，Xt：卸載時間，時間單位：小時）所示。

表1 人員在設備間移動時間信息表

表2 物料加工信息表（一）

采用文獻[23]的生產調度模型對該問題進行求解，為使表達更加直觀，將調度結果轉變為任務加工甘特圖，并以“人員編號-設備編號”形式標明對工件進行加工的人員和設備（如“1-2”為人員1輔助設備2進行加工），如圖2所示。

圖2 文獻[23]策略下的任務加工甘特圖

在該調度模型中，單個工件的加工時間等同于并行調度模型中對應工件的裝載、加工和卸載總時間，并且人員參與加工全過程，所有工件加工完成時，總的調度時間為128小時。為進一步縮短總調度時間，采用本文調度模式對該問題進行求解，調度結果以甘特圖形式展出（如“M2”表示在設備2上完成加工，左右兩側分別代表對該工序進行裝、卸的人員），如圖3所示。

圖3 并行工作調度策略任務加工甘特圖

在該并行工作調度模型中，工人完成裝、卸作業后離開，設備對工件自動化加工，實現了人員與設備的并行。由圖3可知，并行工作模式求解得到的總調度時間比文獻[23]的調度策略提前35小時，總調度時間縮短了27.34%，使得客戶訂單可以更早的配送，因此并行工作調度模式更加有效。

3.2 算法主要參數確定

在帶有身份轉換機制的人工蜂群算法（Improved-ABC，I-ABC）中，唯一需要確定的參數就是種群規模N。為確定合適的種群規模N，以5臺加工設備、5名工人為資源基礎，加工10種工件為例，（人員在設備間移動時間信息見表1，各物料屬性如表3所示）。在不同種群規模下，即N取50，100，150，……，900不同的值，對I-ABC的有效性進行驗證。每組實驗運行15次，分別取每次實驗的平均值作為種群變化的優值，并繪制出優值變化圖、優值方差變化圖以及運行時間圖（如圖4、圖5及圖6所示，其中圖4縱坐標表示優化結果，單位：小時；圖6縱坐標表示運行時間，單位：秒）。

表3 物料加工信息表（二）

圖4 優值變化圖

圖5 優值方差變化圖

圖6 運行時間變化圖

據圖4可知，種群規模達到600時，優值曲線趨于平緩且由圖5可看出，種群規模達到600時優值方差波動變小。由圖6可見，N在600～700之間，運行速度相對較快，N大于700時，算法運行時間較長，因此種群規模設置在600～700之間較為合理。本文采用600作為實驗參數。

3.3 算法的有效性驗證

為進一步驗證I-ABC算法的有效性，選擇標準人工蜂群算法（ABC）、文獻[24]的改進差分算法進行對比實驗。文獻[24]以加工時間最短為目標，設計了改進差分算法用于解決作業車間調度問題，并得出了較好的調度方案。實驗中設定每算法種群規模均為600，ABC的引領蜂局部尋優次數為20，循環次數為200。每種算法運行10次，算法比較運行結果如表5所示。實驗中測例數據是在文獻[25]中10組測例的基礎上增加了裝卸操作時間得來的，增加部分如表4所示。Z1、Z2、Z3分別表示I-ABC、S-ABC與文獻[24]算法運行10次后的平均值。GPA1表示ABC與I-ABC之間的差值比，計算方式為GPA1=（Z2-Z1）/Z2×100%。同理，GPA2表示I-ABC與文獻[24]算法之間的差值比，計算方式為GPA1=（Z3-Z1）/Z3×100%。如果GPA1與GPA2均為正值，則說明I-ABC優于ABC與文獻[24]算法。

表4 測例數據表

表4（續）

表5 實驗結果表

表5（續）

從表4中可以看出，在10種測例規模下GPA1、GPA2的值均為正數，表明在同種資源條件下，相比較ABC與文獻[24]的改進差分算法，運用I-ABC算法可以得到更優的作業車間調度方案。這說明I-ABC在減少參數設置的同時，提高了算法的尋優精度和效率，在求解作業車間調度問題方面具有更高的應用價值。

4 結語

面向自動化車間生產的Job Shop調度問題中，在考慮人員裝卸時間的情況下，研究“一人多機”的并行工作調度模型，是對Job Shop調度問題研究的進一步補充和完善。本文研究表明：

1）考慮人員裝卸時間的情況下，“一人多機”的并行工作生產模式較傳統調度模式有縮短生產時間、提高生產效率的優勢。

2）通過不同規模測例實驗比較，說明改進人工蜂群算法在解決Job Shop調度問題上較標準的人工蜂群算法和改進差分算法具有優越性。

此類生產調度問題的解決，首先可以縮短產品的生產周期，提前產品交貨期，更好的滿足客戶需求。其次，從企業角度來說，客戶對產品的個性化需求越來越強烈，當企業收到客戶訂單時，可以在現有資源下更快的完成訂單，從而提升企業的競爭力。