本文關(guān)鍵詞：帶裝載和卸載的平行機調(diào)度問題

  更多相關(guān)文章： 調(diào)度 算法 最壞情況界 最大完工時間 配送中心 包裹運輸

【摘要】：本文主要研究帶服務器的平行機調(diào)度問題，服務器負責裝載和卸載的操作。對于帶服務器的平行機調(diào)度問題一般研究的是服務器負責裝載的操作，但隨著自動化的全面發(fā)展，既然在工件加工之前有安裝，相應的再將加工完成之后的工件從機器上卸載下來，這在實際的生產(chǎn)操作中也是一個很值得研究的問題。因此，本文的服務器既要負責裝載的操作又要負責卸載的操作，即工件在加工之前先由服務器負責把工件裝載到機器上，工件加工完成之后再由服務器把它從機器上卸載下來。由于增加了一個操作，在算法的設計上也增加了一定的難度，因此，本文首先研究帶單個服務器的可中斷的平行機調(diào)度問題；其次，再擴展到帶兩個服務器的不可中斷的平行機調(diào)度問題；最后應用經(jīng)典的LPT算法解決有關(guān)配送中心包裹的調(diào)度問題。通過比較隨機算法R的結(jié)果、LPT算法的結(jié)果以及最優(yōu)解值，得出LPT算法可以有效地解決包裹的調(diào)度問題。 本論文分為五章： 在第一章中，主要給出調(diào)度問題的相關(guān)知識以及有關(guān)調(diào)度問題算法的設計與分析，通過使用最壞情況界（或競爭比）來衡量一個算法的有效性。并介紹本文所要研究的帶服務器的調(diào)度問題的相關(guān)背景、研究現(xiàn)狀以及所要研究的問題。 在第二章中，研究只帶一個服務器的可中斷的平行機調(diào)度問題，每個工件在加工之前需要服務器先把它裝載到兩臺機器中的一臺上去，在加工完成之后再由該服務器把它從機器上卸載下來。該問題裝卸載的時間都是單位時間，目標是極小化最大完工時間。本文設計了一個算法OPA來解決該問題，并且證明該算法是最優(yōu)算法。 在第三章中，研究帶兩個服務器的平行機調(diào)度問題。這里的兩個服務器，一個負責在工件加工開始之前把工件裝載到機器上，另外一個負責在工件加工完成之后把工件從機器上卸載下來。這一章研究的是不可中斷的情況，裝卸載時間都是單位時間，目標是極小化最大完工時間。本文使用LS算法和LPT算法求解該問題，并證明它們的最壞情況界分別為8/5和6/5。 在第四章中，研究配送中心中有關(guān)包裹的調(diào)度問題。由于每天進入到配送中心的卡車數(shù)量比較多，而卸載點相對較少，如果不能對這些進入卡車進行合理的調(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é)就使用LPT算法嘗試解決該問題。通過幾個具體的實例，分別使用隨機算法R和LPT算法來對這些進入到配送中心的卡車進行調(diào)度安排，得到進入卡車的調(diào)度和相應的包裹流，再把用隨機算法R得到的結(jié)果和用LPT算法得到的結(jié)果與最優(yōu)解值進行比較，找到最壞情況界，，得出LPT算法可以有效地解決該問題。 第五章是對全文的總結(jié)以及對未來的展望。
【關(guān)鍵詞】：調(diào)度 算法 最壞情況界 最大完工時間 配送中心 包裹運輸
【學位授予單位】：浙江理工大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TH186
【目錄】：

• 摘要4-6
• Abstract6-10
• 1 緒論10-16
• 1.1 調(diào)度問題概述10-11
• 1.2 算法的設計與分析11-12
• 1.3 帶服務器的平行機調(diào)度問題12-13
• 1.4 目前國內(nèi)外的研究現(xiàn)狀13-15
• 1.5 論文結(jié)構(gòu)及主要研究成果15-16
• 2 帶單個服務器的平行機調(diào)度問題的最優(yōu)算法設計16-26
• 2.1 引言16-18
• 2.2 符號及最優(yōu)解下界18
• 2.3 最優(yōu)算法OPA18-24
• 2.4 小結(jié)24-26
• 3 帶兩個服務器的平行機調(diào)度問題26-38
• 3.1 引言26-27
• 3.2 預備知識27
• 3.3 LS算法27-32
• 3.3.1 LS算法的結(jié)構(gòu)28-30
• 3.3.2 LS算法的最壞情況界分析30-32
• 3.4 LPT算法32-37
• 3.5 小結(jié)37-38
• 4 LPT算法在配送中心的應用38-54
• 4.1 引言38
• 4.2 配送及配送中心概述38-40
• 4.3 問題背景描述40-44
• 4.3.1 包裹的轉(zhuǎn)移操作40-41
• 4.3.2 包裹的工作流41-44
• 4.4 三種關(guān)于包裹的調(diào)度44-48
• 4.4.1 隨機調(diào)度R45
• 4.4.2 最優(yōu)調(diào)度OPT45-47
• 4.4.3 LPT算法調(diào)度47-48
• 4.5 不同調(diào)度方法的比較48-53
• 4.6 小結(jié)53-54
• 5 總結(jié)與展望54-56
• 參考文獻56-60
• 攻讀學位期間的研究成果60-62
• 致謝62

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 徐俊剛,戴國忠,王宏安;生產(chǎn)調(diào)度理論和方法研究綜述[J];計算機研究與發(fā)展;2004年02期

本文編號：754684