毛永年，唐秋華，張利平

1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081; 2.武漢科技大學(xué)機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081)

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

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

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

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

1 問題描述與符號(hào)定義

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

圖1 典型的電鍍生產(chǎn)線布局

由于所研究的各類型工件具有相同的工藝路線，本文根據(jù)進(jìn)入時(shí)間的先后順序?qū)⒅芷趦?nèi)的各工件依次編號(hào)為1,2,…,K。因此，面向產(chǎn)品投產(chǎn)比例的多Hoist調(diào)度問題可以用3個(gè)輸入?yún)?shù)n、H、K來描述。

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

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

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

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

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

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

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

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

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

該問題的決策變量為：

(1)T：周期長(zhǎng)度。

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

(3)?k,i：工件k的第i個(gè)階段所使用的機(jī)器數(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ī)劃模型的建立

面向產(chǎn)品投產(chǎn)比例的多Hoist調(diào)度混合整數(shù)規(guī)劃模型構(gòu)建如下：

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)

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

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

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

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

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

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

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

3 實(shí)例研究

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

3.1 工藝介紹

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

圖2 全板電鍍工藝流程

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

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

表1 各工件的加工時(shí)間窗口

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

3.3 案例求解

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

表2給出了各類型工件單獨(dú)生產(chǎn)時(shí)，最優(yōu)周期長(zhǎng)度T與鍍銅工位使用數(shù)量(C5)的關(guān)系?？偟膩碚f，使用的鍍銅工位數(shù)量越多，周期長(zhǎng)度越短。考慮到工件A鍍銅工序的加工時(shí)間參數(shù)，當(dāng)鍍銅工序使用8個(gè)鍍槽時(shí)，該線上的生產(chǎn)能力已經(jīng)飽和，繼續(xù)增加鍍銅工位不會(huì)縮減周期長(zhǎng)度，因此剩余7個(gè)鍍槽始終為空閑狀態(tài)。

表2工件單獨(dú)生產(chǎn)時(shí)的最優(yōu)周期長(zhǎng)度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)合生產(chǎn)，應(yīng)用所建模型分別進(jìn)行求解。表3和表4列出了這兩種情形下鍍銅工位所有可能的分配組合以及對(duì)應(yīng)的最優(yōu)周期長(zhǎng)度T。觀察結(jié)果可知，當(dāng)工件A與B同時(shí)生產(chǎn)時(shí)，工件A使用4個(gè)鍍銅槽、工件B使用9個(gè)鍍銅槽可以實(shí)現(xiàn)最小的生產(chǎn)周期656 s；當(dāng)工件A與C同時(shí)生產(chǎn)時(shí)，工件A使用4個(gè)鍍銅槽、工件C使用11個(gè)鍍銅槽可以實(shí)現(xiàn)最小的生產(chǎn)周期656 s，此時(shí)，所有的鍍銅工位都被使用，使用率達(dá)到最高。

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

Table3OptimalcycleTwhenpartAandpartBareproducedsimultaneously

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

表4工件A與C同時(shí)生產(chǎn)時(shí)的最優(yōu)周期長(zhǎng)度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同時(shí)投產(chǎn)時(shí)的調(diào)度方案。由圖3可知，各Hoist移動(dòng)軌跡安排合理，每個(gè)搬運(yùn)作業(yè)執(zhí)行緊湊。調(diào)度周期內(nèi)，一個(gè)工件A和一個(gè)工件C分別在0、328 s進(jìn)入生產(chǎn)線。一個(gè)工件A和一個(gè)工件C分別在192、64 s離開生產(chǎn)線。在192 s離開的工件A是4個(gè)周期前進(jìn)入該線并在此周期完成所有處理工序。在64 s離開的工件C是11個(gè)周期前進(jìn)入該線并在當(dāng)前周期完成所有處理工序。工件A離開生產(chǎn)線時(shí)夾具立即返回生產(chǎn)線執(zhí)行退鍍操作。工件C

圖3 工件A與C同時(shí)生產(chǎn)時(shí)的調(diào)度方案

Fig.3SchedulingsolutionwhenpartAandpartCareproducedsimultaneously

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

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

表5工件A與B的投產(chǎn)比例為2∶1時(shí)的求解結(jié)果

Table5ResultsforthecombinationofpartAandpartBwithproductionratioof2∶1

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

表6工件A與C的投產(chǎn)比例為2∶1時(shí)的求解結(jié)果

Table6ResultsforthecombinationofpartAandpartCwithproductionratioof2∶1

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

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

表7工件A、B、C不同投產(chǎn)比例時(shí)的求解結(jié)果

Table7ResultsforthecombinationofpartA,partBandpartCwithdifferentproductionratios

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

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

4 結(jié)語

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

參考文獻(xiàn)

[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].軟件學(xué)報(bào)，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.