有資源限制的分批排序問(wèn)題的算法研究.pdf

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

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