Study On Algorithms For Lot-sizing Problems In Discrete Manufacturing Enterprises

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.