當(dāng)代工業(yè)中的若干排序問題研究.pdf

1、排序問題是一個經(jīng)典的組合優(yōu)化問題，受到眾多學(xué)者的關(guān)注，隨著社會生產(chǎn)的發(fā)展，又不斷地產(chǎn)生一些新模型，本文就針對這些新模型，主要研究當(dāng)代工業(yè)中的若干排序問題.全文共分為七章，第一章主要介紹與排序問題相關(guān)的一些概念和預(yù)備知識.接著我們分別研究了六個排序模型. 第二章研究機(jī)器帶準(zhǔn)備時間的兩臺同型機(jī)排序問題.對于極小化機(jī)器最大完工時間的目標(biāo)函數(shù)，我們給出了一個最壞情況界為10/9的線性時間近似算法.第三章研究機(jī)器需周期性維護(hù)的單臺機(jī)排序問

2、題.目標(biāo)函數(shù)為極小化工件最大完工時間，我們考慮工件加工不可恢復(fù)情形.我們首先證明LPT算法的最壞情況界為2，然后證明在P≠NP的假設(shè)下不存在最壞情況界比2小的多項(xiàng)式時間近似算法，從而證明LPT算法已經(jīng)是最優(yōu)的近似算法. 第四章研究了機(jī)器在固定時刻提速的單臺機(jī)排序問題，目標(biāo)是極小化工件最大完工時間.我們分別對在線和離線情形進(jìn)行了相應(yīng)的分析，證明該問題是NP-hard問題，給出了最優(yōu)在線算法，并設(shè)計(jì)了一個最壞情況界為5/4的離線算法

3、. 第五章討論機(jī)器可以進(jìn)行速率調(diào)整的單臺機(jī)排序問題.對于極小化工件最大完工時間和極小化工件總完工時間兩個目標(biāo)，我們都進(jìn)行了計(jì)算復(fù)雜性分析，并對大部分情形設(shè)計(jì)了多項(xiàng)式時間近似算法或者偽多項(xiàng)式時間動態(tài)規(guī)劃算法.特別地，對于極小化工件最大完工時間，我們還設(shè)計(jì)了完全多項(xiàng)式時間近似方案;對于極小化工件總完工時間，我們還對一個常見子情形給出了一個偽多項(xiàng)式時間最優(yōu)算法. 第六章研究一種加工時間依賴開工時間，并且機(jī)器帶一個維護(hù)時間段的單

4、臺機(jī)排序問題.我們考慮工件加工不可恢復(fù)情形，目標(biāo)是極小化工件最大完工時間和極小化工件總完工時間.我們分別進(jìn)行了計(jì)算復(fù)雜性分析.進(jìn)一步地，對于前一個目標(biāo)，我們給了一個最優(yōu)的在線算法和一個離線情形下的完全多項(xiàng)式時間近似方案;對于后一個目標(biāo)，我們給了一個啟發(fā)式算法并通過數(shù)據(jù)試驗(yàn)驗(yàn)證其性能. 第七章主要研究帶運(yùn)送費(fèi)用的單臺機(jī)分批運(yùn)送排序問題.目標(biāo)為極小化賦權(quán)工件總運(yùn)送時間和運(yùn)送費(fèi)用之和，其中運(yùn)送費(fèi)用和運(yùn)送的次數(shù)有關(guān).我們進(jìn)行了計(jì)算復(fù)雜性