關(guān)于重新排序的一些結(jié)果.pdf

1、排序論作為運(yùn)籌學(xué)的一個分支，有著深刻的理論意義和廣闊的應(yīng)用前景。所謂排序問題就是指在一定的約束條件下，對工件和機(jī)器按時間進(jìn)行分配和安排加工次序，使一個或多個目標(biāo)達(dá)到最優(yōu).它可以分為經(jīng)典排序和現(xiàn)代排序.近幾十年來，有關(guān)現(xiàn)代排序的研究有了很大的發(fā)展，新的排序模型也不斷涌現(xiàn).常見的現(xiàn)代排序模型有可控排序、成組分批排序、在線排序、同時加工排序、資源受限排序、多目標(biāo)排序和帶有運(yùn)輸考慮的排序等等.在本文中，我們研究了一種新的模型-重新排序。該模型可

2、描述如下：一批原始工件已經(jīng)按某種目標(biāo)排好序，但是還沒有被加工，而此時又有一批新工件來到.決策者需要把這些工件插入到原排序中進(jìn)行重新排序，而原來的工件可能產(chǎn)生錯位.本文所研究的問題是在有錯位影響的約束下使排序花費(fèi)達(dá)到最小.我們用π*表示原始工件的最優(yōu)排序，用σ表示所有工件(包括原始工件和新到工件)的任意排序。用Dj(π*，σ)和△j(π*，σ)分別表示工件j在π*和σ之間產(chǎn)生的順序錯位和時間錯位，分別簡寫為Dj(π*)和△j(π*)。本文

3、用到的錯位主要有以下幾個：Dmax(π*)表示工件的最大序錯位；∑Dj(π*)表示工件的總序錯位；△max(π*)表示工件的最大時間錯位；∑△j(π*)表示工件的總時間錯位。 本篇論文的工作是Hall和Potts等人(2004)的研究工作的發(fā)展，主要研究兩種重新排序模型：極小化所有工件的排序花費(fèi)和極小化總的花費(fèi)目標(biāo)(其中包括排序的花費(fèi)和錯位花費(fèi))。主要結(jié)果如下： (1)問題1｜Dmax(π*)≤k1，△max(π*)≤k

4、2，∑Dj(π*)≤k3，∑△j(π*)≤k4｜∑Cj在O(n2on2Nmin{nOPN，nNPO})時間內(nèi)可解；(2)問題1||Lmax+μ1Dmax(π*)+μ2△max(π*)在O(n+nNlognN)時間內(nèi)可解；(3))問題1‖∑Cj+μ1Dmax(π*)+μ2△max(π*)在O(n+nNlognN)時間內(nèi)可解；(4)問題1‖∑Cj+μ1∑Dj(π*)+μ2∑△j(π*)在O(n+nNlogn)時間內(nèi)可解.另外本文還得到對目標(biāo)