基于雙向動態(tài)規(guī)劃的無向圖的無向圖調度

基于雙向動態(tài)規(guī)劃的無向圖的無向圖調度

在線應用不僅是應用方案中最簡單的問題，也是應用方案中最重要的問題。理論上通常把單機調度作為復雜調度系統(tǒng)的一個子系統(tǒng),實際生產中比較復雜的調度問題也可以分解為多個單機問題來解決,研究單機調度問題可以幫助理解和解決更為復雜的多機調度問題。對單機的合理調度有助于實現(xiàn)資源的合理分配、降低成本、提高生產效率和設備的利用率,因而對其進行研究具有十分重要的實際意義。單機總加權完成時間調度是單機調度中的一個經典問題。在激烈的市場競爭中,能夠在最短的時間內完成客戶的訂單可以有效提高一個企業(yè)的競爭力,因此,最小化1||∑w1具有無向環(huán)的多級連接圖單機總加權完成時間調度問題具體描述如下:在1臺機器上,有n個工件按照一定的優(yōu)先級要求進行連續(xù)加工,通過計算工件完成時間{C單機加工過程中,工件間的優(yōu)先級關系所構成的圖形稱為優(yōu)先級圖。圖1舉例說明了一個含有無向環(huán)的優(yōu)先級連接圖,工件OP5,OP6,OP7,OP8和工件OP8,OP9,OP10,OP11分別構成了一個無向環(huán)。以工件OP5為例,工件OP1,OP2,OP3和OP4是工件OP5的緊前工件,工件OP6和OP7是工件OP5的緊后工件。這里的“緊前”及“緊后”關系只表明工件的優(yōu)先級關系,不一定指的是工件的加工順序。例如在實際生產中,只有工件OP1,OP2,OP3,OP4都完成后才能開始工件OP5的加工,在單機上只能有1個工件在工件OP5開始前進行加工,因此,不能確定工件OP1,OP2,OP3和OP4的加工順序。2計劃時間范圍參數表示如下:I—工件集,I={1,2,…,n}),其中,n為總工件數GpwK—計劃時間范圍,K=∑pC決策變量為根據以上參數,建立1|prec|∑w滿足條件如下:在上述模型中,目標函數式(1)表示最小化所有工件的總加權完成時間之和。約束式(2)表示優(yōu)先級圖中工件間的加工優(yōu)先級順序;約束式(3)和(4)規(guī)定了變量的取值范圍,其中,CN3拉格朗日協(xié)議算法的解決方案拉格朗日松弛算法是一種高效的優(yōu)化算法3.1乘子的確定根據單機總加權完成時間調度的數學模型,給定一組拉格朗日乘子{u滿足式(1)~(3)和(5)以及式(7)~(8)。令則有L為原問題的一個下界,為了獲得最緊的下界,定義如下的拉格朗日對偶問題(LD):3.2拉格朗日松弛算法的建立由于前向動態(tài)規(guī)劃只能處理有多個緊前工件的調度,而不能處理有多個緊后工件的情況,后向動態(tài)規(guī)劃則剛好相反,因此,設計雙向動態(tài)規(guī)劃處理1個工件既有緊前工件又有緊后工件的情況。該方法由Zhang等使用雙向動態(tài)規(guī)劃求解優(yōu)先級圖中含無向環(huán)的調度問題時,必須先對優(yōu)先級圖做一定的轉化。首先,任意打破1個環(huán),即忽略環(huán)中1組工件的優(yōu)先級關系以使優(yōu)先級圖中不存在環(huán)。然后,找到G用Z從工件的最后一個節(jié)點τ式中:從而得到松弛問題的下界:算例分析如下:以圖1的工件優(yōu)先級關系為例,表1給出了各個工件的加工時間和權重。應用拉格朗日松弛求解時,設其乘子{u(1)當打破環(huán)(1)和環(huán)(3)時,轉換后的優(yōu)先級圖如圖2所示。根據工件在樹中的位置排序得到:1-5-2-3-4-6-8-7-9-11-10-12-13-14-15。(2)計算每個工件的最早和最晚可能完成時間,(3)從最后一個工件開始向前計算,由R(4)由R(5)由R(6)由R(7)由R(9)由R(10)RZ(11)由R(12)由R(13)由R(14)由R(15)由R(16)由R(17)由R計算下界和{C(19)通過向前追蹤得到松弛問題的解:3.3拉格朗日乘數更新求解拉格朗日對偶問題LD是一個不斷迭代的過程:給定一組可行的拉格朗日乘子{u3.4解的可行性分析因為對偶問題得到的解可能違反機器的能力約束,因此它的解對于原問題一般是不可行的。為構造可行解,本文基于拉格朗日松弛問題的解以及局域搜索設計啟發(fā)式法將不可行解轉化為可行解。4拉格朗日松弛法實驗測試在PentiumⅣ主頻3.0GHz的微機上運行,當對偶間隙小于0.05%或迭代次數達到100次時,程序停止。實驗測試了7種問題規(guī)模,每種組合有15個實例,共有105個實例用于本實驗,工件數從20~80個變化,隨機產生的工件加工時間和權重都滿足[2,8]之間的均勻分布。每個實例中,工件的優(yōu)先級關系給定,假設工件優(yōu)先級圖為連接圖。用拉格朗日松弛法求解調度問題時,對偶問題的最優(yōu)解(L由表2和圖3可得出如下結論:(1)在平均4.04s內,用拉格朗日松弛算法計算得到的總平均對偶間隙為0.63%,說明此算法可在較短的CPU時間內得到一個較高質量的解。(2)隨著工件數的增加,對偶間隙、計算時間和迭代次數也隨之增加。這是因為工件數的增多增強了調度難度,從而使問題變得更加復雜。(3)迭代初期,算法的收斂性比較快,但隨著迭代數的增加,收斂性趨于平緩,得到的對偶間隙變化不大;迭代后期,由于利用啟發(fā)式構造可行解時采用了局域搜索,這進一步提高了解的質量。5基于雙向動態(tài)規(guī)劃的拉格朗日松弛算法本文擴展了單機調度的研究,進一步對工件優(yōu)先級關系中含無向環(huán)的單機調度問題進行了深入探討,目標函數