一種多工序生產(chǎn)作業(yè)安排方法

一種多工序生產(chǎn)作業(yè)安排方法

0企業(yè)動態(tài)生產(chǎn)作業(yè)計劃的設(shè)計在現(xiàn)代經(jīng)濟(jì)和社會環(huán)境中，產(chǎn)品生產(chǎn)變得越來越復(fù)雜。通常，公司可以在一個公司的內(nèi)部或多個形式的公司（以下簡稱公司）中生產(chǎn)不同的產(chǎn)品。一個產(chǎn)品需要經(jīng)過多個階段的過程，并且可以根據(jù)公司的實際生產(chǎn)能力和設(shè)備條件精心選擇最合適的生產(chǎn)操作方案。然而，如果市場上競爭激烈，需求變頻繁，公司規(guī)模發(fā)生變化，如何快速調(diào)整生產(chǎn)操作計劃，不僅可以動態(tài)適應(yīng)公司內(nèi)部環(huán)境的變化，而且可以指導(dǎo)公司的實際生產(chǎn)（例如，特定設(shè)備部門需要詳細(xì)說明時間間隔內(nèi)必須完成的加工任務(wù)），以實現(xiàn)降低成本和提高效率。通過分析和動態(tài)規(guī)劃網(wǎng)絡(luò)，我們解決了上述問題。這種方法尤其適用于零件加工和安裝公司。1問題的計算過程企業(yè)在實際生產(chǎn)作業(yè)安排中,存在的制約因素有交貨期限、生產(chǎn)能力、庫存容量等,需要實現(xiàn)的目標(biāo)有按時交貨、降低成本、平衡生產(chǎn)能力等.而且不同企業(yè)會產(chǎn)生不同的制約和目標(biāo).若企業(yè)有d種產(chǎn)品,m道工序.i表示產(chǎn)品代號,j表示工序代號,每道工序的可用工時劃分成jn段時間片(時間片是指將機(jī)器工時劃分成相等的時段,可以是日、小時甚至分鐘.應(yīng)根據(jù)要求結(jié)果精確度和計算量大小來確定),xjkijki表示i產(chǎn)品在j工序上第k個時間片是否安排生產(chǎn)的決策變量:xjki={1產(chǎn)品i在j?序k時間片上安排生產(chǎn)0產(chǎn)品i在j?序k時間片上不安排生產(chǎn)f(x)表示某個生產(chǎn)作業(yè)計劃下的成本函數(shù),不允許缺貨和僅考慮成本目標(biāo)的情況下,生產(chǎn)作業(yè)安排的問題可表述為:其中:X表示x的可行域(滿足不發(fā)生生產(chǎn)能力不足,庫存超容以及能按時交貨的限制條件).由于現(xiàn)實問題的復(fù)雜性以及對生產(chǎn)作業(yè)計劃及時性要求,本文解決問題的計算過程通過總體生產(chǎn)能力安排,單臺設(shè)備時間片安排和合成調(diào)整三個階段進(jìn)行,每個階段由相應(yīng)的步驟組成.2計算過程2.1全球生產(chǎn)能力的配置2.1.1工序過程vi,vj將整個企業(yè)各產(chǎn)品的流程和工序標(biāo)繪成一個網(wǎng)絡(luò)D=(V,A,C),其中V是產(chǎn)品生產(chǎn)起始點和所有工序結(jié)束點的集合,A是緊前工序結(jié)束點指向緊后工序結(jié)束點弧的集合,可理解為在其上完成了某道工序的加工任務(wù),C是弧上容量的集合,可理解為每道工序加工能力.對每條弧標(biāo)注上(b*ij,aij),其中b*ij表示某一產(chǎn)品在工序(vivj)上最優(yōu)經(jīng)濟(jì)批量時的單位產(chǎn)品的生產(chǎn)成本(包括半成品從緊前工序運輸?shù)皆摴ば騿挝划a(chǎn)品運輸成本和該道工序單位產(chǎn)品加工成本),aij表示該工序的加工能力.本文的產(chǎn)品流程和工序網(wǎng)絡(luò)略不同于一般運籌學(xué)中定義的網(wǎng)絡(luò),它有多個起點和終點,并且在有些點和弧有其特殊的性質(zhì),下面舉一簡單的例子來說明其特殊性.圖1描繪有兩種產(chǎn)品的流程和工序網(wǎng)絡(luò).S1,S2分別表示產(chǎn)品1和產(chǎn)品2的生產(chǎn)起點.E1,E2分別表示產(chǎn)品1和產(chǎn)品2的生產(chǎn)終點.a,b,…,g表示各工序的結(jié)束點,可以理解為有a,b,…,g臺設(shè)備,某道工序結(jié)束就表示在某臺設(shè)備上完成了加工任務(wù)(為方便論述,以后都稱為設(shè)備a,b,…,g),每條孤表示一道工序,記作(vi,vj),如:(vs1,va);(va,vd),…,其中(va,vd)表示產(chǎn)品1在設(shè)備a上加工完畢后的半成品送往設(shè)備d并在設(shè)備d上完成加工任務(wù)的工序,弧(va,vd)上的標(biāo)注(4,6)表示產(chǎn)品1完成該工序所需單位生產(chǎn)成本(包括產(chǎn)品1在設(shè)備a上加工完畢后的半成品從設(shè)備a所在地運往設(shè)備b所在地的單位運輸成本和在設(shè)備b上的單位加工成本)為4個貨幣單位(如4元),特定時期內(nèi)該工序生產(chǎn)能力為6個單位(如6件).圖上與終點相連的虛線表示沒有真實的工序,僅表示某產(chǎn)品生產(chǎn)完畢后從流程中流出.從圖1上可以看出產(chǎn)品1可選擇生產(chǎn)流程有P11(S1,a,d,f,E1)和P21(S1,a,c,f,E1),同理產(chǎn)品2也有P12(S2,b,c,g,E2),P22(S2,b,e,g,E2)兩條生產(chǎn)流程.注意圖中特殊的點c,f,g,這些點共同的特點是有多于1條弧指向它們,以點f為例,有(vd,vf),(vc,vf)兩條弧指向f點,兩條弧上的標(biāo)注分別為(4,6)和(3,3).這里有兩種情況,第一種情況:標(biāo)注adf項6表示產(chǎn)品1經(jīng)設(shè)備d加工之后,設(shè)備f對設(shè)備d交來的產(chǎn)品1的半成品的加工能力為6件.若產(chǎn)品1經(jīng)設(shè)備c加工之后,設(shè)備f對設(shè)備c交來的產(chǎn)品1的另一種形式的半成品加工能力為3件.表明產(chǎn)品1在設(shè)備c和d上完成加工后的半產(chǎn)品是不同的,后繼工序需要的加工時間也將不一樣.對于從設(shè)備d交來產(chǎn)品1的半成品,設(shè)備f的加工能力為對設(shè)備c交來產(chǎn)品1的另一種半成品的2倍.所以假設(shè)由設(shè)備c交來1件產(chǎn)品1的半成品需要設(shè)備f進(jìn)行加工,則對弧(vc,vf)來說剩余的加工能力為2(2=3-1)個單位,而此時對于弧(vd,vf)來說剩余的加工能力為4(4=6-6/3×1)個單位.第二種情況:設(shè)備f是對設(shè)備d和c交來的半成品進(jìn)行組裝,這其實是同一流程的不同工序的銜接.只需將裝配點前所有緊前工序的單位生產(chǎn)成本記為:至裝配點完工后總的單位生產(chǎn)成本減去該工序前所有可用流程(有剩余生產(chǎn)能力)的單位生產(chǎn)成本的最小值.在這里,點c、f和g均屬于第一種情況.2.1.2弧的集合cij1)繪制形如圖1的整個企業(yè)的流程和工序網(wǎng)絡(luò).其中弧上標(biāo)注的b*ij是某產(chǎn)品在(vi,vj)工序上最優(yōu)經(jīng)濟(jì)批量下的單位生產(chǎn)成本.在計算過程中得到某個生產(chǎn)作業(yè)安排實際的單位生產(chǎn)成本,記為bij,得出的bij可能會大于b*ij,這個問題在第三階段進(jìn)行討論.2)從第一步所形成的網(wǎng)絡(luò)中分離出各產(chǎn)品的分網(wǎng)絡(luò)(弧上標(biāo)注的含義均不變).對每一產(chǎn)品的分網(wǎng)絡(luò),使用最小費用最大流方法確定每一產(chǎn)品成本最低的生產(chǎn)流程安排.單條流程的生產(chǎn)能力不足的情況下,可能選擇其中的多條生產(chǎn)流程.但要注意的是使用最小費用最大流方法(詳見參考文獻(xiàn)).解題時,在尋找新的增廣鏈前,對于類似圖1中指向f點各弧的剩余加工能力要同時按相應(yīng)值一并減少.此外,第k次調(diào)整量θ應(yīng)按以下公式確定:θ=min{minu+(Cij-fk-1ij),minu-fk-1ij,(Οi-fk-1)}(4)其中:θ為弧(vi,vj)第k次調(diào)整的流量;u+為前向弧的集合;u-為后向弧的集合;Cij為弧(vi,vj)的容量(加工能力);Oi為產(chǎn)品i的訂單量;fk-1ij為第k-1次弧(vi,vj)的流量;fk-1為第k-1次的可行流.第k次可行流:fkij={fk-1ij+θ(vi,vj)∈u+fk-1ij-θ(vi,vj)∈u-fk-1ij(vi,vj)?u(5)重復(fù)尋找新的增廣鏈,直到某次k使得(Oi=fk)則第二步停止.如圖1,若產(chǎn)品1和產(chǎn)品2的訂單量分別為3件和4件,對于產(chǎn)品1選擇成本最低的流程P21就能完成3件的訂單量.對于產(chǎn)品2首先按Dijkstra算法(見文獻(xiàn))選擇流程P12,按公式(4)確定θ=min{3,∞,4}=3,則弧(vc,vg)和(ve,vg)的剩余加工能力應(yīng)同時減少為1(1=4-3)和2(2=8-(8/4)×3)件.用含負(fù)權(quán)的最短路徑算法(詳見參考文獻(xiàn))尋找到新的增廣鏈p22,確定θ=min{2,∞,1}=1,調(diào)整后就能完成4件訂單量.3)再將分網(wǎng)絡(luò)合并成整個企業(yè)的流程和工序網(wǎng)絡(luò),判斷每道工序是否有沖突(即現(xiàn)有設(shè)備的加工能力不足完成合并后的的生產(chǎn)任務(wù)).如圖1中點c,生產(chǎn)產(chǎn)品1與產(chǎn)品2共需要設(shè)備c加工能力為6件,而設(shè)備c僅有3件的加工能力.找到這些沖突點,并且選擇與現(xiàn)有加工能力差距最大的沖突點,繪制出除去最大沖突點各產(chǎn)品的分網(wǎng)絡(luò).分網(wǎng)絡(luò)弧上標(biāo)注aij項改為工序的剩余加工能力,但在被刪除的最大沖突點所在流程上的弧以及最大沖突點緊后工序?qū)?yīng)支流的弧(如:弧(vc,vf)和(vc,vg)分別對應(yīng)的弧(vd,vf)(ve,vg))上標(biāo)注aij項改記為工序剩余的加工能力加上按最大沖突點加工能力不足量所換算的工序加工能力,因為發(fā)生了沖突表示要選擇另外的流程,某產(chǎn)品的全部或部分沖突的加工量將可能由不經(jīng)過沖突點所在流程上來實現(xiàn),則相應(yīng)的加工能力給予還原.4)從第3)得出新的各產(chǎn)品分網(wǎng)絡(luò)的基礎(chǔ)上,找到各產(chǎn)品新的一條增廣鏈,計算各產(chǎn)品新增廣鏈的單位產(chǎn)品成本(記為Ti)以及該新增廣鏈的單位產(chǎn)品成本與此前最后一次需通過沖突點安排產(chǎn)品生產(chǎn)的流程的單位產(chǎn)品成本(記為T′i)之差,選擇成本差最小的i產(chǎn)品(mini(Τi-Τ′i))的分網(wǎng)絡(luò)來進(jìn)行調(diào)整,θ表示i產(chǎn)品新增鏈上的最大可調(diào)整量,θ*表示沖突量,則調(diào)整量為min{θ,θ*}.如圖1,對于產(chǎn)品1,T1=as1a+aad+adf=2+4+4=10,T′1=as1a+aac+acf=2+3+3=8,T1-T′1=10-8=2;類似產(chǎn)品2的T2=12,T′1=6,T2-T′2=6,公式mini(Τi-Τ′i)中的i為1,調(diào)整量為3件(3=min{4,3}).5)再將各產(chǎn)品的分網(wǎng)絡(luò)合并,判斷是否存在沖突點.若無沖突點則可以進(jìn)入第二階段,若還存在沖突點,返回到第三步.當(dāng)各產(chǎn)品分網(wǎng)絡(luò)都不存在新的增廣鏈且沖突點仍然存在,則表明企業(yè)整體生產(chǎn)能力不足以滿足訂單對生產(chǎn)能力的需求,進(jìn)行相應(yīng)追加設(shè)備投資或拒絕部分訂單等決策,以消除整體生產(chǎn)能力的不足.2.1.3設(shè)備c的按需加工和運輸時間t在實際企業(yè)產(chǎn)品生產(chǎn)過程中,在前一道工序加工完畢運到后一道工序是需要時間的,特別是前后兩道工序所使用的設(shè)備安置在相隔距離較遠(yuǎn)的地點時,還有設(shè)備等待所需半成品的時間.在計算設(shè)備生產(chǎn)能力時必須要考慮途中的運輸時間和設(shè)備等待時間.如圖2所示(帶箭頭的虛線表示可能存在多道工序),設(shè)備a完成對產(chǎn)品i半成品的加工任務(wù)后由設(shè)備c繼續(xù)加工,則設(shè)備c的可用工時應(yīng)為:在特定期間內(nèi)設(shè)備c總工時減去第一批半成品運達(dá)設(shè)備c之前所有工序所需加工和運輸時間以及所有后續(xù)工序?qū)υO(shè)備c交來的最后一批半成品加工和運輸所需時間.設(shè)備a可用工時的計算也應(yīng)作類似處理.如果有兩道緊前工序,并且不同緊前工序的加工和運輸時間有差異,可以把設(shè)備c看成兩臺設(shè)備,其中一臺表示某緊前工序由于時間差原因獨占設(shè)備c的加工能力.如圖3,點C2表示點b專占的由于時間差計算的設(shè)備c的加工能力.但半成品有庫存的情況下,上述情況就不存在.若各產(chǎn)品的交貨期不同,也可按上述方法將交貨期時間差所計算某設(shè)備加工能力作為某產(chǎn)品的專屬加工設(shè)備.交貨期重疊的時間的加工能力由各產(chǎn)品共同占用.如果半產(chǎn)品可以出售的情況,看作一新的產(chǎn)品并且單獨繪制該半產(chǎn)品的分網(wǎng)絡(luò).如果一臺設(shè)備同一時刻能完成兩種加工任務(wù),視作兩臺設(shè)備.2.2動態(tài)優(yōu)化方法如果每道工序可看成一臺設(shè)備,則需要考慮將這些加工任務(wù)分配到單臺設(shè)備的時間片上.本文簡單介紹由文獻(xiàn)提出的使用動態(tài)規(guī)劃的解決方法.該方法的基本思路是:將單臺設(shè)備的加工能力劃分成若干較小的時間片,假設(shè)每個時間片只能被一種產(chǎn)品所占用.對每一個需要在設(shè)備上加工的產(chǎn)品按其各自的約束條件通過動態(tài)規(guī)劃解出各自成本最低的設(shè)備時間片上的生產(chǎn)安排,然后進(jìn)行合并,檢查是否發(fā)生沖突(即一個時間片被一種以上的產(chǎn)品同時占用).若有沖突發(fā)生,在沖突的時間片加一罰值(限于片幅,加罰值方法詳見參考文獻(xiàn)),表示占用該時間片需承擔(dān)額外的費用.在加罰值的情況下再對各產(chǎn)品進(jìn)行動態(tài)規(guī)劃.經(jīng)過反復(fù)調(diào)整罰值、動態(tài)規(guī)劃和合并檢查過程,求得最優(yōu)解.公式如下:δit={1產(chǎn)品i在第t個時間片上安排生產(chǎn)0產(chǎn)品i在第t個時間片上不安排生產(chǎn)(6)庫存狀態(tài)轉(zhuǎn)移方程:xit=xi(t-1)-rit+Piδit(7)成本方程:Ci(1-δi(t-1))δit+hixit+uvtδit(8)上式Ci(1-δi(t-1))δit表示如第t-1個時間片設(shè)備被i產(chǎn)品占用,則第t個時間片就不需要重新啟動設(shè)備,設(shè)備啟動費用也不存在.成本遞推方程:Lit(δit,xit)=minδi(t-1){Ci(1-δi(t-1))δit+hixit+uvtδit+Li(t-1)(δi(t-1),xi(t-1))}(9)文獻(xiàn)中建設(shè)按以下公式設(shè)定uvt的值:uv+1t=uvt+max{0,αgt(δv)}(10)其中:gt(δv)}=Ι∑i=1δit-1(11)i為產(chǎn)品編號(i=1,2,…,I);t為設(shè)備時間片編號(t=1,2,…,T);Ci為產(chǎn)品i的設(shè)備起動費用;Pi為產(chǎn)品i在單位時間片內(nèi)的生產(chǎn)量;hi為產(chǎn)品i的單位存儲費用;rit為產(chǎn)品i在第t個時間片的需要量;xit為產(chǎn)品i在第t個時間片末的庫存量;ximax為產(chǎn)品i庫存上限;uvt為拉格朗日乘數(shù),迭代到v步第t個時間片的罰值和;α為單位罰值;δit為變動系數(shù).文獻(xiàn)還討論了設(shè)備啟動時間跨越幾個時間片和單位罰值α選擇等問題,限于篇幅詳見原文.此外,動態(tài)規(guī)劃過程的約束條件應(yīng)根據(jù)企業(yè)實際的情況來設(shè)立.2.3根據(jù)重和重的要求進(jìn)行的生產(chǎn)作業(yè)安排.在合成階段主要解決以下兩個問題:(1)如圖4,要解決點b,c與點a時間上的銜接問題.在設(shè)備b和設(shè)備c上單臺設(shè)備時間片安排確定情況下,在設(shè)備a不發(fā)生沖突的條件下和規(guī)定時間內(nèi)保證設(shè)備b和設(shè)備c所需半成品的供應(yīng).(2)在第一階段總體生產(chǎn)能力安排所使用的是每道工序最優(yōu)經(jīng)濟(jì)批量下的單位生產(chǎn)成本,而在第二步單臺設(shè)備時間片安排的結(jié)果不一定是最優(yōu)經(jīng)濟(jì)批量下的單位生產(chǎn)成本,它們之間的成本差異要進(jìn)行處理.合成按以下步驟進(jìn)行:1)從所有最后的工序開始,考慮訂單交貨期及其它約束條件下進(jìn)行第二階段的動態(tài)規(guī)劃過程.2)如有圖4的情況時,檢查所有最后的工序在單臺設(shè)備時間片安排下對緊前工序提出的半成品供應(yīng)時間的要求是否在所有前道