發(fā)布時間：2018-01-22 23:54

  本文關鍵詞： 調度 資源約束 可重用資源 分支定界　出處：《上海交通大學》2014年碩士論文　論文類型：學位論文

【摘要】：汽車制造業(yè)的零部件入廠物流運輸采用專用料箱完成。專用料箱作為一種可重用資源，對運輸的完成至關重要。料箱不足，不但會影響車輛的裝載率，更會影響運輸的等待時間，甚至造成生產計劃的延誤，導致運輸效率低下。本文研究基于可重用空箱資源約束下的多車輛運輸調度問題，目標為最小化最大完工時間。 首先給出了問題的數學描述，根據一定的假設，將問題轉化為帶有資源約束的平行機調度問題，建立了混合整數線性規(guī)劃模型，為高效地得到問題的最優(yōu)解，本文設計了分支定界算法，并針對問題的上界、下界給出了多種設計方案。進一步，，為提高分支定界的計算規(guī)模，提出了滾動式分支定界算法。 為驗證算法性能，本文設計了合理的試驗參數并進行數值試驗。針對小規(guī)模問題，通過與CPLEX精確求解進行比較，驗證算法的有效性。進一步，對大規(guī)模問題，通過與啟發(fā)式算法比較，驗證滾動分支定界算法的有效性。結果表明，本文所提出的模型與滾動算法技巧具備有效性及高效性。 本文所提出的模型與算法具有一定的理論價值，對優(yōu)化零部件入廠物流具有一定的指導意義。
[Abstract]:As a kind of reusable resource, the special material box is very important to the completion of the transportation. The shortage of the material box will not only affect the loading rate of the vehicle. It will affect the waiting time of transportation, even lead to the delay of production plan, and lead to inefficient transportation. This paper studies the problem of multi-vehicle transportation scheduling based on the constraints of reusable empty box resources. The goal is to minimize the maximum completion time. Firstly, the mathematical description of the problem is given. According to certain assumptions, the problem is transformed into a parallel machine scheduling problem with resource constraints, and a mixed integer linear programming model is established to obtain the optimal solution of the problem efficiently. In this paper, a branch and bound algorithm is designed, and a variety of design schemes are given for the upper bound and lower bound of the problem. Furthermore, in order to improve the calculation scale of the branch and bound, a rolling branch and bound algorithm is proposed. In order to verify the performance of the algorithm, reasonable experimental parameters are designed and numerical experiments are carried out. For small scale problems, the validity of the algorithm is verified by comparing with CPLEX. The effectiveness of the rolling branch and bound algorithm is verified by comparing with the heuristic algorithm for large-scale problems. The results show that the model and the rolling algorithm presented in this paper are effective and efficient. The model and algorithm proposed in this paper have certain theoretical value, and have certain guiding significance for optimizing parts entry logistics.
【學位授予單位】：上海交通大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：U492.22

【參考文獻】

相關期刊論文 前7條

1 范靜,楊啟帆;機器帶準備時間的三臺平行機排序問題的線性時間算法[J];浙江大學學報(理學版);2005年03期

2 歐錦文,施保昌;平行機排序鄰域搜索算法設計[J];計算機工程與應用;2003年18期

3 徐武來;黎展滔;毛寧;陳慶新;;具有交貨期和工裝數量約束的平行機調度[J];機電工程技術;2012年09期

4 樊保強,董廣龍,曲桂東,張玉忠;帶約束的平行機排序問題[J];曲阜師范大學學報(自然科學版);2003年04期

5 談之奕,何勇;帶機器準備時間的平行機在線與半在線排序[J];系統(tǒng)科學與數學;2002年04期

6 羅守成;陳峰;唐國春;;平行機排序問題的列生成解法[J];系統(tǒng)科學與數學;2008年06期

7 陳榮軍;唐國春;;平行機的供應鏈排序[J];系統(tǒng)科學與數學;2010年02期

本文編號：1456085