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

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

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

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

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