毛永年，唐秋華，張利平

1.武漢科技大學冶金裝備及其控制教育部重點實驗室，湖北 武漢，430081; 2.武漢科技大學機械傳動與制造工程湖北省重點實驗室，湖北 武漢，430081)

Hoist(行車)調度問題[1]來源于以制造印刷電路板為代表的電鍍企業(yè)，其產品通常需要經(jīng)歷多個工作站(鍍槽)，工件在這些工作站中的處理時間有一定的變動范圍(即時間窗口)。加工時間較長的工藝階段常配有多個功能相同的工作站，以消除此階段的生產瓶頸，提高系統(tǒng)整體加工效率。同時，為了克服由運輸設備造成的生產瓶頸，在同一條軌道上通常安裝有多個Hoist以協(xié)同完成線上運輸作業(yè)，受計算機編程控制的Hoist必須在給定的時間窗口內，將工件從當前工作站轉移到下一工序所在工作站。自動化電鍍生產線一般采用周期性生產模式，Hoist在每一個生產周期內執(zhí)行相同的搬運作業(yè)序列以完成大批量工件的生產。此外，電鍍企業(yè)常常需要將多種不同類型產品按照一定的比例投產才能達到設計產能，實現(xiàn)較高的設備使用率，加快訂單的響應速度。因此，面向產品投產比例的調度模式在電鍍生產線上應用較廣泛。

針對Hoist調度問題的研究主要集中在周期性調度領域。Phillips等[2]提出了該問題的第一個周期性調度模型。Liu等[3]構建一個混合整數(shù)線性規(guī)劃(MILP)模型，以解決存在重入工藝和并行工作站的周期性調度問題。Lei等[4]指出，在一個生產周期內同時加工多個工件可以提升系統(tǒng)的平均產出，這種模式被稱為“多度周期調度”(multi-degree cyclic scheduling)。Zhou等[5]建立了解決該類問題的MILP模型。El Amraoui等[6]研究由工件加工時間窗口帶來的生產瓶頸問題，提出了考慮并行工作站的MILP模型，其在一個生產周期內只涉及兩個不同類型的工件。Zhao等[7]研究基于產品投產比例的單Hoist調度問題，考慮了并行工作站使用能力約束。

增加Hoist的數(shù)量可以顯著提高電鍍生產線的生產效率。Yang等[8]將電鍍生產線劃分為若干個互不重疊的區(qū)域，且每個Hoist只負責一個區(qū)域內的搬運作業(yè)，然后使用模擬退火算法求解最佳區(qū)域劃分方法。Leung等[9]提出了多Hoist周期性調度問題的MILP模型。針對具有雙向工件運輸流的電鍍生產線，Jiang等[10]分析了多類Hoist避碰條件，構建了該問題的MILP模型并發(fā)展了基于混合整數(shù)規(guī)劃的分支定界算法。針對多Hoist多度周期調度問題，Li等[11-12]也采用區(qū)域劃分的方法構建MILP模型。

最近，Mao等[13]研究了運行區(qū)域存在重疊的多Hoist多度周期調度問題，構建了工件流為單向情形時的最優(yōu)化MILP數(shù)學模型?；谠撗芯?，本文將問題擴展到考慮產品投產比例的多工件調度領域，即在一個周期內考慮多個具有相同工藝路線的工件，區(qū)別于文獻[13]，本文研究的各工件的加工時間窗口參數(shù)可能相同也可能不同，各類型工件有一定的投產比例，并且加工時間較長的瓶頸工序配有并行工作站。針對此類實際生產問題，本文采用啟發(fā)式策略實現(xiàn)多個不同類型工件在并行工作站上的分配，進而構建混合整數(shù)規(guī)劃模型。該模型同時考慮時間窗口約束、工作站使用能力約束和Hoist無碰撞約束。最后，以某印刷電路板制造企業(yè)的生產實例驗證所建數(shù)學模型的應用價值。

1 問題描述與符號定義

