排序問(wèn)題的動(dòng)態(tài)規(guī)劃模型、算法和計(jì)算復(fù)雜性.pdf

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

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

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

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

5、排序費(fèi)用和控制費(fèi)用的總和為最小的加工時(shí)間可控的同時(shí)加工排序問(wèn)題。選取不同的排序費(fèi)用,共解決了三個(gè)問(wèn)題：用動(dòng)態(tài)規(guī)劃的方法為問(wèn)題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)設(shè)計(jì)了最優(yōu)算法。3．工件可拒絕排序問(wèn)題研究安排n個(gè)工件,使接受加工工件的帶權(quán)總完工時(shí)間