【作者】 韩毅；

【导师】 唐加福；

【作者基本信息】 东北大学 ， 系统工程， 2009， 博士

【摘要】 物料需求计划(Material Requirements Planning, MRP)是制造资源计划/企业资源计戈(?)J(Manufacturing Resource Planning/Enterprise Resource Planning, MRPII/ERP)的基础,同时也是供应链管理(Supply Chain Management, SCM)的基础。在制造和分销企业中,遇到的最普遍的决策问题就是与MRP相关联的决策问题。虽然这些决策问题是这些企业每天都要面对的问题,但是并不意味着这些问题就是容易解决的。MRP是制造系统中协调产成品(由半成品和部件组成)补充决策的方法。MRP确保了在恰当的时间点制造系统中各个层次上的组件都具有足够的数量,使顾客对产成品的需求可以得到满足。由于组件数量的大小直接影响了生产系统的性能和生产力,而生产力是制造企业在市场中保持竞争力的重要因素,因此生产批量计划问题是MRP系统中的关键问题。由于MRP只能提供生产批量计划问题的可行解,因此寻找高质量解(具有最小成本的补充数量)的问题随之而来。实践证明当现实中的产品由几百个部件组成时,这个问题是一个棘手的组合优化问题。在生产批量计划问题的早期工作中,大部分研究集中于特定环境下的最优解算法。然而,只有较小规模的问题可以在合理的时间内得到最优解。随着问题规模的增加,所需要的计算量(更不用说它们的复杂性)也极度增加。这种情况促使人们需要开发大量的求解算法,使得计算时间和成本效益能够令人满意地得到平衡。生产批量计划问题可以分为多种类型。从生产能力来看,包括有资源约束和无资源约束批量计划问题；从产品的结构角度看包括单级结构、线型结构、装配结构和一般结构的批量计划问题；还有以需求方式角度来划分的固定需求、时变需求、随机需求和模糊需求环境下的批量计划问题等。由于生产批量计划问题起源于20世纪50年代,至今为止,关于生产批量计划问题模型方面的研究已经十分成熟,因此本文主要针对确定需求环境下具有不同生产结构的生产批量计划问题的求解算法进行了研究,设计了几种亚启发式(Meta-heuristic)算法。本文的主要工作包括：(1)对生产批量计划问题的相关研究进行了综述。介绍了生产批量计划问题的产生背景和概况,阐述了具有不同产品结构的生产批量计划问题的各种模型,概述了可以用于求解生产批量计划问题的相关亚启发式算法。(2)提出了可求解无资源约束多级生产批量(Multilevel Lot-sizing, MLLS)问题的粒子群优化(Hybrid Particle Swarm Optimization, HPSO)算法。传统的PSO算法是在具有连续定义域的实优化问题中寻优的有效工具,通过将传统PSO算法中粒子的速度和位置、加法、乘法等运算规则进行了重新定义,使得PSO算法能够求解具有二进制变量的MLLS问题,扩展了PSO算法的应用领域。在此基础上,对二进制版本的HPSO算法进行调整和变化,引入柔性惯量和反捕食概念,形成带有柔性惯量的PSO算法和带柔性惯量的反捕食PSO算法。通过计算算例表明了几种PSO算法对MLLS问题进行求解的可行性和有效性。(3)针对无资源约束MLLS问题,为避免基本遗传算法(Genetic Algorithm, GA)因过早收敛造成搜索效率低的问题,将排斥算子(Repulsion Operator, RO)概念引入GA中,提出带排斥算子的遗传算法(Genetic Algorithm integrated with RO, RGA)。采用RGA与GA对MLLS问题进行求解比较,结果表明RGA的运行效果优于GA。(4)分散搜索(Scatter Search, SS)算法是一种亚启发式算法,其应用范围已涉及优化领域中的许多NP难问题。本文提出结合变异算子的混合SS (Hybrid Scatter Search,HSS)算法对无资源约束MLLS问题进行了求解。计算实验表明HSS算法能够有效地求解MLLS问题,其求解结果明显优于GA的求解结果。(5)对上述三类算法采用英文文献中的benchmark算例进行求解性能比较分析。通过96个小规模问题,3个中规模问题和1个大规模问题的比较结果来看,SS算法在求解小规模和中规模问题时性能优于HPSO算法和RGA算法,在求解大规模问题时HPSO算法的性能更好。(6)将目前约束处理时常用的罚函数法和能力调整法与元算法相结合,提出了求解单级多产品多资源约束生产批量计划问题的混合元算法。采用3组算法执行策略,并对每组执行策略的具体实现过程以流程图的方式进行了描述。通过文献中的实例对3种执行策略进行了测试和比较,验证了算法的可行性和适用性。(7)针对多级多资源有资源约束的MLLS问题,提出了一种基于SS算法与能力调整方法相结合的方法(Scatter Search integrated with Capacity Adjustment Methods, CAM-SS),阐明了该方法的具体实现过程。在CAM-SS方法中,首先按无资源约束问题采用SS算法对问题进行求解；之后采用能力调整方法按“先顺序—后逆序”的方式逐个时段处理资源约束条件。通过对计算实例进行计算和结果比较分析,表明该算法在寻优能力、求解速度和稳定性方面明显优于文献中的GA算法。更多还原