本文研究如圖1所示的電鍍生產線，包括H個Hoist、n+ω個鍍槽。在鍍槽上方的軌道上，多個Hoist同時運行，Hoist的編號從左至右依次為1,2,…,H；工作站的編號從左至右依次為0,1,2,…,n+ω，其中工作站0同時為裝載站和卸載站，各鍍槽呈線性排列，鍍槽n至n+ω具有相同的工藝處理功能，即參數(shù)ω為線上并行工作站的數(shù)量。每個工件自工作站0進入生產線，依次經(jīng)歷n個處理工序后，從工作站0離開，因此，每個工件包含n個工藝處理階段。裝載站和卸載站的容量設為無限大，工作站1至n+ω為單工件處理能力機器，即在任何時候最多只能同時加工一個工件。由于工作站之間沒有緩沖設施，工件在滿足時間窗口約束條件下完成當前階段的加工后，須由Hoist將其從當前工作站取出，并運送到下一階段所在的工作站。

圖1 典型的電鍍生產線布局

由于所研究的各類型工件具有相同的工藝路線，本文根據(jù)進入時間的先后順序將周期內的各工件依次編號為1,2,…,K。因此，面向產品投產比例的多Hoist調度問題可以用3個輸入?yún)?shù)n、H、K來描述。

為了方便模型的表述，定義如下參數(shù)：

(1)mk,i：工件k的第i個階段所在的工作站編號，1≤k≤K，0≤i≤n+1。

(2)搬運作業(yè)[k,i]：工件k完成第i個階段的加工后，Hoist將工件從當前工作站取出，然后將其搬運到第i+1個階段所在工作站，并卸載到該工作站上的全過程，1≤k≤K，0≤i≤n。

(3)Ci：加工第i個工藝階段所能使用的工作站總數(shù)量。

(4)ak,i：工件k的第i個階段的加工時間下限，1≤i≤n。

(5)bk,i：工件k的第i個階段的加工時間上限，1≤i≤n。

(6)dk,i：執(zhí)行搬運作業(yè)[k,i]所需的時間，其中包括Hoist將工件從工作站mk,i中取出的時間μ、Hoist將工件k從工作站mk,i運輸?shù)絤k,i+1所需的時間，以及Hoist將工件k放入工作站mk,i+1的時間η，1≤k≤K，0≤i≤n。

(7)φ([k,i],[r,j],θ)：當搬運作業(yè)[k,i]的優(yōu)先級高于搬運作業(yè)[r,j]時，執(zhí)行此兩項搬運作業(yè)的最小間隔時間，其中θ=g-h，1≤h、g≤H，1≤k、r≤K，0≤i、j≤n，h與g分別為執(zhí)行搬運作業(yè)[k,i]與[r,j]的Hoist編號。參數(shù)φ([k,i],[r,j],θ)用以避免Hoist之間的潛在碰撞沖突，其推導過程請參閱文獻[10]和文獻[13]。

(8)M：足夠大的正數(shù)；ε：足夠小的正數(shù)。

該問題的決策變量為：

(1)T：周期長度。

(2)sk,i：搬運作業(yè)[k,i]的開始時間，1≤k≤K，0≤i≤n。

(3)?k,i：工件k的第i個階段所使用的機器數(shù)量，1≤k≤K，1≤i≤n。

(4)zk,i,h：

1≤k≤K， 0≤i≤n， 1≤h≤H。

(5)yk,i;r,j：

1≤k、r≤K， 0≤i、j≤n。

2 混合整數(shù)規(guī)劃模型的建立

面向產品投產比例的多Hoist調度混合整數(shù)規(guī)劃模型構建如下：

minT

s.t.：

sk,i≥0， 1≤k≤K，1≤i≤n

(1)

sk,i+ε≤T， 1≤k≤K，1≤i≤n

(2)

s1,0=0

(3)

(4)

yk,i;r,j+yr,j;k,i=1， 1≤k、r≤K，1≤i

(5)

sr,j-sk,i≥φ([k,i],[r,j],g-h)-

M(3-yk,i;r,j-zk,i,h-zr,j,g)，

1≤i

(6)

sk,i-sr,j≥φ([r,j],[k,i],h-g)-

M(2+yk,i;r,j-zk,i,h-zr,j,g)，

