有資源限制的分批排序問題的算法研究.pdf

1、排序問題是組合優(yōu)化領(lǐng)域的一個重要分支，它有著重要的應(yīng)用背景和深刻的理論意義．而分批排序是繼經(jīng)典排序之后的較新排序模型之一．本文就這一模型的有資源限制的問題做了一些工作． 第一章簡單介紹了排序問題的相關(guān)定義、記號及相關(guān)預(yù)備知識． 第二章考慮了單機(jī)分批排序問題中目標(biāo)是極小化加權(quán)總完工時間的問題．將FBLW算法進(jìn)行推廣，就工件到達(dá)時間均為正整數(shù)、加工時間恒為1的情形，設(shè)計出了一個時間復(fù)雜性為(O)(n<'2>log n)的最優(yōu)

2、算法；對工件有常數(shù)m個到達(dá)時間、加工時間恒等的情形給出一個最優(yōu)算法，并給出其算法復(fù)雜性為O(2<'m-1>n log n)． 第三章研究了分批排序中機(jī)器有使用限制的兩個問題．這是首次將機(jī)器有使用限制的條件在分批排序問題中進(jìn)行考慮．對于目標(biāo)是極小化最大完工時間、工件不可中斷的單機(jī)分批排序問題，我們對批容量無限的情形找到了多項(xiàng)式時間的最優(yōu)算法，對批容量有限的情形提出了一個最差性能比為4/3的近似算法，并且界是緊的． 第四章總