排序問題的近似算法.pdf

1、編號：碩士學位論文碩士學位論文題目：排序問題的近似算法培養(yǎng)單位：數學與系統(tǒng)科學學院專業(yè)名稱：應用數學指導教師：羅成新研究生：張琦完成時間：2015年3月21日沈陽師范大學研究生處制類別全日制研究生√教育碩士同等學力排序問題的近似算法摘要排序作為近代應用數學的一個分支，有著深切的實際背景和廣博的應用領域。主要是將生產、管理等事件中出現的一些運籌問題加以提煉，然后利用數學方法求解問題。它廣泛應用于工廠，生產調度，管理科學，計算機科學和工程技

2、術等眾多領域。其本質是組合優(yōu)化問題，即在問題的有限可行解集中求出最優(yōu)解。但是在實際生產過程中，由于一些前提條件的限制導致某些排序問題得不到最優(yōu)解；或者需要很長的運行時間和極大的存儲空間才能找到最優(yōu)解。為了求解實際問題，我們可以采用近似算法，即在較短的運行時間內得到問題的近似解來替代最優(yōu)解。從而簡化算法，降低時間復雜性。為了具有實用性，近似算法得到的近似解與最優(yōu)解之間必須滿足一定的誤差精度。本文對兩種機器模型的近似算法進行研究。主要內容為

3、：第一章主要介紹排序問題的相關定義和三參數表示法，并介紹了幾類排序問題的研究背景及本文在此基礎之上的改進工作。第二章主要研究帶有不可用區(qū)間工件中斷可恢復的平行機排序問題。分別討論了兩種不同的目標函數。使最大的完工時間最小是其中一個目標函數。本章所考慮的第一個問題是一般意義下?NP困難的，因此需要尋找滿足指定誤差精度的近似解。在較短的運行時間內利用削減狀態(tài)空間的方法設計了一個全多項式時間的近似方案)(FPTAS，并得到該問題的近似解。該近

4、似方案具有強多項式的運行時間，算法的時間復雜性為)(23?nO，這里n是輸入工件的個數，?是誤差精度。另一個目標函數是使加權總完工時間最小。本章所考慮的第二個問題同樣是一般意義下?NP困難的。為了找到滿足指定誤差精度的近似解，利用劃分程序的方法得到了一個FPTAS。該算法的運行時間為)(455?LnO，其中n為加工工件的個數，L為輸入規(guī)模?為誤差精度。第三章主要研究帶有退化效應和拒絕的m臺恒速機排序問題。工件具有退化效應和允許被拒絕。退