1≤k、r≤K， 1≤i

(7)

sr,j+T-sk,i≥φ([k,i],[r,j],g-h)-

M(2-zk,i,h-zr,j,g)，

1≤k、r≤K， 1≤i

(8)

sk,i+T-sr,j≥φ([r,j],[k,i],h-g)-

M(2-zk,i,h-zr,j,g)，

1≤k、r≤K， 1≤i

(9)

?k,i=1， 1≤k≤K，1≤i≤n，Ci=1

(10)

(11)

sk,i-(sk,i-1+dk,i-1)+(?k,i-1)T≥

ak,i-M(1-yk,i-1;k,i)， 1≤k≤K，1≤i≤n

(12)

sk,i-(sk,i-1+dk,i-1)+(?k,i-1)T≤

bk,i+M(1-yk,i-1;k,i)， 1≤k≤K，1≤i≤n

(13)

(sk,i+T)-(sk,i-1+dk,i-1)+(?k,i-1)T≥

ak,i-Myk,i-1;k,i， 1≤k≤K，1≤i≤n

(14)

(sk,i+T)-(sk,i-1+dk,i-1)+(?k,i-1)T≤

bk,i+Myk,i-1;k,i， 1≤k≤K，1≤i≤n

(15)

(16)

1≤i≤n，Ci=1

(17)

模型的目標函數(shù)是最小化周期長度T。式(1)～式(3)為初始條件，其中式(1)～式(2)限定所有搬運作業(yè)的開始時間都在周期調度域[0,T)內；式(3)規(guī)定第一個工件的第一個搬運作業(yè)始于0時刻。式(4)強調任意一項搬運作業(yè)只能分配給一個Hoist。式(5)強調任意兩項搬運作業(yè)之間只有唯一的一對優(yōu)先關系存在。

式(6)～式(9)是Hoist的移動能力及無碰撞約束。假設搬運作業(yè)[k,i]、[r,j]分別由編號為h、g的Hoist執(zhí)行，式(6)表示，當搬運作業(yè)[k,i]優(yōu)先于搬運作業(yè)[r,j]時，為了保證此兩項搬運作業(yè)不沖突，其開始時間間隔sr,j-sk,i必須不小于參數(shù)φ([k,i],[r,j],θ)；式(7)表示，當搬運作業(yè)[r,j]優(yōu)先于搬運作業(yè)[k,i]時，為了保證此兩項搬運作業(yè)不沖突，其開始時間間隔sk,i-sr,j必須不小于參數(shù)φ([r,j],[k,i],-θ)。式(8)和式(9)確保了相鄰周期之間的Hoist移動軌跡具有連續(xù)性且不存在碰撞沖突。

式(10)、式(11)為工件在工作站上的分配約束。對于那些不存在并行工作站的工藝階段i，即Ci=1，式(10)表示每個工件k的每一個處理階段只有相同的一個工作站可以分配。對于那些存在并行工作站的工藝階段i，即Ci>1，式(11)表示分配處理工件的工作站數(shù)量不大于處理該階段的工作站數(shù)量總和。

式(12)～式(15)為工件各階段的加工時間窗口約束。此時根據(jù)是否存在并行工作站分兩種情形討論：

(1)Ci=1。當yk,i-1;k,i=1時，工件k第i個階段的加工都在一個周期內完成，因此其加工時長為sk,i-(sk,i-1+dk,i-1)，式(12)、式(13)表示工件k第i個階段的加工時長不小于其允許的下限值ak,i同時不大于上限值bk,i。當yk,i-1;k,i=0時，工件k第i個階段的加工開始時間要晚于其結束時間，這意味著工件k第i個階段的加工跨越了兩個周期，那么工件k第i個階段的實際加工時長為(sk,i+T)-(sk,i-1+dk,i-1)。式(14)、式(15)確保此種情形下工件的加工時間窗口約束。

(2)Ci>1。在整個周期內定有(?k,i-1)個工作站被工件k完全占用，此時可視為工件k的第i個階段已經(jīng)加工了(?k,i-1)個周期。因此，相對于Ci=1時的情形，Ci>1時工件k的第i個階段存在額外的(?k,i-1)個周期的加工時長。

