關(guān)于分批排序問題的研究.pdf

1、本文的內(nèi)容分三大部分：第一部分提出了三種新型分批排序模型：(1)具有主次指標(biāo)的單機(jī)分批排序問題(第二章)；(2)具有三重指標(biāo)的單機(jī)平行分批排序問題(第三章)；(3)單機(jī)準(zhǔn)時分批排序問題(第四章)．對于這些問題的研究在文獻(xiàn)中幾乎沒有見到，而這些模型具有很強(qiáng)的應(yīng)用背景和理論研究意義．本文對這些新型排序模型給出了若干研究結(jié)果．第二部分對一些現(xiàn)有單機(jī)分批排序問題最優(yōu)解的結(jié)構(gòu)性質(zhì)進(jìn)行了系統(tǒng)研究(第五章)．對于分批排序結(jié)構(gòu)性質(zhì)的研究在文獻(xiàn)中也沒見到

2、．第三部分研究了工件在限選機(jī)器上加工的若干平行機(jī)分批排序問題(第六章)． 在第二章中，本文研究了具有主次指標(biāo)的單機(jī)分批排序問題，其主要結(jié)果如下：證明了帶有到達(dá)時間、主指標(biāo)為最大完工時間的兩個問題是強(qiáng)NP．困難的：第一個是批容量有限制、次指標(biāo)為總存儲費(fèi)用的平行分批排序問題；第二個是批容量無限制、次指標(biāo)為最大延遲的繼列分批排序問題．給出了三個批容量無限制問題的多項(xiàng)式時間算法：第一個是帶有到達(dá)時間、主指標(biāo)為最大完工時間、次指標(biāo)為占用機(jī)

3、器總時間的繼列分批排序問題；第二個是主指標(biāo)為最大延遲、次指標(biāo)為最大完工時間的平行分批排序問題；第三個是主指標(biāo)為最大延遲、次指標(biāo)為誤工總數(shù)的平行分批問題．此外，給出了主指標(biāo)為最大延遲、次指標(biāo)為關(guān)于Cj的任意正規(guī)函數(shù)、批容量無限制的平行分批模型的擬多項(xiàng)式時間算法． 在第三章中，對于具有三重指標(biāo)的單機(jī)平行分批排序問題，主要給出了兩種批容量無限制平行分批模型的O(n2)時間算法：第一個問題是帶有到達(dá)時間、三個指標(biāo)依次為最大完工時間、占用

4、機(jī)器的總時間、總存貯費(fèi)用；第二個問題的三個指標(biāo)依次為最大延遲、最大完工時間、關(guān)于工件完工時間的任意正規(guī)函數(shù)． 在第四章中，對于若干批容量無限制的繼列分批和平行分批準(zhǔn)時排序問題，給出了當(dāng)每批恰有b個工件且工件有相同交工期時的O(nlogn)時間算法． 第五章主要研究批容量無限制的繼列分批和平行分批問題最優(yōu)特殊分批的存在性條件，目標(biāo)函數(shù)分別為：加權(quán)完工時間之和、總完工時間、完工時間平方之和及最大延遲．這里，特殊分批主要指僅分

5、一批和恰分n批． 第六章主要討論當(dāng)工件的加工長度均為1、每個工件Jj只能在限選機(jī)器(允許加工的機(jī)器)Mj上加工時的平行機(jī)分批排序問題，其中朋f是機(jī)器集合的某個子集．已知分批排序問題PIs-batch；Pj=1；A4jICm越可歸結(jié)為非分批問題Plnj=1；A4jIemax．Pinedo(1995)給出了當(dāng)子集族{Mj}是嵌套集族時的LFJ(1eastflexiblejobfirst)算法．這里給出了子集族{Mj}為一般情形的多項(xiàng)