含有雙重在線限制的排序問題.pdf

1、排序論是運籌學(xué)的一個非?；钴S的分支，具有廣泛而又直接的應(yīng)用前景。排序問題是組合最優(yōu)化領(lǐng)域中的一類重要問題。而在線排序因其研究的內(nèi)容非常具有實際意義，從而更加引人關(guān)注。 在線排序一般分為兩種；列表在線排序和時間在線排序。在前一種模型里，工件是排列成一個表逐個出現(xiàn)的，一個工件只有當(dāng)表中排在其前面的工件都安排以后才知道這個工件的有關(guān)信息。在后一種模型中，工件隨著時間進行安排，在任何時刻只知道當(dāng)前已到達(dá)的工件信息。在二種模型中，工件一旦

2、被安排就不允許改變。 本文研究的模型是同型機在線排序問題，其中工件的到達(dá)方式是on-lineovertime，并且工件之間具有序約束(precedence constraints)，目標(biāo)函數(shù)是最小化最大完工時間．所以從某種意義上說，本文的排序模型是兩種在線排序模型的復(fù)合(即使n個工件同時到達(dá)，它們的信息也是逐個釋放的)。在第一章中，主要向大家介紹了排序問題產(chǎn)生的背景和一些相關(guān)基礎(chǔ)知識。在第二章中，研究了同型機條件下雙重在線復(fù)合排