روش جستجو بر اساس محله های متغیر برای مشکلات تعیین اندازه دسته تولید چند سطحی ایجاد نشده

In this paper, an effective approach based on the variable neighborhood search (VNS) algorithm is presented to solve the uncapacitated multilevel lot-sizing (MLLS) problems with component commonality and multiple end-items. A neighborhood structure for the MLLS problem is defined, and two kinds of solution move policies, i.e., move at first improvement (MAFI) and move at best improvement (MABI), are used in the algorithm. A new rule called Setup shifting is developed to conduct a more efficient neighborhood search for the MLLS problems. Computational studies are carried out on two sets of benchmark problems. The experimental results show that the VNS algorithm is capable of solving MLLS problems with good optimality and high computational efficiency as well, outperforming most of the existing algorithms in comparison.

The multilevel lot-sizing (MLLS) problem concerns how to determine the lot sizes for producing/procuring multiple items at different levels, which are quantitative interdependent, so as to minimize the production/procurement setup cost and inventory-holding cost in the whole planning horizon. High quality solution of the MLLS problem can improve efficiently the operation of modern manufacturing and assembly processes. Algorithms providing optimal solutions exist for the problem; however, only small instances can be solved in reasonable time because the problem is NP-hard (Steinberg & Napier, 1980). Several optimization formulations and algorithms have been developed to solve variant MLLS problems. Early dynamic programming formulations used a network representation of the problem with a series structure (Zhangwill, 1968 and Zhangwill, 1969) or an assembly structure (Crowston & Wagner, 1973). Other approaches involve the branch and bound algorithms (Afentakis et al., 1984 and Afentakis and Gavish, 1986) that used a converting approach to change the classical formulation of the general structure into a simple but expanded assembly structure. As the MLLS problem is so common in practice and the solution plays a fundamental role in MRP system, many heuristic approaches have also been developed, consisting first of the sequential application of the single-level lot-sizing models to each component of the product structure (Veral and LaForge, 1985 and Yelle, 1979), and later, of the application of the multilevel lot-sizing models. The multilevel models quantify items interdependencies and thus perform better than the single-level based models (Blackburn and Millen, 1982, Blackburn and Millen, 1985 and Coleman and McKnew, 1991). In recent years, the so-called meta-heuristic algorithms have been developed to solve the MLLS problems, such as the hybrid genetic algorithm (Dellaert and Jeunet, 2000 and Dellaert et al., 2000), the simulated annealing (Raza and Akgunduz, 2008 and Tang, 2004), the particle swarm optimization (Han, Tang, Kaku, & Mu, 2009), the soft optimization approach based on segmentation (Kaku et al., 2010 and Kaku and Xu, 2006), and the ant colony optimization system (Almeder, 2010 and Pitakaso et al., 2007). It have been reported that these algorithms can provide highly cost-efficient solutions within reasonable time. However, most of the meta-heuristic algorithms, such as the hybrid genetic algorithm (HGA), the particle swarm optimization (PSO) and the ant colony optimization (ACO), are highly technology-based and require complicated programming skills, which as a consequence might deter many potential users, not mentioning the mathematical complexity of these algorithms. The soft optimization (SO) approach may be easy for implementation, but is not very effective in finding solutions with good qualities. In this paper, we present a succinct approach based on the variable neighborhood search (VNS) algorithm to efficiently solve the uncapacitated MLLS problem. The VNS algorithm, initiated by Mladenovic and Hansen (1997), is a top-level methodology for solving the combinatorial optimization problems. Since its principle, as to be shown in Section 3 is very simple and easily understood and implemented, the VNS algorithm has been successfully applied to solve various kinds of optimization problems, such as Travel Salesman Problem (Mladenovic & Hansen, 1997), P-media problem (Fathali and Kakhki, 2006 and Hansen and Mladenovic, 1997), and Vehicle Routing Problem (Chen et al., 2010 and Imran et al., 2009). The success of VNS is largely due to its enjoying most of the 11 desirable properties of meta-heuristics generalized by Hansen, Mladenovic, and Pe´rez (2008), such as simplicity, user-friendliness, efficiency, effectiveness, etc. Since the MLLS problem is observed to share common characteristics, e.g., binary decision variables, with the problems solved successfully by VNS based algorithms, it is promising to develop a VNS based algorithm for efficiently solving the MLLS problem. To our best knowledge, this work is a first attempt to solve the classical MLLS problem by using a VNS based algorithm and fortunately, the VNS algorithm does not disappoint us, showing its broad applicability again on combinatorial optimization problem. In practice, various models on the MLLS problems have been developed to match the practical production environments, such as the capacitated lot-sizing model with variable technology by Pratsini (2000). In this paper, we focus on the basic model of the MLLS problem that is featured as uncapacitated, with time-invariant costs, of finite horizon, with no backlogging, and with static requirements on end-products. To examine the performance of our new algorithm, different kinds of product structures are considered in the experimental studies. The experiments are conducted on two sets of benchmark problems — 96 small-size problems and 40 medium-size problems, to compare the new algorithm with the existing hybrid genetic algorithm (HGA) (Dellaert & Jeunet, 2000), the MAX–MIN ant system (MMAS) algorithm (Pitakaso et al., 2007), and the parallel GA algorithm (PGA) (Homberger, 2008). The results show that the VNS algorithm is very competitive since it can on average find better solutions in less computing time. The rest of the paper is organized as follows. Section 2 describes the MLLS problem. Section 3 explains the principle of the VNS algorithm, the definition of the neighborhood structure for the MLLS problem, a rule named setup shifting for considering interdependencies, and the scheme of the new VNS algorithm for MLLS problem. In Section 4, computational experiments are carried out to test the new algorithm against existing algorithms. Finally, in Section 5, we conclude the paper.

This paper studies the variable neighborhood search (VNS) based approach for solving the uncapacitated MLLS problem. The neighborhood structures for the MLLS problem are defined and the mechanism of the VNS algorithm for the MLLS problem is discussed. With the consideration of the items interdependencies in general product structure with component commonality and multiple end-items, a new rule called Setup shifting is developed to enhance the searching efficiency. Two sets of benchmark problems — (1) 96 small-size MLLS problems with assembly structures and known optimal solutions, and (2) 40 medium-size MLLS problems with general structures, are tested to examine the developed VNS algorithm. The experiments show that the VNS algorithm enjoys good optimality when tested against the 96 small-size benchmark problems, and high computational efficiency as well when solving the medium-sized problems. Two neighborhood search policies, move at first improvement (MAFI) and move at best improvement (MABI), are compared in the experiments. Since the MAFI can deliver more cost-efficient solutions than the MABI and therefore is recommended for solving the MLLS problems. The new VNS algorithm is further compared with the reproduced hybrid GA over the medium-size MLLS benchmark problems, which shows that the VNS algorithm outperforms the hybrid GA with respect to all kinds of product structures. The new VNS algorithm is also compared with the MMAS algorithm and the PGA algorithm developed in literature on the 96 small-size and 40 medium-size problems, and shows good performances in the comparisons. Moreover, by taking into account the simplicity of the VNS algorithm and the complexities of other meta-heuristic algorithms like HGA, MMAS, PGA and PSO, we deem that the VNS algorithm is among the best meta-heuristic algorithms for the MLLS problem.