本文關鍵詞：帶裝載和卸載的平行機調度問題

  更多相關文章： 調度 算法 最壞情況界 最大完工時間 配送中心 包裹運輸

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

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

【參考文獻】

中國期刊全文數據庫 前1條

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

本文編號：754684