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

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

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

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

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

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

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

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

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