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

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

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

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

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

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