排序問題的近似算法.pdf

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

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

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

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