幾類排序問(wèn)題的近似算法.pdf

1、排序問(wèn)題本質(zhì)是一類組合最優(yōu)化問(wèn)題，即要找到一個(gè)最優(yōu)算法來(lái)求出該問(wèn)題的最優(yōu)解。對(duì)于幾類經(jīng)典排序問(wèn)題，已經(jīng)找到最優(yōu)算法并且獲得最優(yōu)解。但在實(shí)際生產(chǎn)生活中，由于某些前提因素的限制和新增加的一些變量導(dǎo)致一些排序問(wèn)題得不到最優(yōu)解；或者需在相當(dāng)大的運(yùn)行時(shí)間內(nèi)才能找到最優(yōu)解（如動(dòng)態(tài)規(guī)劃算法），這些都不是我們想要的結(jié)果，為了能在較短的運(yùn)行時(shí)間內(nèi)解決此類排序問(wèn)題，我們利用較好的算法得到的近似解來(lái)替代最優(yōu)解。本文對(duì)幾類排序問(wèn)題的近似算法進(jìn)行研究。主要內(nèi)容為

2、：
　　第一章主要對(duì)排序問(wèn)題的定義和三參數(shù)表示法進(jìn)行描述，并介紹幾類排序問(wèn)題的研究背景及本文在此基礎(chǔ)上所做的工作。
　　第二章主要研究帶有拒絕工件和機(jī)器維修區(qū)間的單機(jī)排序問(wèn)題。目標(biāo)是找到一個(gè)全多項(xiàng)式近似方案(FPTAS)，在該方案下得到近似解使?jié)M足一定的誤差要求，同時(shí)給出該近似方案的時(shí)間復(fù)雜性為O(n2/ε2)。
　　第三章主要研究帶有退化工件和機(jī)器維修區(qū)間的單機(jī)排序問(wèn)題?？紤]的是單機(jī)上工件允許被拒絕，工件的加工時(shí)間是