排序問題的動態(tài)規(guī)劃模型、算法和計算復雜性.pdf

1、排序論又稱為時間表理論,是一類重要的組合優(yōu)化問題。隨著社會的發(fā)展,新的模型層出不窮,并且絕大多數是NP-難問題或強NP-難問題。動態(tài)規(guī)劃是求解組合最優(yōu)化問題的一個重要方法,特別適合求解NP-難問題,在工程技術、經濟管理、工業(yè)生產和軍事等方面都有著廣泛的應用。在排序問題越來越復雜的情況下,只要運用得當,動態(tài)規(guī)劃這個傳統的方法可以成為解決復雜問題的較好途徑。本文討論排序問題的動態(tài)規(guī)劃算法,考慮的排序模型涉及供應鏈排序、工件加工

2、時間可控排序、工件可拒絕排序,以及工件有優(yōu)先約束的排序問題。第一章介紹了用動態(tài)規(guī)劃方法解決問題的基本步驟,總結了用動態(tài)規(guī)劃方法設計排序問題算法的基本情況,其中涉及的排序問題類型有經典的單機、平行機問題,可中斷排序問題,車間作業(yè)問題,柔性流水作業(yè)問題,同時加工問題,成組排序問題,以及供應鏈問題。第二章和第三章是本文的主要內容。主要研究以下幾個問題：1.供應鏈排序問題(1)在只有一個供應商的樹狀供應鏈中,研究平行機加工工件,使

3、排序費用和發(fā)送費用達到最小的問題。對用總流程時間衡量排序費用的問題1→G,Pm‖∑Fj+∑Dgyg,證明其強NP-難性,設計最壞性能比是2-1/m的動態(tài)規(guī)劃算法。另外,證明了問題1→G,Pm‖Lmax+∑Dgyg和1→G,Pmll∑Uj+∑Dgygg的NP-難性質。(2)在多供應商、多制造商的網狀供應鏈中,分別從供應商和制造商的角度研究生產的安排和發(fā)送的決策問題。用動態(tài)規(guī)劃的方法給出了以下六個問題的最優(yōu)算法：供應商階段的總流

4、程時間問題K－>G,1‖∑Fj+∑Dk,gyk,g,最大延遲問題K－>G,1‖Lmax+∑Dk,gyk,g和誤工工件數問題K－>G,1‖∑Uj+∑Dk,gyk,g,制造商階段的總流程時間問題G－>C,1|rj|∑Fj+∑Dg,hyg,h,最大延遲問題G－>C,1|rj|Lmax+∑Dg,hyg,h和誤工工件數問題G－>C,1‖∑Uj+∑Dg,hyg,h。2．工件加工時間可控排序問題研究工件具有離散型可控加工時間,安排n個工件使

5、排序費用和控制費用的總和為最小的加工時間可控的同時加工排序問題。選取不同的排序費用,共解決了三個問題：用動態(tài)規(guī)劃的方法為問題1|B,dis_cpt|∑UJ+n∑i=1∑h∑k=1ckIk(xi),1|B,dis_cpt|Lmax+n∑i=1∑h∑k=1ckIk(xi)和1|B,dis_cpt|Cmax+n∑i=1∑h∑k=1ckIk(xi)設計了最優(yōu)算法。3．工件可拒絕排序問題研究安排n個工件,使接受加工工件的帶權總完工時間