多目標(biāo)分批排序及其相關(guān)課題.pdf

1、在過(guò)去的50年中，機(jī)器排序問(wèn)題已成為組合最優(yōu)化中最活躍的研究課題之一.然而，在大多數(shù)經(jīng)典的排序文獻(xiàn)中，只考慮機(jī)器一次至多加工一個(gè)工件，且目標(biāo)函數(shù)只有一個(gè).隨著時(shí)間的推移，分批排序和多目標(biāo)排序已蓬勃發(fā)展起來(lái).可是將兩者（分批排序和多目標(biāo)排序）結(jié)合起來(lái)的研究尚不多見(jiàn).由于電子加工業(yè)及其它產(chǎn)業(yè)的高速發(fā)展，以及決策者的不同利益需求，將分批排序與多目標(biāo)排序結(jié)合起來(lái)考慮，應(yīng)該提到議事日程上.
　　 設(shè)n個(gè)無(wú)關(guān)的工件J1，J2，...，Jn，

2、它們將在一臺(tái)分批處理機(jī)上加工.工件Jj的加工時(shí)間、工期、期限和權(quán)分別為pj、dj、dj和wj（j=1，…，n）.以Sj和Gj分別表示工件Jj的開(kāi)始加工時(shí)間和完工時(shí)間.給定一個(gè)序σ，Lj（σ）=Cj（σ）-dj與Lmax（σ）=maxnj=Lj（σ）分別表示工件Jj的延遲與序σ的最大延遲.Tj=max{0，Lj}為工件Jj的延誤，Uj為它的單位懲罰因子.本論文主要考慮分批處理機(jī)上同時(shí)最小化雙目標(biāo)排序問(wèn)題.所謂的分批處理機(jī)是指機(jī)器可同時(shí)加工

3、多個(gè)工件，放在一起加工的工件集稱為一批，同一批中的工件具有相同的開(kāi)工時(shí)間和完工時(shí)間.根據(jù)批的加工時(shí)間的不同定義，分批處理機(jī)又分為平行分批處理機(jī)和序列分批處理機(jī).對(duì)前者，一批的加工時(shí)間等于這一批中最長(zhǎng)工件的加工時(shí)間.這一模型是由半導(dǎo)體加工的烘烤、計(jì)算機(jī)系統(tǒng)及其它領(lǐng)域的操作抽象而來(lái)的.對(duì)后者，一批的加工時(shí)間等于這一批中所有工件的加工時(shí)間之和，且在每一批加工開(kāi)始前，都有一個(gè)常數(shù)s的安裝時(shí)間.這一模型起源于現(xiàn)實(shí)生活中這樣的要求：當(dāng)一批工件加工完

4、成后，需要一段時(shí)間來(lái)調(diào)換工具、維修機(jī)器等.另一方面，兩個(gè)目標(biāo)函數(shù)可以代表兩個(gè)決策者的不同利益.這一方向發(fā)展的基本動(dòng)機(jī)源于這樣的事實(shí)：質(zhì)量評(píng)估通常是一個(gè)多維概念.并且決策者常常追求多個(gè)目標(biāo)同時(shí)最優(yōu)化一對(duì)所有目標(biāo)函數(shù)找出全部的Pareto最優(yōu)序.稱一個(gè)可行序σ是關(guān)于目標(biāo)函數(shù)f和g的Pareto最優(yōu)序，是指不存在可行序π，使得，（π）≤f（σ），g（π）≤g（σ），且其中這兩個(gè)不等式至少有一個(gè)嚴(yán)格成立.
　　 本學(xué)位論文的主要研究成果

5、如下：
　　 1.單機(jī)平行分批的雙目標(biāo)排序
　　 前人分別對(duì)雙目標(biāo)及平行分批兩方面已得到一些結(jié)果.例如，證明了同時(shí)最小化最大延遲和最大費(fèi)用函數(shù)的單機(jī)排序問(wèn)題可在O（n3logn）時(shí)間內(nèi)解決.在平行分批處理機(jī)上，當(dāng)機(jī)器容量無(wú)界時(shí)，最小化最大延遲問(wèn)題已有O（n2）時(shí)間的動(dòng)態(tài)規(guī)劃算法.而我們考慮兩方面的結(jié)合，即同時(shí)最小化最大延遲和最大完工時(shí)間的平行分批排序問(wèn)題，并給出一個(gè)O（n3）時(shí)間的多項(xiàng)式時(shí)間算法，可以求出全部Pareto

6、最優(yōu)解.對(duì)多目標(biāo)優(yōu)化問(wèn)題而言，求出全部Pareto最優(yōu)解是最完整的解答.另外，當(dāng)機(jī)器容量有界，且工件的加工時(shí)間為常數(shù)時(shí)，以總延誤為主指標(biāo)，次指標(biāo)分別是誤工工件數(shù)、加權(quán)誤工工件數(shù)和加權(quán)總完工時(shí)間的分層最小化問(wèn)題已有O（n3）時(shí)間算法.我們統(tǒng)一地給出O（nlogn）時(shí)間算法，改進(jìn)了上述時(shí)間界.
　　 2.單機(jī)序列分批的雙目標(biāo)捧序
　　 對(duì)于序列分批的單目標(biāo)排序問(wèn)題，當(dāng)機(jī)器容量無(wú)界時(shí)，最小化最大延遲問(wèn)題已有O（n2）時(shí)間的算法

7、；最小化加權(quán)總完工時(shí)間也已有了O（n）時(shí)間的算法.對(duì)于雙目標(biāo)問(wèn)題，沒(méi)有已知結(jié)果.我們?cè)贠（n2）時(shí)間內(nèi)解決了同時(shí)最小化最大延遲和最大完工時(shí)間問(wèn)題.此外，對(duì)同時(shí)最小化最大完工時(shí)間和總完工時(shí)間問(wèn)題，在機(jī)器容量無(wú)界或有界的情形下，我們分別給出O（m2）時(shí)間算法.以上算法均可求出全部Pareto最優(yōu)解，獲得完全的解答.
　　 3.單機(jī)雙目標(biāo)排序
　　 已知最小化具有截止時(shí)間的誤工工件數(shù)問(wèn)題是NP-困難的.對(duì)如下特殊情形的誤工工件

8、數(shù)問(wèn)題，文獻(xiàn)中已有O（n2）時(shí)間的后向算法.（?。┤绻鹍i≤dj，那么di≤dj與pi≤pj；（ⅱ）如果pi≥pj，那么di-dj≤pi-pj.為建立統(tǒng)一的理論，我們提出了一種對(duì)偶算法一前向的貪婪算法，對(duì)情形（?。?，它有更好的時(shí)間界O（nlogn）.對(duì)情形（ⅱ），得到相同的時(shí)間界，但方法有不同特點(diǎn).并且我們還研究了工件加工時(shí)間相等的情形，也找到了O（nlogn）時(shí)間算法.
　　 因?yàn)椴煌臎Q策者對(duì)同一個(gè)工件的工期要求可能不同（它