【作者】 王勇；

【导师】 钟金宏；

【作者基本信息】 合肥工业大学 ， 管理科学与工程， 2016， 硕士

【摘要】 随着市场竞争的日益激烈,企业需要与其供应链内外伙伴紧密协作,以最小的成本为客户提供更好的产品和服务。外包可以降低成本,改进顾客服务质量,已成为企业的常用策略。在动态批量问题研究方面,考虑生产能力限制的文献要多于考虑库存能力；考虑外包的动态批量问题研究多限于单产品,多产品方面研究很少。同时考虑生产能力、库存能力和外包的多产品动态批量问题研究尚未发现,而对企业来说,这些因素是同时存在的,因此本文开展这方面研究。论文综述了多产品动态批量问题的研究现状,以及拉格朗日松弛方法在多产品动态批量问题的应用。概述了动态批量问题的基本模型、外包、拉格朗日松弛算法、动态规划算法和启发式算法。建立了考虑生产工时约束、有限库存和外包的多产品动态批量问题模型,模型中生产成本为带固定费用的线性函数,外包和库存成本为线性函数,不允许延期交货。每种产品的生产时间包括启动时间和加工时间,在每个周期,生产所有产品消耗的总工时受限,外包量不超过当周期需求。设计了基于拉格朗日松弛的求解算法,松弛掉原问题中耦合的生产工时约束,将原问题转化为N个单产品有界库存模型,给出了动态规划求解算法；提出了一种4阶段可行解构造策略,即前向移动、单步后向移动、外包移动和单周期优化,前3个阶段肯定可得到可行解,第4阶段仅针对同时有外包和生产的周期。在仿真实验中,首先验证了所提算法的有效性,分别对具有不同周期、不同产品数的多组问题实例,比较所提算法和LINGO的运算结果。接着给出了一个完整算例,展示了动态规划算法求出的子问题解和拉格朗日松弛算法得到的原问题解。进行了6组可行解构造策略影响实验,显示了单周期优化阶段总能降低总成本降低,4阶段构造策略的成本上下界均最低。通过改变产品数和周期数构造了12组实例,展示了所提算法在不同规模问题上的相对对偶间隙和运行时间。进行了不同生产工时对算法性能的影响实验。在所有实验中,相对对偶间隙均在2%以内。更多还原

【Abstract】 With the intense market competition, the enterprises need to coorperate with their suppliers more closely and provide better products and service for the customers with the lowest costs. Outsourcing has been a common stragety, which can both reduce the costs and improve the service level. In the research of dynamic lot-sizing problem, the articles which consider production capacity are more than that consider inventory capacity, and studies about dynamic lot-sizing problem with outsourcing are usually limited to single-item, less in multi-item. The articles in the research of multi-item dynamic lot-sizing problem which consider product capacity, inventory capacity and outsourcing at the same time haven’t been found. For an enterprise, these factors existed meanwhile which should been considered. Therefore this article researched the multi-item dynamic lot-sizing problem with restricted resource and outsourcing.This paper overviewed the research status of multi-item dynamic lot-sizing problem, and summarized the application of Lagrangean relaxation on multi-item dynamic lot-sizing problem. A brief summarization was given about basic theory of dynamic lot-sizing problem, outsourcing, Lagrangean relaxation algorithm, dynamic programming algorithm and heuristic algorithm.A multi-item dynamic lot-sizing model which considered production time constraint, limited storage capacity and outsourcing is built, where the production cost funciton is linear with fixed cost, outsourcing cost and holding cost are also linear and backlogging is not allowed. The production time of one product include setup time and processing time. In each period, the total prodution time for all products is limited. For a product, outsourcing quantity must be less than or equal to the demand of the current period.An algorithm based Lagrangean relaxation is developed to solve this problem. The constraints of production time capacity are relaxed into the objective funciton, and the problem can be decomposed into N subproblems with limited storage capacity. A dynamic programming algorithm is developed to solve these subproblem. A heuristic algorithm is proposed to construct feasible solutions, which include 4 phases called forward pass, single step backward pass, outsourcing pass and single period optimization. The first three phases are used to construct the feasible solutions and the last phase is used to improve the solution.In the simulation experiment, the effectiveness of the Lagrangean relaxation algorithm is verified by comparing the calculation result with commercial software LINGO under the same example. Then an integral demo example is given, the primal solution computed by dynamic programming algorithm and the feasible solution provided by Lagrangean relaxation heuristic algorithm are also showed. Six experiments are proposed to test the performance of different feasible solution construction strageties. Twelve instances with different product number and period number are used to test the total performance of the Lagrangean relaxation algorithm. In all experiments, the relative duality gap are within 2%.更多还原