【Abstract】 Material Requirements Planning (MRP) is not only the basis of Manufacturing Resource Planning/Eenterprise Resource Planning (MRPII/ERP), but also the basis of supply chain management. Among the most common decisions in manufacturing and distribution companies are probably those regarding MRP. However, that firms are daily confronted with these decisions does not mean they are easy to handle. MRP is a method for coordinating replenishment decisions for manufactured items, i.e. end-items made of sub-assemblies and component parts. MRP ensures that the right amounts of components are planned at the various levels of manufacturing and at the right time so that demand for finished goods can be met. As making the right decisions in lot-sizing will directly affects the system performance and its productivity, which is important for a manufacturing firm’s ability to remain competitive in the market, the multilevel lot-sizing problem is a key problem in MRP. Since MRP can only provides feasible solutions to the multilevel lot-sizing (MLLS) problem, the problem of finding a high quality solution, i.e. a sequence of replenishment quantities having the lowest possible cost, comes. The MLLS problem turns out to be a difficult combinatorial problem, especially when real-size set-ups (involving several hundreds of components) are considered. Much of the early work on the MLLS problem has focused on optimizing algorithms tailored for specific variants. However, with the increase of the problem size, the amount of calculation of these algorithms (not to mention their complexity) required for exact solution increases dramatically. This situation motivated the development of numerous solving methods to achieve a satisfactory banlance between computational demands and cost effectiveness.The MLLS problem is a combinatorial optimization problem which can be classified into different categories according to the capacity structures e.g. unconstrained, constrained single resource and constrained multiple resources; the product structures e.g. single level system. serial, assembly, and general systems; the demand models e.g. static demand, dynamic demand, stochastic demand and fuzzy demand; and et al.As the origin of the MLLS problem can date back to 1950s, so far, the research on the models of the MLLS problem has been very mature. The potential research direction focuses on the development of effective and efficient solving tools. In this paper, the meta-heuristic algorithms for solving MLLS problem with dynamic demands are designed. The major work of this paper falls on seven aspects as follows:(1) In this paper, a summary of the related researches on the lot-sizing problem is presented. First, the survey and the background of the MLLS problem are introduced. Second, models of the MLLS problem with different product structures are described in detail. Then, those correlative meta-heuristic algorithms, which can be utilized to solve the MLLS problem, are introduced.(2) PSO algorithms for solving the MLLS problem are proposed. The classical PSO algorithm is a powerful method to find the minimums of numerical functions on a continuous definition domain. It has been a very important optimization tool in many research fields. By embedding the characteristics of formulation of the MLLS problem, the velocity and position in the classical PSO algorithm are redefined. Also the formulas and operators of the classical PSO algorithm are redefined. Based on the above mentioned work, the PSO algorithm is furtherly extended into two versions. They are PSO algorithm with flexible inertial weight and anti-predatory PSO algorithm. Experiments showed the feasibility and credibility of these algorithms.(3) To avoid the decrease in search efficiency caused by pre-maturity, the repulsion operator was integrated into GA (RGA) to solve unconstrained MLLS problem. Simulation tests showed that RGA is obviously superior to GA and that RGA is an effective method to solve MLLS problem.(4) Scatter search (SS) algorithm is one of meta-heuristics. Currently, SS algorithm has been widely used to solve many NP-hard problems in optimization research fields. In this paper, we extended the application scope of SS algorithm and adopted a SS algorithm integrated with mutation operator (HSS) to solve the unconstrained MLLS problem. Experimental results showed that HSS algorithm is an effective tool for solving the unconstrained MLLS problem and that the results of HSS are obviously superior to those of GA.(5) For the above-mentioned three kinds of algorithms, instances of different size from literature are conducted to test the performance of three algorithms. Through 96 small-sized instances,3 medium-sized instances and 1 large-sized instance, these three algorithms are compared. The results of SS algorithm are better than those of HPSO algorithm and RGA for small-sized instances and medium-sized instances. While for large-sized problems, the results of HPSO algorithm are better.(6) In this paper, the problem-based memetic algorithms (MAs) are proposed to solve lot-sizing problems with single level, multiple items and multiple resources. Three executive procedures are constructed by the combination of MA and two commonly used constraints handling methods—punishment method and capacity adjustment method. The procedures of MAs were described in detail in the form of flowchart. Through instances in the literature, MAs were tested and compared. Simulation results showed the feasibility and adaptability of MAs.(7) To solve the constrained multilevel lot-sizing (MLLS) problem with multiple resources, a scatter search (SS) approach integrated with capacity adjusting methods was proposed and its implementation was illustrated in detail. During the execution of this approach, the problem is seen as an unconstrained one and is solved by SS approach firstly; then the result is revised into a feasible one by the capacity adjusting methods. Through the result comparison and the computation on an instance in the literature, the proposed algorithm has demonstrated its higher efficiency, faster convergence speed and better stability than GA mentioned in that literature.更多还原