含有雙重在線(xiàn)限制的排序問(wèn)題.pdf

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

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