汽車4維修系統(tǒng)調(diào)度問(wèn)題的協(xié)調(diào)與優(yōu)化

1動(dòng)態(tài)柔性加工車間調(diào)度模型及其改進(jìn)后的再調(diào)度2004年，ibm和美國(guó)競(jìng)爭(zhēng)力委員會(huì)首次提出了服務(wù)科學(xué)的概念。在他們的大力支持下，國(guó)內(nèi)外科學(xué)家積極響應(yīng)。郭重慶、國(guó)家自然科學(xué)基金委員會(huì)交通管理部的郭重慶、劉作義教授等在科學(xué)研究方面做了筆記。服務(wù)系統(tǒng)調(diào)度問(wèn)題屬于服務(wù)科學(xué)研究的范疇。目前,針對(duì)汽車4S店維修服務(wù)系統(tǒng)調(diào)度問(wèn)題的理論研究還比較少,4S店的車間管理人員通常是結(jié)合任務(wù)的緊急程度和設(shè)備的繁忙狀況等因素,依據(jù)經(jīng)驗(yàn)預(yù)估任務(wù)的完成時(shí)間,進(jìn)行任務(wù)的作業(yè)排序。這即不利于提高企業(yè)資源利用率,也難以滿足客戶需求。因此,該研究具有理論和現(xiàn)實(shí)價(jià)值。汽車4S店維修服務(wù)系統(tǒng)調(diào)度問(wèn)題的基本形式可以描述為動(dòng)態(tài)柔性加工車間調(diào)度問(wèn)題(FlexibleJobShopSchedulingProblem,FJSP)。FJSP問(wèn)題是對(duì)經(jīng)典加工車間調(diào)度問(wèn)題(JobShopSchedulingProblem,JSP)的擴(kuò)展,由于問(wèn)題的復(fù)雜性,目前對(duì)此類問(wèn)題的研究集中在應(yīng)用啟發(fā)式算法求解靜態(tài)問(wèn)題上。但是汽車4S店維修服務(wù)系統(tǒng)存在:任務(wù)不確定、無(wú)法庫(kù)存以及任務(wù)的作業(yè)時(shí)窗缺乏柔性等特征,使得其調(diào)度更具動(dòng)態(tài)性。再調(diào)度是解決動(dòng)態(tài)調(diào)度問(wèn)題的有效方式,眾多學(xué)者研究了再調(diào)度策略及其應(yīng)用。但是再調(diào)度將一個(gè)FJSP問(wèn)題變成多個(gè),進(jìn)一步增加了問(wèn)題的求解難度。Goldratt(1984)提出約束理論,簡(jiǎn)稱TOC(theoryofconstraints),指出瓶頸是制約系統(tǒng)朝著目標(biāo)前進(jìn)的主要因素,決定了整個(gè)系統(tǒng)的性能,通過(guò)把管理重點(diǎn)放到瓶頸環(huán)節(jié),簡(jiǎn)化非瓶頸環(huán)節(jié),能有效地提升管理效率。目前,已經(jīng)有學(xué)者研究如何將約束理論運(yùn)用于生產(chǎn)調(diào)度和供應(yīng)鏈管理等領(lǐng)域,并取得較好的結(jié)果。但是,現(xiàn)有研究多針對(duì)制造系統(tǒng),很少有涉及動(dòng)態(tài)的服務(wù)系統(tǒng)。本文試圖在已有研究的基礎(chǔ)上,針對(duì)汽車4S店維修服務(wù)系統(tǒng)的柔性調(diào)度特性進(jìn)行問(wèn)題的分解簡(jiǎn)化,通過(guò)緩沖設(shè)置與管理協(xié)調(diào)瓶頸與非瓶頸加工中心,并設(shè)計(jì)再調(diào)度策略實(shí)現(xiàn)問(wèn)題的動(dòng)態(tài)求解。2數(shù)量質(zhì)量描述中,下標(biāo)j表示任務(wù)(j=1,2,…,n,n表示任務(wù)的數(shù)量);上標(biāo)i表示工作中心(i=1,2,…,l,l表示工作中心的數(shù)量);上標(biāo)h表示工作中心i中的一臺(tái)并行異速機(jī)(h=1,2,…,mi,mi表示工作中心i中并行異速機(jī)的數(shù)量)。2.1任務(wù)2:每臺(tái)設(shè)備未加工一項(xiàng)任務(wù)假設(shè)1:每項(xiàng)任務(wù)在每個(gè)加工中心只選擇一臺(tái)設(shè)備加工一次。假設(shè)2:任一時(shí)刻每臺(tái)設(shè)備只加工一項(xiàng)任務(wù)。假設(shè)3:每項(xiàng)任務(wù)按照預(yù)定的工藝路徑依次通過(guò)各加工中心。假設(shè)4:在整個(gè)服務(wù)系統(tǒng)中只存在一個(gè)瓶頸加工中心。假設(shè)5:任務(wù)在設(shè)備開(kāi)始加工則不允許中斷。2.2這個(gè)問(wèn)題的基本描述采用三元組α/β/γ方法,對(duì)4S店維修服務(wù)系統(tǒng)與制造系統(tǒng)調(diào)度問(wèn)題的共性進(jìn)行基本描述。2.2.1車輛維修保養(yǎng)汽車4S店維修服務(wù)系統(tǒng)中包含多個(gè)串行加工中心(包括:機(jī)電、鈑金、油漆和美容等)。車輛維修保養(yǎng)任務(wù)要按照事先預(yù)定的加工路線,順序通過(guò)上述加工中心,每個(gè)加工中心有多臺(tái)設(shè)備可供選擇。整體而言,該系統(tǒng)相當(dāng)于柔性加工車間,符合FJSP調(diào)度模型。2.2.2任務(wù)響應(yīng)約束任務(wù)具有提交時(shí)間rj、工期dj、權(quán)重ωj、作業(yè)時(shí)間pj和設(shè)備能力Mj等約束,具體如下:①時(shí)間窗約束完成一輛汽車的維修保養(yǎng)任務(wù),要滿足作業(yè)提交時(shí)間rj和工期dj約束。②準(zhǔn)備時(shí)間約束sjg準(zhǔn)備時(shí)間sjg是指設(shè)備連續(xù)完成任務(wù)j和g的過(guò)程中需要的整理調(diào)試時(shí)間,它受任務(wù)作業(yè)順序的影響。例如,對(duì)車輛進(jìn)行噴漆,前后車輛顏色相同則準(zhǔn)備時(shí)間短,否之則準(zhǔn)備時(shí)間長(zhǎng)。③能力約束Mj設(shè)備能力約束由任務(wù)性質(zhì)和設(shè)備適用性決定,例如車輛擦刮后需要打磨噴漆和烘干,由于受損面積和位置不同,決定了不同任務(wù)適用的設(shè)備存在差異。2.2.3績(jī)效目標(biāo)iii域與制造系統(tǒng)的調(diào)度目標(biāo)相類似,汽車維修服務(wù)系統(tǒng)設(shè)備的調(diào)度也要滿足制造時(shí)間和工作的最終期限等調(diào)度目標(biāo)。2.3問(wèn)題描述針對(duì)汽車4S店維修服務(wù)系統(tǒng)與制造系統(tǒng)調(diào)度問(wèn)題的差異,進(jìn)行汽車4S店維修服務(wù)系統(tǒng)調(diào)度問(wèn)題的特性描述。2.3.1薄層加工汽車4S店維修服務(wù)系統(tǒng)與一般的FJSP調(diào)度模型相比存在明顯的瓶頸加工中心。由于汽車4S店維修車間的烤漆房?jī)r(jià)格貴,任務(wù)在該設(shè)備上的作業(yè)時(shí)間長(zhǎng),利用率高,鈑噴加工中心成為整個(gè)汽車4S店維修服務(wù)系統(tǒng)的瓶頸環(huán)節(jié)。2.3.2作業(yè)時(shí)窗的柔性汽車4S店維修服務(wù)系統(tǒng)中任務(wù)的動(dòng)態(tài)性比制造系統(tǒng)更強(qiáng),具體表現(xiàn)為以下幾個(gè)方面:①作業(yè)時(shí)窗缺乏柔性制造系統(tǒng)的庫(kù)存準(zhǔn)備為任務(wù)的作業(yè)時(shí)窗提供了緩沖。而汽車維修服務(wù)系統(tǒng),只有在客戶將車輛送至現(xiàn)場(chǎng),發(fā)出工單后,才能開(kāi)始作業(yè),沒(méi)有預(yù)先的庫(kù)存準(zhǔn)備,因此其作業(yè)時(shí)窗缺乏柔性。②任務(wù)具有實(shí)時(shí)性由于客戶到達(dá)時(shí)間是實(shí)時(shí)的,使得任務(wù)提交時(shí)間不確定,任意時(shí)刻都可能出現(xiàn)任務(wù)要及時(shí)安排,因此工作任務(wù)具有實(shí)時(shí)性,要實(shí)行動(dòng)態(tài)調(diào)度。2.3.3任務(wù)權(quán)重的確定使客戶滿意是服務(wù)業(yè)經(jīng)營(yíng)管理的關(guān)鍵。從時(shí)間上講,就是確保任務(wù)的預(yù)期完成時(shí)間,減小滯后,特別是重要任務(wù)的滯后。因此,汽車4S店維修服務(wù)系統(tǒng)的調(diào)度目標(biāo)是最小化加權(quán)滯后時(shí)間和∑ωjTj,式中ωj表示任務(wù)的權(quán)重,體現(xiàn)了任務(wù)j的重要程度;Tj=max(Cj-dj,0),表示任務(wù)滯后時(shí)間,Cj表示任務(wù)j離開(kāi)系統(tǒng)的實(shí)際時(shí)間。2.4任務(wù)系統(tǒng)約束綜上所述,汽車4S店維修服務(wù)系統(tǒng)調(diào)度問(wèn)題可設(shè)計(jì)為存在明顯瓶頸,以最小化加權(quán)滯后時(shí)間和為目標(biāo),受多約束限制的動(dòng)態(tài)FJSP問(wèn)題。其數(shù)學(xué)模型如下:Μinn∑j=1ωjΤj(1)Min∑j=1nωjTj(1)s.t.Tj=max(dj-Cj,0)(2)Cihjihj-rij≥pihj+sihjg/(i,j)∈N/(3)x1hj≥rj/(i,j)∈N/(4)xkhj-xihj≥pihj+sihjg/(i,j)→(k,j)∈A/(5)xihj-xihg≥pihg+sihjgorxihg-xihj≥pihj+sihjg/i∈L,h∈Mi/(6)xihj≥0/(i,j)∈N/(7)模型中,決策變量xihj表示操作(ih,j)的起始時(shí)間;L表示工作中心集合,Mi表示工作中心i中的機(jī)器集合;N表示任務(wù)集合;Cihj表示任務(wù)j在工作中心i中機(jī)器h上的完工時(shí)間;A為線路約束(i,j)→(k,j)集合,表示任務(wù)j在工作中心加工的先后順序。式(1)為目標(biāo)函數(shù),式(2)-式(7)為約束條件。其中:式(2)度量了任務(wù)j的延遲時(shí)間;式(3)保證任務(wù)j的所有工序都能夠完成;式(4)確保任務(wù)j開(kāi)始作業(yè)的時(shí)間滿足任務(wù)提交時(shí)間約束;式(5)為操作約束,確保任務(wù)j在不同工作中心的加工順序;式(6)為機(jī)器約束,保證在同一臺(tái)機(jī)器上加工的不同任務(wù)之間存在先后排序;式(7)保證每道加工工序的時(shí)間大于0。3非瓶頸加工中心優(yōu)化調(diào)度流程約束理論將優(yōu)化的重點(diǎn)聚焦到瓶頸環(huán)節(jié),首先松弛非瓶頸加工中心的能力約束,調(diào)度最難安排的瓶頸設(shè)備,接著安排非瓶頸設(shè)備,然后協(xié)調(diào)各子問(wèn)題,以獲得可行調(diào)度。3.1分解、簡(jiǎn)化和建模3.1.1加工中心、瓶頸后加工中心的加工以瓶頸為核心,在瓶頸加工中心前后設(shè)置緩沖能確保瓶頸環(huán)節(jié)任務(wù)的連續(xù)性和及時(shí)性,據(jù)此汽車4S店維修服務(wù)系統(tǒng)調(diào)度問(wèn)題可分解為:瓶頸前(機(jī)電、鈑金)加工中心、瓶頸(鈑噴)加工中心和瓶頸后(洗車、美容)加工中心三個(gè)部分。如圖1所示:圖中:pbbj=b-1∑i=1pij+sij表示任務(wù)j在瓶頸前各加工中心的作業(yè)與準(zhǔn)備時(shí)間和,TBin表示輸入緩沖,rbj表示瓶頸加工中心的提交時(shí)間,pbj表示瓶頸加工中心的作業(yè)時(shí)間,sbj表示瓶頸加工中心的準(zhǔn)備時(shí)間,dbj表示瓶頸加工中心的工期,TBout表示輸出緩沖,pabj=l∑i=b+1pij+sij表示瓶頸后各加工中心的作業(yè)與準(zhǔn)備時(shí)間和。3.1.2非瓶頸加工中心的機(jī)器能力約束非瓶頸環(huán)節(jié)的加工能力無(wú)限大,且在瓶頸加工中心前后設(shè)置有緩沖,則非瓶頸加工中心的機(jī)器能力約束可以松弛。FJSP問(wèn)題的求解簡(jiǎn)化為對(duì)瓶頸環(huán)節(jié)并行異速機(jī)的求解問(wèn)題。3.1.3子問(wèn)題建模動(dòng)態(tài)調(diào)度問(wèn)題根據(jù)約束理論,瓶頸決定系統(tǒng)的節(jié)奏,最小化任務(wù)在整個(gè)系統(tǒng)的滯后時(shí)間就是最小化任務(wù)在瓶頸環(huán)節(jié)的滯后時(shí)間。同時(shí),瓶頸環(huán)節(jié)存在資源短缺,在調(diào)度中要提高資源的利用率。據(jù)此,瓶頸加工中心的調(diào)度問(wèn)題可設(shè)計(jì)為包含最小化的制造期(Cmax)與最小化加權(quán)滯后時(shí)間和(∑ωjTj)的多目標(biāo),受到多約束限制的并行機(jī)動(dòng)態(tài)調(diào)度問(wèn)題(Qm|rj|θ1∑wjTj+θ2Cmax)。非瓶頸加工中心的調(diào)度問(wèn)題可設(shè)計(jì)為帶任務(wù)提交時(shí)間和交貨期限制的并行機(jī)動(dòng)態(tài)調(diào)度問(wèn)題(Qm|rj|Lmax)。加工中心任務(wù)到達(dá)時(shí)間和工業(yè)進(jìn)展瓶頸加工中心提交時(shí)間如式(8),工期如式(9);瓶頸前加工中心任務(wù)到達(dá)時(shí)間如式(10),工期如式(11);瓶頸后加工中心任務(wù)到達(dá)時(shí)間如式(12),工期如式(13)。式中tbj和cbj分別表示瓶頸加工中心調(diào)度結(jié)果的開(kāi)始時(shí)間和完工時(shí)間。rbj=rj+pbbj+TBin(8)dbj=dj-pabj-TBout(9)rbbj=rj(10)dbbj=tbj-TBin(11)rabj=cbj(12)dabj=dj(13)3.2瓶頸不是瓶頸加工中心的協(xié)調(diào)3.2.1緩沖設(shè)計(jì)Daniel提出動(dòng)態(tài)緩沖的長(zhǎng)度是瓶頸前或瓶頸后作業(yè)時(shí)間和的倍數(shù)。結(jié)合經(jīng)驗(yàn)數(shù)據(jù),為確保瓶頸環(huán)節(jié)加工任務(wù)不間斷,在瓶頸(鈑噴)加工中心前設(shè)置輸入緩沖(TBin=2Pbbj);為確保瓶頸環(huán)節(jié)任務(wù)及時(shí)完成,不拖延工期,在瓶頸(鈑噴)加工中心后設(shè)置輸出緩沖(TBout=Pabj)。3.2.2簡(jiǎn)單的調(diào)度規(guī)則預(yù)調(diào)度以瓶頸(鈑噴)加工中心為核心。首先運(yùn)用動(dòng)態(tài)調(diào)度規(guī)則獲得問(wèn)題的初始解,接著運(yùn)用智能搜索算法迭代尋優(yōu);非瓶頸加工中心加工能力大于需求,且只需滿足提交時(shí)間和工期要求,可以運(yùn)用簡(jiǎn)單的調(diào)度規(guī)則快速求解。調(diào)度結(jié)果中:任務(wù)j在瓶頸前(機(jī)電、鈑金)加工中心實(shí)際完工時(shí)間用cbbj表示;在瓶頸后(洗車、美容)加工中心的實(shí)際開(kāi)始時(shí)間用tabj表示。通過(guò)協(xié)調(diào)上述結(jié)果變量可實(shí)現(xiàn)汽車4S店維修服務(wù)系統(tǒng)的調(diào)度。3.2.3緩沖管理應(yīng)用如果瓶頸前工序不能在期望的完工時(shí)間內(nèi)完成,則可能造成瓶頸和瓶頸前加工中心作業(yè)在時(shí)間軸上的迭代,使得調(diào)度不可行。對(duì)于瓶頸后加工中心,rabj=cbj,這使得調(diào)度不存在時(shí)間軸上的迭代,所以緩沖管理的重點(diǎn)是輸入緩沖區(qū)。通過(guò)在瓶頸與非瓶頸加工中心間的緩沖管理可有效緩解這種時(shí)間上的迭代,如圖2所示。忽略區(qū),cbbj∈[rj+pbbj,rj+2pbbj],落入此區(qū)域的任務(wù)在重調(diào)度時(shí)可忽略,只需將新任務(wù)插入其中即可,如果有大量任務(wù)落入此區(qū)域,可考慮縮短輸入緩沖。警示區(qū),cbbj∈[rj+2pbbj,rbj],落入此區(qū)域的任務(wù)要關(guān)注,如果該任務(wù)在瓶頸加工中心上的作業(yè)開(kāi)始時(shí)間tbj發(fā)生變化則需要重新計(jì)算其指數(shù),進(jìn)行重排。凍結(jié)區(qū),cbbj∈[rbj,tbj],任務(wù)落入此區(qū)域則需要凍結(jié)其在瓶頸加工中心前的作業(yè)時(shí)段,確保該任務(wù)能按時(shí)執(zhí)行,如果有大量任務(wù)落入此區(qū)域,則需要延長(zhǎng)各任務(wù)的工期,并重新設(shè)計(jì)輸入緩沖。重排區(qū),cbbj≥tbj,對(duì)落入此區(qū)域的任務(wù),需要進(jìn)行重新調(diào)度,調(diào)整瓶頸加工中心的到達(dá)時(shí)間和完工時(shí)間,隨后根據(jù)新的調(diào)度結(jié)果重新設(shè)定非瓶頸加工中心的到達(dá)時(shí)間和工期。4再規(guī)劃策略設(shè)計(jì)設(shè)計(jì)再調(diào)度策略包括重調(diào)度時(shí)刻的確定和各子問(wèn)題再調(diào)度方法的選擇兩個(gè)方面。4.1局部重調(diào)度局部重調(diào)度采用基于任務(wù)(車輛)的混合策略進(jìn)行重調(diào)度,即在周期性調(diào)度的基礎(chǔ)上,當(dāng)特定事件發(fā)生時(shí)也要引發(fā)重調(diào)度。如圖3所示。橫坐標(biāo)表示任務(wù)(車輛)序號(hào),W(l)表示第l個(gè)預(yù)測(cè)窗口,預(yù)測(cè)窗口內(nèi)有L(l)個(gè)車輛。重調(diào)度時(shí)刻有兩種情況:情況一,周期性重調(diào)度,每次執(zhí)行局部最優(yōu)調(diào)度中的k個(gè)車輛,并將完成這k個(gè)車輛的時(shí)刻作為重調(diào)度時(shí)刻;情況二,特定事件(包括:緊急車輛到達(dá)、車輛延遲、優(yōu)先權(quán)變化等)發(fā)生時(shí)。滾動(dòng)窗口內(nèi)最多有k個(gè)車輛,且滾動(dòng)窗口內(nèi)的車輛數(shù)小于預(yù)測(cè)窗口內(nèi)的車輛數(shù),即L(l)>k。4.2車輛集、監(jiān)控方法對(duì)瓶頸加工中心采取完全重調(diào)度,即任意重調(diào)度時(shí)刻t,對(duì)未加工的所有車輛集進(jìn)行調(diào)度。對(duì)瓶頸前加工中心采取部分重調(diào)度,即:僅重調(diào)度直接和間接受干擾的任務(wù),具體可用緩沖區(qū)管理中的再調(diào)度方法。對(duì)瓶頸后加工中心采取右移再調(diào)度,即推遲車輛的加工直到調(diào)度可行,調(diào)度順序保持不變。5測(cè)試結(jié)果與分析通過(guò)現(xiàn)場(chǎng)調(diào)研,日常情況下,開(kāi)業(yè)期在2-10年的汽車4S店維修車間每天的任務(wù)數(shù)量范圍為[20,130],其中需要進(jìn)行油漆工序的任務(wù)占總數(shù)的20%-30%,可以使用預(yù)噴房和烤燈的任務(wù)占油漆任務(wù)數(shù)的30%-50%。瓶頸資源烤漆房的數(shù)量范圍為,預(yù)噴房的數(shù)量范圍為,烤燈的數(shù)量范圍為?？酒岱康淖鳂I(yè)時(shí)間pAj在區(qū)間中均勻分布,預(yù)噴房的作業(yè)時(shí)間pBj在區(qū)間[0.5,1]中均勻分布;各項(xiàng)作業(yè)的權(quán)重在區(qū)間中正態(tài)分布;非瓶頸工位上任務(wù)的加工時(shí)間服從[0.3,1]的均勻分布;任務(wù)到達(dá)時(shí)間rj服從[0,8]的離散均勻分布;為了避免預(yù)期完成時(shí)間dj設(shè)置過(guò)松或過(guò)緊,令dj=rj+λ∑p,∑p表示任務(wù)總的作業(yè)時(shí)間和,任務(wù)在每個(gè)工序的作業(yè)時(shí)間可用任務(wù)在該工序不同設(shè)備上的平均作業(yè)時(shí)間表示,λ在區(qū)間中均勻分布。本文運(yùn)用幾種調(diào)度規(guī)則(先到先加工FCFS,最短加工時(shí)間先加工SPT,最早交貨期限先加工EDD)對(duì)所有設(shè)備進(jìn)行完全重調(diào)度。并將本文所述算法記作DBR進(jìn)行仿真比較。以10個(gè)任務(wù)為滾動(dòng)窗口,用n×m[D(m1),B(m2)]標(biāo)志每個(gè)組別,其中n表示任務(wù)數(shù),m表示油漆設(shè)備的數(shù)量,D和B分別表示烤漆房和預(yù)噴房,括號(hào)內(nèi)的m1,m2表示對(duì)應(yīng)資源的數(shù)量,每組產(chǎn)生10個(gè)樣本。采用以