兩類新型排序問題-算法設(shè)計(jì)與分析.pdf

1、排序問題一直是組合優(yōu)化領(lǐng)域的活躍研究方向．傳統(tǒng)的排序模型假設(shè)所有的工件屬于一個排序者，而且整個排序過程中機(jī)器總是保持相同的性能．近年來，人們根據(jù)生產(chǎn)實(shí)際的需要不斷拓展出新的排序問題.針對第一個假設(shè)，出現(xiàn)了多客戶排序問題，每個客戶擁有自己的工件，在共同的機(jī)器資源上安排工件使得各方的利益達(dá)到某種平衡.對于第二個假設(shè)，人們研究機(jī)器需要維護(hù)情形下的排序方案.機(jī)器維護(hù)有兩個關(guān)鍵參數(shù)，維護(hù)的開始時刻和維護(hù)的時長.不同的參數(shù)環(huán)境提出了不同的排序問題，

2、圍繞上述的兩點(diǎn)拓展，本文主要討論下面幾個新型排序模型：維護(hù)時間可變的單機(jī)排序問題，浮動維護(hù)下的線性退化工件單機(jī)排序問題和兩個客戶下的兩臺機(jī)流水作業(yè)排序問題.本文由四章組成．
　　 第一章為緒論，主要介紹組合優(yōu)化和排序的基本概念和預(yù)備知識．
　　 第二章研究了維護(hù)時間可變的單機(jī)排序問題，其中維護(hù)的時長是維護(hù)開始時刻的非降函數(shù)．當(dāng)極小化目標(biāo)函數(shù)分別是最大完工時間，最大延遲和工件的完工時間和時，我們給出多項(xiàng)式時間的精確算法．而

3、當(dāng)目標(biāo)函數(shù)為工件的賦權(quán)完工時間和時，我們證明了該問題是弱NP-困難的，并先后設(shè)計(jì)了一個(2+ε)-近似算法和一個完全多項(xiàng)式時間近似方案．
　　 對一類特殊情形，即維護(hù)的時長是維護(hù)開始時刻的非降凹函數(shù)時，我們分別給出了2-近似算法和(1+√2/2+ε)-近似算法.這兩個近似算法都是強(qiáng)多項(xiàng)式時間的．
　　 最后，我們討論了維護(hù)的時長是維護(hù)開始時刻的任意函數(shù)的情形，證明了對極小化（賦權(quán)）完工時間和的目標(biāo)函數(shù)，不存在近似比為常數(shù)

4、的多項(xiàng)式時間算法，除非P=NP.
　　 第三章考慮了浮動維護(hù)下的線性退化工件單機(jī)排序問題．所謂浮動維護(hù)是指維護(hù)的時長固定，但維護(hù)的開始時間不晚于一個給定的時刻．對極小化最大完工時間以及極小化工件完工時間和兩個目標(biāo)函數(shù)，我們證明了弱NP-困難性，并分別給出了完全多項(xiàng)式時間近似方案.
　　 第四章則研究兩個客戶下的兩臺機(jī)流水作業(yè)排序問題．每個客戶只關(guān)心自己的工件最大完工時刻．為了將兩個目標(biāo)結(jié)合起來化成單目標(biāo)優(yōu)化問題，我們考慮