分批排序及資源約束排序中若干問題.pdf

1、排序是組合優(yōu)化的一個重要的分支．由于其堅實的應用背景和深刻的理論意義，它被廣泛應用于工農(nóng)業(yè)生產(chǎn)、運輸業(yè)、管理科學和計算機科學等諸多領域．分批排序與機器有使用限制的排序都是新型的排序問題，因此吸引了國內(nèi)外眾多學者的關注．在經(jīng)典排序問題中，通常假設工件的加工時間為常數(shù)．但在許多實際問題中，工件的加工時間可能與其開工時間或所排位置有著某種聯(lián)系，由此產(chǎn)生一些工件的工時可變化的現(xiàn)代排序問題．本文就工件加工時間為常數(shù)或線性變化的分批排序及資源有約束

2、排序中若干問題做了如下工作：
　　1．第一章介紹了排序問題產(chǎn)生的主要背景以及相關基本知識．
　　2．第二和第三章考慮了工件的加工時問是常數(shù)的分批排序問題．其中在第二章研究的是無限批容量下的同類機分批排序問題，目標是極小化加權總完工時間。給出了該問題的最優(yōu)排序的性質(zhì)，當機器的臺數(shù)m為常數(shù)時，設計了一個時間復雜性為O(n m+2)的動態(tài)規(guī)劃算法．第三章研究的是批容量無限和有限的無關機分批排序問題．對批容量無限排序模型，目標是極小

3、化總完工時間，我們?yōu)楣r一致性的情形設計了一個時間復雜性為O(n m+2)的動態(tài)規(guī)劃算法；對批容量有限排序模型中的特殊情形pij=pi(1≤i≤ m≤1≤j≤n)，為若干不同目標，分別設計了最優(yōu)算法及偽多項式時間算法．
　　3．第四和第五章我們考慮了工件的加工時間是變量的分批排序問題．其中第四章研究的工件的實際加工時間為pj=αjt，其中αj被定義為工件的惡化率，i是開工時間．本章我們考慮了極小化最大完工時間和總完工時間問題．對極

4、小化最大完工時間問題，對工件有同一到達時間情形，我們分別就單機和平行機問題設計了最優(yōu)算法和FPTAS；對工件到達時間不一致情形，我們證明了其NP-難性，并就一特殊情形給出了多項式時間最優(yōu)算法．對極小化總完工時間的單機問題，當工件的惡化率的個數(shù)是常數(shù)m(0，目標是極小化被接收工件的最大完工時間