帶裝載和卸載的平行機調(diào)度問題.pdf

1、本文主要研究帶服務器的平行機調(diào)度問題，服務器負責裝載和卸載的操作。對于帶服務器的平行機調(diào)度問題一般研究的是服務器負責裝載的操作，但隨著自動化的全面發(fā)展，既然在工件加工之前有安裝，相應的再將加工完成之后的工件從機器上卸載下來，這在實際的生產(chǎn)操作中也是一個很值得研究的問題。因此，本文的服務器既要負責裝載的操作又要負責卸載的操作，即工件在加工之前先由服務器負責把工件裝載到機器上，工件加工完成之后再由服務器把它從機器上卸載下來。由于增加了一個操

2、作，在算法的設計上也增加了一定的難度，因此，本文首先研究帶單個服務器的可中斷的平行機調(diào)度問題；其次，再擴展到帶兩個服務器的不可中斷的平行機調(diào)度問題；最后應用經(jīng)典的LP T算法解決有關(guān)配送中心包裹的調(diào)度問題。通過比較隨機算法R的結(jié)果、LP T算法的結(jié)果以及最優(yōu)解值，得出LP T算法可以有效地解決包裹的調(diào)度問題。
　　本論文分為五章：
　　在第一章中，主要給出調(diào)度問題的相關(guān)知識以及有關(guān)調(diào)度問題算法的設計與分析，通過使用最壞情況界

3、（或競爭比）來衡量一個算法的有效性。并介紹本文所要研究的帶服務器的調(diào)度問題的相關(guān)背景、研究現(xiàn)狀以及所要研究的問題。
　　在第二章中，研究只帶一個服務器的可中斷的平行機調(diào)度問題，每個工件在加工之前需要服務器先把它裝載到兩臺機器中的一臺上去，在加工完成之后再由該服務器把它從機器上卸載下來。該問題裝卸載的時間都是單位時間，目標是極小化最大完工時間。本文設計了一個算法OP A來解決該問題，并且證明該算法是最優(yōu)算法。
　　在第三章中，

4、研究帶兩個服務器的平行機調(diào)度問題。這里的兩個服務器，一個負責在工件加工開始之前把工件裝載到機器上，另外一個負責在工件加工完成之后把工件從機器上卸載下來。這一章研究的是不可中斷的情況，裝卸載時間都是單位時間，目標是極小化最大完工時間。本文使用LS算法和LP T算法求解該問題，并證明它們的最壞情況界分別為8/5和6/5。
　　在第四章中，研究配送中心中有關(guān)包裹的調(diào)度問題。由于每天進入到配送中心的卡車數(shù)量比較多，而卸載點相對較少，如果不

5、能對這些進入卡車進行合理的調(diào)度安排，就可能導致整個包裹轉(zhuǎn)移網(wǎng)絡的擁堵，從而導致更長的操作時間，所以如何對這些進來的卡車進行調(diào)度就顯得至關(guān)重要。合理的調(diào)度能夠降低操作費用，提高運輸系統(tǒng)的可靠性，并且提升配送中心的競爭力。但往往最優(yōu)的調(diào)度安排很難找到，如果找到一個調(diào)度，使得它接近最優(yōu)調(diào)度，那么這個調(diào)度也是合理的。這節(jié)就使用LP T算法嘗試解決該問題。通過幾個具體的實例，分別使用隨機算法R和LP T算法來對這些進入到配送中心的卡車進行調(diào)度安排