式(16)～式(17) 為工作站使用能力約束。根據(jù)式(10)、式(11)可知，當Ci=1時，一個周期內多個工件共享一個工作站，此時工作站可能存在使用能力沖突；當Ci>1時，一個周期內每個工作站至多加工一個工件，此時不存在工作站使用沖突。因此，只需考慮第一種情形(Ci=1)對工作站使用能力約束進行建模。文獻[5]中已構建了單Hoist多度周期調度問題的工作站使用能力約束，而文獻[13]又將問題擴展至多Hoist多度周期調度領域。本文研究具有與上述研究相同的工藝路線且不存在重入工藝，針對式(16)、式(17)的詳細解釋請參閱文獻[5]和文獻[13]。

3 實例研究

本文研究的實例來自于某印刷電路板制造企業(yè)。一般而言，印刷電路板需要經(jīng)歷3個電鍍工藝環(huán)節(jié)：沉銅電鍍、全板電鍍、圖形電鍍。下面針對該企業(yè)的全板電鍍生產過程進行實例分析。

3.1 工藝介紹

該企業(yè)全板電鍍生產線的工藝流程如圖2所示。工件(印刷電路板)首先在1號工位(缸號1)上板，隨后經(jīng)歷7個工藝階段，包括除油(缸號5)、水洗1(缸號6)、水洗2(缸號7)、酸洗(缸號10)、鍍銅(缸號11～25)、水洗3(缸號9)、高位水洗1(缸號8)，最后，在1號工位下板。但是由于夾具(企業(yè)稱之為“飛巴”)在卸載工件后需要經(jīng)過退鍍工藝環(huán)節(jié)(包括退鍍、水洗4、高位水洗2)后返回1號工位，因此，全板電鍍工藝必須以夾具為研究對象。此外，為了避免工件表面黏附的電鍍液污染其它鍍槽，Hoist將工件從電鍍液中取出后還要停留一段時間(滴水時間)，待工件表面的液體滴盡之后再開始移動。

圖2 全板電鍍工藝流程

3.2 輸入?yún)?shù)

本文研究該企業(yè)三種常見的工件類型，分別記為工件A、B、C，各工藝階段加工時間在表1中列出。除了鍍銅工藝之外，A、B、C三種產品的其它工藝加工時間相同。

表1 各工件的加工時間窗口

其它輸入?yún)?shù)設置如下：Hoist空載移動速度χ=0.50 m/s，負載移動速度v=0.50 m/s。Hoist裝載和卸載工件的時間μ=η=8 s。全板電鍍生產線每個工作站間隔1 m，Hoist之間的安全距離為1 m。

3.3 案例求解

在CPU主頻為2.30 GHz的PC機上使用C++語言編寫數(shù)學模型代碼，并在Visual Studio 2010軟件平臺上調用優(yōu)化軟件IBM ILOG CPLEX(版本12.7)求解數(shù)學模型。該案例的求解結果如表2～表7所示，其中“—”表示在當前參數(shù)設置下問題無可行解。

表2給出了各類型工件單獨生產時，最優(yōu)周期長度T與鍍銅工位使用數(shù)量(C5)的關系。總的來說，使用的鍍銅工位數(shù)量越多，周期長度越短?？紤]到工件A鍍銅工序的加工時間參數(shù)，當鍍銅工序使用8個鍍槽時，該線上的生產能力已經(jīng)飽和，繼續(xù)增加鍍銅工位不會縮減周期長度，因此剩余7個鍍槽始終為空閑狀態(tài)。

表2工件單獨生產時的最優(yōu)周期長度T

Table2OptimalcycleTwhenthepartsareproducedindependently

C5T/s工件A工件B工件C12344534471444587.51337.51787.58328670.25895.259—596.4796.44410—536.8716.811—488.36465212—447.667597.66713—413.5355214—384512.57115—358478

