大規(guī)模排序問題的列生成算法研究.pdf

1、排序論又稱為時間表理論，它是為滿足一個或者多個優(yōu)化目標(biāo)，安排稀缺資源，執(zhí)行任務(wù)的決策過程。一般認為，1954年,Johnson的論文[52]是經(jīng)典排序的第一篇文章，從此排序論迅速發(fā)展起來。隨著社會的發(fā)展，新的問題及模型層出不窮，同時伴隨著問題的規(guī)模越來越大，因此從解決實際需要出發(fā)，從歸結(jié)得到的排序模型具有實際應(yīng)用意義的角度來看，對于大量NP-難的排序問題，設(shè)計精確算法是目前排序論研究中一個值得深入研究的課題。對于大規(guī)模的NP

2、-難的組合優(yōu)化問題，已有的精確算法有分支定界算法，動態(tài)規(guī)劃算法，以及列生成算法[62，76，85，95，99]等。最初，列生成方法是Ford與Fulkerson [34]在1958年求解最短路問題時提出，后來它在求解整數(shù)規(guī)劃方面得到很好的應(yīng)用。但是很少的文獻應(yīng)用列生成方法來求解NP-難的排序問題，van den Akker et a1.[87]結(jié)合D-W分解和分支定界方法，對于所有GJ的正則目標(biāo)函數(shù)，給出了經(jīng)典單機排序問題的列

3、生成算法。1999年，陳志龍和Powell[25]討論了經(jīng)典排序問題α||∑ Fj(Cj)的列生成算法，這里α∈{P，Q，R}，他們在[26]中給出了JIT(just-in-time)平行機排序問題的列生成算法。本文主要研究結(jié)果包括以下幾個方面：一是研究NP-難的成組加工排序問題的列生成算法；二是建立一種新型排序—柔性同時加工排序模型，討論它的復(fù)雜性并設(shè)計精確算法。三是對現(xiàn)代排序問題，資源受限的確定性排序問題進行了研究。在

4、第—章，首先介紹了排序問題的基本知識和分類方法，然后介紹了列生成方法在整數(shù)規(guī)劃方面的應(yīng)用，以及關(guān)于求解大規(guī)模排序問題的列生成算法。經(jīng)典的排序中更換工件所需要的安裝時間是假設(shè)與機器無關(guān)的，并且與工件的排法也無關(guān)。然而在實際問題中，工件在機器上加工前所需要的安裝時間往往是與排法有關(guān)的，在第二章，我們考慮了成組加工排序問題。分別討論一臺機器和m臺機器環(huán)境下，大規(guī)模的NP-難問題的列生成算法，并通過試驗，驗證了我們的算法的有效性。

5、在第三章考慮了一種新型的排序模型—柔性同時加工排序問題，系統(tǒng)地討論了它在不同的工件約束條件，以及不同的目標(biāo)函數(shù)下，柔性同時加工排序問題的計算復(fù)雜性。給出機器容量和時間滿足一致性，目標(biāo)是工件完工時間和的柔性同時加工平行機排序問題的列生成算法。最后考慮到企業(yè)的市場競爭，生產(chǎn)成本和資源的限制，例如機器加工能力的限制，較少的生產(chǎn)線，庫存限制等等，在第四章，主要研究機器加工和倉儲的綜合準(zhǔn)時排序問題，討論了倉庫容量有限，一臺機器，目標(biāo)函