兩類新型排序問題的算法研究.pdf

1、排序作為組合優(yōu)化領(lǐng)域的一個(gè)重要分支，正被越來越廣泛地應(yīng)用于生產(chǎn)與制造領(lǐng)域。其中，帶有庫存約束的排序和含有服務(wù)器的排序是兩類新型排序模型。前者是建立在車輛調(diào)度與倉庫管理這一實(shí)際背景下的排序模型，而后者則在網(wǎng)絡(luò)計(jì)算、紡織行業(yè)、鋼鐵工業(yè)等方面有著重要的應(yīng)用。本文主要研究這兩類排序問題，核心工作是建立它們的數(shù)學(xué)模型、設(shè)計(jì)算法并分析算法的性能。全文共分為五章。
　　第一章首先介紹排序、計(jì)算復(fù)雜性、近似算法等基本概念，接著簡(jiǎn)要綜述經(jīng)典排序研究

2、的理論與算法，最后闡述本文擬研究的排序模型。
　　第二章，我們研究了單臺(tái)機(jī)器帶有庫存約束的排序問題。這一章主要包括兩個(gè)部分。第一部分考慮的是負(fù)工件個(gè)數(shù)只有一個(gè)的問題1｜inv,｜n-｜=1｜∑w1c1。我們首先給出了問題復(fù)雜性的證明，緊接著給出了貪婪算法，盡管算法的最壞情況界是無窮大，但隨機(jī)試驗(yàn)表明算法的平均性能十分優(yōu)越。第二部分，我們對(duì)負(fù)工件個(gè)數(shù)為任意多個(gè)的問題1｜inv,｜n1｜∑C1(n1≧1,n1∈Z+)進(jìn)行了研究，給出了

3、解決問題的0-1整數(shù)規(guī)劃模型，同時(shí)設(shè)計(jì)了貪婪-合并算法，并采用隨機(jī)試驗(yàn)說明算法的平均性能同樣是非常優(yōu)越的。
　　第三章，我們對(duì)含有一個(gè)服務(wù)器的m臺(tái)平行機(jī)器排序問題進(jìn)行了研究。在每個(gè)工件加工之前必須由一臺(tái)公共的服務(wù)器將它們安裝到機(jī)器上然后才能在機(jī)器上開始加工。每個(gè)工件在機(jī)器上的加工時(shí)間相同。這一章主要分為兩個(gè)部分。首先，我們研究了問題p,s1｜s1,p1=p1｜Cmax證明了SPT算法的最壞情況界不超過2-1/m，且是緊的。緊接著，