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

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

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

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

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