為了提高電鍍槽的使用率，考慮將工件A分別與工件B及工件C聯(lián)合生產，應用所建模型分別進行求解。表3和表4列出了這兩種情形下鍍銅工位所有可能的分配組合以及對應的最優(yōu)周期長度T。觀察結果可知，當工件A與B同時生產時，工件A使用4個鍍銅槽、工件B使用9個鍍銅槽可以實現(xiàn)最小的生產周期656 s；當工件A與C同時生產時，工件A使用4個鍍銅槽、工件C使用11個鍍銅槽可以實現(xiàn)最小的生產周期656 s，此時，所有的鍍銅工位都被使用，使用率達到最高。

表3工件A與B同時生產時的最優(yōu)周期長度T(單位：s)

Table3OptimalcycleTwhenpartAandpartBareproducedsimultaneously

工件B使用的鍍槽數(shù)量工件A使用的鍍槽數(shù)量123415372———22682———323501790——4—1343——5—11751074—6——895—7——8957618——7836719———656

表4工件A與C同時生產時的最優(yōu)周期長度T(單位：s)

Table4OptimalcycleTwhenpartAandpartCareproducedsimultaneously

工件C使用的鍍槽數(shù)量工件A使用的鍍槽數(shù)量123423584———323892389——423441792——5—1434——6—11951195—7—11721024—8——896—9——79679610——78171711———656

圖3給出了工件A與C按1∶1同時投產時的調度方案。由圖3可知，各Hoist移動軌跡安排合理，每個搬運作業(yè)執(zhí)行緊湊。調度周期內，一個工件A和一個工件C分別在0、328 s進入生產線。一個工件A和一個工件C分別在192、64 s離開生產線。在192 s離開的工件A是4個周期前進入該線并在此周期完成所有處理工序。在64 s離開的工件C是11個周期前進入該線并在當前周期完成所有處理工序。工件A離開生產線時夾具立即返回生產線執(zhí)行退鍍操作。工件C

圖3 工件A與C同時生產時的調度方案

Fig.3SchedulingsolutionwhenpartAandpartCareproducedsimultaneously

離開生產線后，Hoist立即運送一個完成退鍍工藝的夾具離開系統(tǒng)。一個周期內總有兩個夾具隨工件進入系統(tǒng)，并且有兩個夾具獨立完成退鍍工藝后等待裝夾工件。系統(tǒng)穩(wěn)態(tài)運行時，生產線按照比例1∶1產出工件A與C。

此外，本文還研究了該生產線按照比例2∶1生產工件A與B以及A與C時的情形，其求解結果見表5、表6。針對工件A與B的組合生產，獲得了2組可行的鍍銅工位分配方案，最優(yōu)調度方案可以在一個周期內使用12個鍍銅工位，其對應的最優(yōu)周期長度為984 s。針對工件A與C的組合生產，獲得了3組可行的鍍銅工位分配方案，最優(yōu)調度方案可以在一個周期內使用14個鍍銅工位，其對應的最優(yōu)周期長度同樣為984 s。兩種最優(yōu)方案穩(wěn)態(tài)運行時，按照2∶1的比例產出工件。

表5工件A與B的投產比例為2∶1時的求解結果

Table5ResultsforthecombinationofpartAandpartBwithproductionratioof2∶1

鍍銅工位分配方案鍍銅工位使用數(shù)量AABT/s133510742336984

表6工件A與C的投產比例為2∶1時的求解結果

Table6ResultsforthecombinationofpartAandpartCwithproductionratioof2∶1

鍍銅工位分配方案鍍銅工位使用數(shù)量AACT/s13361197233710243338984

表7給出了工件A、B、C按照不同比例投產時鍍銅工位的使用數(shù)量、周期長度以及模型的求解時間。當工件投產數(shù)量比為2∶1∶1時，其對應的最優(yōu)周期長度為1352 s。此時，一個周期內2個工件A總計使用4個鍍銅工位，工件B和工件C分別使用5個和6個鍍銅工位，即15個鍍銅工位全部被使用。該方案穩(wěn)態(tài)運行時，每1352 s按比例產出4個工件，而當各工件單獨生產時，每產出這4個工件平均需要328×2+358+478=1492s。因此，相對于各工件單獨生產，按2∶1∶1聯(lián)合投產模式可以獲得9.38%的產出提升率。當工件的投產數(shù)量比為1∶2∶1時，同樣使用了全部15個鍍銅工位，其產出提升率為5.76%。當工件的投產數(shù)量比為2∶1∶3時，使用了14個鍍銅工位，其產出提升率為2%。

