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

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

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

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

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