在線生產(chǎn)調(diào)度策略的設(shè)計(jì)與分析.pdf

1、本文主要討論在線生產(chǎn)調(diào)度問題，并對這類調(diào)度問題設(shè)計(jì)和分析策略。在文獻(xiàn)中，確定性調(diào)度模型已經(jīng)被廣泛研究。這類研究模型的一個基本假設(shè)是所有信息在調(diào)度之前全部知道。然而，這個假設(shè)又常常是不切實(shí)際的。這種現(xiàn)實(shí)情況使得在線調(diào)度問題備受關(guān)注。在在線調(diào)度問題里，在線策略通常在沒有未來信息的情況下做決策。本文用競爭分析方法來分析在線策略的效果。具體來講，用競爭比作為度量標(biāo)準(zhǔn)。這個指標(biāo)分析策略在最壞情況下的效果。相對于在線策略，離線最優(yōu)策略是在決策之前對

2、需求序列信息完全知道，并做出最優(yōu)決策。
　　論文主要研究兩種在線生產(chǎn)調(diào)度模式。第一種，訂單以列表方式到達(dá)或一個一個到達(dá)。需求序列里的訂單存儲在列表里，并當(dāng)列表頭一個訂單被安排加工后下一個訂單才出現(xiàn)。第二種，訂單隨時間到達(dá)。每個訂單都對應(yīng)一個到達(dá)時刻，并在此時刻后，它才能夠被加工?；谶@兩個模式，本文研究了不同的調(diào)度模型：單機(jī)調(diào)度、平行機(jī)調(diào)度、不同速度平行機(jī)器調(diào)度、批處理機(jī)調(diào)度和流水線調(diào)度。對于每一個問題都先給出在線問題競爭比下界。

3、然后，設(shè)計(jì)并分析在線策略。對于某些問題，本文所設(shè)計(jì)的策略是最優(yōu)策略。這里最優(yōu)策略意味著該策略的競爭比與所對應(yīng)在線調(diào)度問題競爭比的下界相等。
　　本文貢獻(xiàn)主要集中在以下五部分。
　　·第一部分研究單機(jī)模型不同目標(biāo)函數(shù)的兩個問題：最小化一般性總完工時間（或稱為完工時間α次冪之和）以及最小化變形的總延遲（或延遲與預(yù)期交貨時間之和）。對于第一個問題，證明了D-SPT是最優(yōu)策略。當(dāng)a-l時，Vestjens提出并證明D-SPT策略是最

4、優(yōu)策略。這個結(jié)果是本文的一個特例，即本文得到的是更一般化的結(jié)果。對于第二個問題，證明D-SWPT策略的競爭比是3。此后，進(jìn)一步分析兩個擴(kuò)展問題，同時設(shè)計(jì)了M-D-SWPT策略并分析其效果。在在線調(diào)度研究中，本文第一次提出并研究以總延遲為目標(biāo)的在線問題。
　　·第二部分本文研究兩平行機(jī)模型并行訂單在線調(diào)度問題。并行訂單需要一定數(shù)目的機(jī)器同時加工才能完成。訂單加工時間在一定區(qū)間范圍。目標(biāo)是最小化加工時間跨度，即系統(tǒng)中最后一個訂單的完成

5、時間。本文利用更多的信息，提出了與文獻(xiàn)中相比具有更小競爭比的在線策略。
　　·第三部分本文研究兩不同速度平行機(jī)模型調(diào)度問題。考慮的約束條件是兩機(jī)器中一臺是周期性不可用。訂單加工過程中不允許搶占。目標(biāo)是最小化加工時間跨度。本文對不同情況給出了不同下界，同時證明LS策略在一些情況下是最優(yōu)的。在在線調(diào)度研究中，本文第一次提出并研究具有周期性可用性約束的在線問題。
　　·第四部分本文研究m不同速度平行機(jī)在線調(diào)度模型。主要討論兩個問題

6、。在第一個問題里，不允許搶占。目標(biāo)是最小化加權(quán)完工時間。本文證明R-LIST策略的競爭比是√4m-√3+3/2。在第二個問題里，允許搶占。目標(biāo)是最小化總加權(quán)完工時間。本文證明了在一定條件下，WSPT-1策略的競爭比是2。當(dāng)m=2時，LiuandLu證明了R-LIST和WSPT-1分別是2.618和2一競爭的。這個結(jié)果是本文的一個特例，即本文獲得了更一般化的結(jié)果。
　　·第五部分討論兩個關(guān)于批加工機(jī)器模型里在線調(diào)度問題。一個批加工機(jī)

7、器可以同時加工B個訂單。我們研究無界批加工機(jī)器模型，即一批可以加工無窮多個訂單。一起加工的訂單構(gòu)成一批，并且這些訂單同時開始同時結(jié)束。批加工機(jī)器的加工時間由這一批里最長訂單的加工時間決定。第一個問題，兩平行批加工機(jī)器模型最小化時間跨度。訂單按其加工時間非降序到達(dá)情況下，我們給出了最優(yōu)策略。本文利用更多的信息，提出了與文獻(xiàn)中相比具有更小競爭比的在線策略。第二個問題，m批加工機(jī)器流水車間模型最小化時間跨度。訂單在各個機(jī)器上的加工時間相同且訂