面向入厂物流的可重用资源约束调度模型及分支定界算法

发布时间：2018-01-22 23:54

本文关键词： 调度资源约束可重用资源分支定界　出处：《上海交通大学》2014年硕士论文　论文类型：学位论文

【摘要】：汽车制造业的零部件入厂物流运输采用专用料箱完成。专用料箱作为一种可重用资源，对运输的完成至关重要。料箱不足，不但会影响车辆的装载率，更会影响运输的等待时间，甚至造成生产计划的延误，导致运输效率低下。本文研究基于可重用空箱资源约束下的多车辆运输调度问题，目标为最小化最大完工时间。首先给出了问题的数学描述，根据一定的假设，将问题转化为带有资源约束的平行机调度问题，建立了混合整数线性规划模型，为高效地得到问题的最优解，本文设计了分支定界算法，并针对问题的上界、下界给出了多种设计方案。进一步，，为提高分支定界的计算规模，提出了滚动式分支定界算法。为验证算法性能，本文设计了合理的试验参数并进行数值试验。针对小规模问题，通过与CPLEX精确求解进行比较，验证算法的有效性。进一步，对大规模问题，通过与启发式算法比较，验证滚动分支定界算法的有效性。结果表明，本文所提出的模型与滚动算法技巧具备有效性及高效性。本文所提出的模型与算法具有一定的理论价值，对优化零部件入厂物流具有一定的指导意义。
[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

【参考文献】