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

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

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

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

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

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