帶有交貨期窗口和加工時(shí)間可控的幾類單機(jī)排序問題.pdf

1、在很多關(guān)于排序問題的文獻(xiàn)中，每個(gè)工件有固定的加工時(shí)間，但在現(xiàn)實(shí)的生產(chǎn)過程中，工件的加工時(shí)間可能會(huì)受到退化效應(yīng)、學(xué)習(xí)效應(yīng)、接受的資源量、工件的加工位置等因素的影響，從而產(chǎn)生變化。近幾年，越來越多的研究者開始關(guān)注加工時(shí)間可控的排序問題。此外，在一些排序問題中會(huì)帶有交貨期窗口，只要工件完工發(fā)生在交貨期窗口外，就會(huì)產(chǎn)生相應(yīng)的提前、延誤費(fèi)用。本文主要研究了帶有交貨期窗口和加工時(shí)間可控的幾類單機(jī)排序問題，具體內(nèi)容如下：
　　第一章，主要介紹了

2、排序問題的背景知識(shí)、研究近狀以及本文的主要研究?jī)?nèi)容。
　　第二章，討論了帶有維護(hù)活動(dòng)和多交貨期窗口的單機(jī)排序問題，其中討論了兩種不同的維護(hù)活動(dòng)：依賴于時(shí)間、資源的維護(hù)活動(dòng)；依賴于位置、資源的維護(hù)活動(dòng)。我們分別討論了三種不同的維護(hù)位置，針對(duì)每一個(gè)維護(hù)位置都給出了多項(xiàng)式時(shí)間算法。
　　第三章，在上一章的基礎(chǔ)上，研究了工件的加工時(shí)間分別可控，即每一個(gè)工件的加工時(shí)間都存在多種可能性，每一個(gè)可能的加工時(shí)間都會(huì)產(chǎn)生相對(duì)應(yīng)的費(fèi)用。經(jīng)過分析

3、計(jì)算，我們發(fā)現(xiàn)最優(yōu)排序存在于三種不同的維護(hù)位置中，按照不同的情況給出了多項(xiàng)式時(shí)間算法。
　　第四章，對(duì)具有交貨期窗口的排序問題進(jìn)行了進(jìn)一步的探究，工件會(huì)接受一定的資源，加工時(shí)間也會(huì)隨之受到影響。我們討論了兩種類型的交貨期窗口問題：多個(gè)交貨期窗口問題、公共交貨期窗口問題。在求解目標(biāo)函數(shù)的過程中，存在一定的約束條件。在滿足約束條件的情況下，我們給出了計(jì)算復(fù)雜性是O(n3)的多項(xiàng)式時(shí)間算法。
　　最后對(duì)本文進(jìn)行總結(jié)并提出今后的研究