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

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

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