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

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

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

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

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

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