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

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

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

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

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

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