供应链调度中的生产计划与分批策略研究

发布时间：2018-08-09 11:21

【摘要】：生产调度问题是一类经典的组合最优化问题,研究如何合理分配和调度有限资源以获得最大效益,在实际的生产中具有广泛的应用。高效的调度方案可以提高生产设备利用率、降低成本,增加企业的利润。供应链调度问题是生产调度问题的扩展,研究的是供应链的成员们(包括供应商、制造商、分销商和第三方物流等)在信息共享的基础上,为了达到缩短产品交货期,降低整条供应链运作成本的目标,实行联合(或协同)的调度,对生产制造领域有着重要的研究价值。首先,本文对供应链调度问题的研究背景和意义进行了归纳总结并对其国内外研究现状做了详细介绍。其次,对组合优化问题、调度问题、相关算法及计算复杂性进行了回顾,同时对于调度问题的求解思路以及本文所采用的主要算法做了简单介绍。然后,研究了带有分批配送的供应链调度问题。我们先对原始问题作了复杂性分析,证明了该问题是强NTP-hard问题；对于配送批次有常数上界的情形,我们证明了是一般的NP-hard问题,并设计了完全多项式时间算法(FPTAS)。另外,我们还研究了三个多项式可解的子问题,对每个子问题设计了相应的多项式时间最优算法,并通过计算实例,验证了算法的有效性。接着,研究了具有恶化效应的供应链调度问题。同样地,我们先对原始问题作了复杂性分析,证明了该问题是强NP-hard问题,并进一步证明了该问题不存在常数最坏情况界的多项式时间算法,除非P=NP；对于到达批次有常数上界的情形,我们对其做了复杂性分析,证明了该问题仍然是强NP-hard问题,并设计了FPTAS。最后,我们对两个模型中设计的FPTAS通过数据试验,采用MATLAB软件对算法进行编程,对随机给定的实例找到了工件的最优批次数,每个批次工件的最优加工顺序,并求出了最优目标值,验证了FPTAS的有效性。
[Abstract]:Production scheduling problem is a classical combinatorial optimization problem. It is widely used in practical production to study how to reasonably allocate and schedule finite resources to obtain maximum benefit. The efficient scheduling scheme can increase the utilization rate of production equipment, reduce the cost and increase the profit of the enterprise. The supply chain scheduling problem is an extension of the production scheduling problem. In order to shorten the product delivery time, the members of the supply chain (including suppliers, manufacturers, distributors and third party logistics, etc.) are studied on the basis of information sharing. To reduce the operation cost of the whole supply chain and to implement joint (or cooperative) scheduling has important research value in the field of production and manufacturing. Firstly, this paper summarizes the research background and significance of supply chain scheduling problem and introduces the current situation of supply chain scheduling problem at home and abroad. Secondly, the combinatorial optimization problem, scheduling problem, related algorithms and computational complexity are reviewed, and the idea of solving the scheduling problem and the main algorithms used in this paper are briefly introduced. Then, the supply chain scheduling problem with batch distribution is studied. We first analyze the complexity of the original problem and prove that the problem is a strong NTP-hard problem, and for the case where the distribution lot has a constant upper bound, we prove that it is a general NP-hard problem, and design a complete polynomial time algorithm (FPTAS). In addition, we also study three polynomial solvable subproblems, design corresponding polynomial time optimal algorithm for each subproblem, and verify the validity of the algorithm by an example. Then, the supply chain scheduling problem with deterioration effect is studied. Similarly, we first analyze the complexity of the original problem, prove that the problem is a strong NP-hard problem, and further prove that the problem does not have a polynomial time algorithm for the worst-case bound of constants, unless the problem is a NP-hard problem. For the case where the batch has a constant upper bound, we analyze its complexity, prove that the problem is still a strong NP-hard problem, and design a FPTAS. Finally, the FPTAS designed in the two models is tested by data, and the algorithm is programmed by MATLAB software. The optimal batch number of the workpiece and the optimal processing order of each batch are found for the random given instance. The optimal target value is obtained, and the validity of FPTAS is verified.
【学位授予单位】：浙江工商大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F274;F272

【参考文献】