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

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

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

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

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

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