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

1、排序就是在一定的約束條件下對若干個要加工的工件或任務(wù)在指定的機器上按時間進度進行分配和調(diào)度，使某一個或某一些指標(biāo)達到最優(yōu)。 重新排序問題是一種新型的排序模型．它有著重要的實際應(yīng)用背景．生產(chǎn)部門根據(jù)自己的生產(chǎn)計劃或是由客戶提出的要求，在生產(chǎn)前一定時期內(nèi)事先有一個作業(yè)方案，將已有的任務(wù)或訂單按照某一規(guī)則安排好，使某一目標(biāo)值最優(yōu)．但是在即將開始生產(chǎn)之前或在生產(chǎn)過程中又有新的客戶訂單或任務(wù)到達．這時就要把新的任務(wù)和原有的還未加工的任務(wù)一

2、起加工．為了不失信于對原客戶的承諾或耽誤原任務(wù)的完成，這就要求在原有的工件或任務(wù)的次序不至于打亂的過多的前提下，使得總的目標(biāo)函數(shù)值達到最優(yōu)．Hall和Potts(2004)在前人研究的基礎(chǔ)上，系統(tǒng)地研究了重新排序問題．他們引入了序列錯位(sequence disruption)和時間錯位(time disruption)的概念，研究了在原來最優(yōu)排序和任意排序的基礎(chǔ)上重新排序，在原來排序的序列錯位和時間錯位不至于太大的情況下，使目標(biāo)函數(shù)最

3、優(yōu)的問題。 多目標(biāo)排序作為一種多目標(biāo)決策，在解決經(jīng)濟、管理、工程、軍事等領(lǐng)域出現(xiàn)的復(fù)雜問題中起著越來越重要的作用．例如，在一個工廠的生產(chǎn)過程中，生產(chǎn)決策者不但想要使工件的總完工時間最小以減少生產(chǎn)費用，還要盡量使誤工工件的個數(shù)最少，以更好地滿足顧客的要求．多目標(biāo)排序包括字典序最優(yōu)問題、Perato最優(yōu)解問題和組合目標(biāo)函數(shù)最優(yōu)問題。 在線排序是指每個工件的信息在該工件到達之前是未知的．在工件的到達時間得到該工件的所有信息并允

4、許對該工件進行加工；而且一旦決定工件的安排就不允許改變．而離線排序在安排所有工件之前便知道所有工件的信息．衡量一個在線排序算法最常用的指標(biāo)是它的競爭度(competitiveness)，即把在線排序算法的結(jié)果與對相同工件運用離線排序算法得到的最優(yōu)排序的結(jié)果進行比較．更確切的說，我們用競爭比(competitive ratio)ρ來衡量一個在線排序算法的性能．對于使目標(biāo)函數(shù)為最小的在線排序問題，競爭比ρ定義為對問題的所有實例的比值C/C<

5、,0>的上確界，其中C和C<,0>分別表示由這個在線排序算法得到的目標(biāo)函數(shù)值和相應(yīng)的離線排序的最優(yōu)值。 本文的內(nèi)容分四部分：第一部分研究了幾種特殊情形的重新排序模型(第二章)．第二部分研究了一種新型重新排序模型(第三章)。第三部分研究了多目標(biāo)的重新排序問題(第四章)．第四部分研究了在線的重新排序問題(第五章)。 在第二章中，研究了幾種特殊情形的重新排序模型，其主要結(jié)果如下：對一些未解問題和強NP-困難問題， (1)給出了

6、當(dāng)工件的加工時間與工期相容或原始工件保持其相對順序時，使得最大延遲和加工時間和為最小的多項式或擬多項式時間算法；(2)給出了當(dāng)工件具有相同的加工時間或具有相同的工期時，使得誤工和為最小的多項式或擬多項式時間算法； (3)給出了當(dāng)工件的加工時間與權(quán)重反相容時，使得加權(quán)完工時間和為最小的多項式或擬多項式時間算法。 在第三章中，對于具有到達時間的最小化最大完工時間的重新排序問題，(1)給出了在最大序列錯位約束下的最小化最大完工時間的重

7、新排序問題的多項式時間算法； (2)給出了在總序列錯位和約束下的最小化最大完工時間的重新排序問題的多項式時間算法； (3)證明了在最大時間錯位或總時間錯位約束下的最小化最大完工時間的重新排序問題是強NP-困難的。 在第四章中，對于多目標(biāo)的重新排序問題，本文將錯位量作為第二目標(biāo)來考察，研究了四種錯位量(D<,max>(π<'*>)，△<,max>(π<'*>)，∑D<,j>(π<'*>)，∑△<,j>(π<'*>))與傳統(tǒng)的目標(biāo)函

8、數(shù)(如C<,max>，L<,max>，∑w<,j>C<,j>)的相互組合問題，給出了多目標(biāo)排序中字典序最優(yōu)問題、Perato最優(yōu)解問題和線性組合目標(biāo)函數(shù)最優(yōu)問題的多項式時間算法或擬多項式時間算法。 在第五章中，主要研究了在線重新排序問題．即在原始工件已經(jīng)按照某一規(guī)則排好，而新工件在原始工件的加工過程中是按時間順序到達的．在此情形下，本文分別給出了在各種錯位量約束下，目標(biāo)函數(shù)為最小化最大延遲的競爭比為2的在線排序算法和最小化最大完