表7工件A、B、C不同投產比例時的求解結果

Table7ResultsforthecombinationofpartA,partBandpartCwithdifferentproductionratios

投產比例(A∶B∶C)鍍銅工位使用數(shù)量ABCT/s求解時長/s2∶1∶12×21×51×61352791∶2∶11×22×41×51439952∶1∶32×11×33×32399170

需要強調的是，在實際生產中，憑借工作經(jīng)驗、人工拼湊制定的調度方案往往不具有最優(yōu)性，而使用本文所提出的模型可以快速獲得問題的最優(yōu)調度方案。更為重要的是，生產企業(yè)可以根據(jù)訂單需求，利用本文方法研究適合企業(yè)的產品投產比例。這不僅可以加快訂單響應速度，還可以提高生產效率。

4 結語

本文將多Hoist多度周期調度問題拓展至多工件類型集成調度領域，構建了面向產品投產比例的多Hoist調度問題的混合整數(shù)規(guī)劃模型，該模型基于工件所使用的并行工作站數(shù)量建立加工時間窗口約束，簡化了存在并行工作站時的使用能力約束建模。通過對實際生產案例的研究表明，多工件調度可以提高加工設備使用率，而面向產品投產比例的調度模式可以更加靈活地應對多樣化的實際生產需求。

參考文獻

[1] Manier M A, Bloch C. A classification for hoist scheduling problems[J].International Journal of Flexible Manufacturing Systems,2003,15(1):37-55.

[2] Phillips L W, Unger P S. Mathematical programming solution of a hoist scheduling program[J]. AIIE Transactions, 1976,8(2):219-225.

[3] Liu J Y, Jiang Y, Zhou Z L. Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution[J]. IIE Transactions, 2002,34(10):905-914.

[4] Lei L, Wang T J. Determining optimal cyclic hoist schedules in a single-hoist electroplating line[J]. IIE Transactions, 1994,26(2):25-33.

[5] Zhou Z, Che A D, Yan P Y. A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints[J].Applied Mathematical Modelling,2012,36(8):3621-3629.

[6] El Amraoui A, Manier M-A, El Moudni A, et al. Resolution of the two-part cyclic hoist scheduling problem with bounded processing times in complex lines’ configuration[J]. European Journal of Industrial Engineering, 2012,6(4):454-473.

[7] Zhao C Y, Fu J, Xu Q. Production-ratio oriented optimization for multi-recipe material handling via simultaneous hoist scheduling and production line arrangement[J]. Computers and Chemical Engineering, 2013,50(7):28-38.

[8] Yang Guangwen, Ju Dapeng, Zheng Weimin, et al. Solving multiple hoist scheduling problems by use of simulated annealing[J].軟件學報，2001，12(1):11-17.

[9] Leung J M Y，Zhang G Q，Yang X G，et al. Optimal cyclic multi-hoist scheduling: a mixed integer programming approach[J].Operations Research,2004, 52(6):965-976.

[10] Jiang Y，Liu J Y. A new model and an efficient branch-and-bound solution for cyclic multi-hoist scheduling[J].IIE Transactions, 2014,46(3):249-262.

[11] Li X, Fung R Y K. Optimal multi-degree cyclic solution of multi-hoist scheduling without overlapping[J]. IEEE Transactions on Automation Science and Engineering, 2017, 14(2):1064-1074.

[12] LiX, ChanFTS, ChungSH. Optimalmulti-degree cyclic scheduling of multiple robots without overlapping in robotic flowshops with parallel machines[J]. Journal of Manufacturing Systems, 2015, 36:62-75.

[13] Mao Y N, Tang Q H, Li Z X, et al. Mixed-integer linear programming method for multi-degree and multi-hoist cyclic scheduling with time windows[J]. Engineering Optimization, 2018:1-18. DOI:10.1080/0305215X.2017.1418865.