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

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

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

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