یک روش گداختگی آرام سازی شبیه سازی شده لاگرانژی یکپارچه برای مسئله تعیین اندازه دسته تولید توانا شده ی چند سطحی چند موردی

This study proposes a heuristic approach for the solution of the dynamic multi-level multi-item capacitated lot sizing problem (MLCLSP) with general product structures. The difficulty in solving MLCLSP is to provide capacity-feasible lot-sizes while maintaining the non-negativity of the inventories belonging to the items in the lower levels of the product structures. The proposed technique aims to resolve this issue by combining the capability of the Lagrangean relaxation to decompose the hard-to-solve problems into smaller subproblems and the intensive search capability of the simulated annealing. As the first attempt, two Lagrangean relaxation schemes are designed and different versions of simulated annealing are incorporated into relaxation designs as the Lagrangean heuristic. Then in order to improve the performance of the heuristic, a Phase-1 procedure is developed as a recursive algorithm to restore capacity feasibility. It is observed that the best results are obtained by executing first Phase-1 procedure and then simulated annealing approach with only improving moves in each Lagrangean cycle. The performance of these approaches is compared by using the benchmark problems available in literature.

This paper addresses the multi-level multi-item capacitated lot sizing problem (MLCLSP) which arises very commonly in multi-stage manufacturing systems. The main issue is to determine the optimal lot-sizes of all items appearing in different levels of the product structure where various resources are needed and shared by multiple items. In fact the model developed in this research includes setup times and setup costs with a general product structure. A lot of research has been directed towards solving lot sizing problems with different modeling features. The single stage capacitated lot sizing problem is shown to be NP-hard in [1], and in case of setup times even the problem of finding a feasible solution becomes an NP-complete problem as shown in [2]. Naturally it becomes even harder to solve the MLCLSP with setup times. In early studies addressing the solution of the MLCLSP, certain modeling features have been excluded in order to simplify the solution procedure. Billington et al. [3] considers general product structures and a single capacity-constrained resource with setup times, and Billington et al. [4] assumes a linear product structure and uniform processing times without setup times. Maes and Van Wassenhove [5] and [6] develop heuristics for the linear product structure case where capacity sharing by multiple levels is not permitted. Kuik et al. [7] also assume a linear product structure for which only a single capacitated stage is assumed to exist among multiple stages without setup times. Tempelmeier and Helber [8] develop a heuristic procedure for the general product structure case where the capacity of multiple resources can be shared by items appearing in different levels of the product structure whereas Tempelmeier and Derstroff [9] apply Lagrangean relaxation, Franca et al. [10] develop a constructive heuristic, and Segerstedt [11] uses dynamic programming for the general product structure with setup times. This study aims at integrating Lagrangean relaxation and global search procedures in solving the MLCLSP. Lagrangean relaxation is employed to solve the single stage capacitated lot sizing problem in [12], [13], [14], [15] and [16]. Furthermore, Billington [17] and Tempelmeier and Derstroff [9] use Lagrangean relaxation in the solution of the MLCLSP. Lagrangean relaxation possesses the capability to decompose a difficult problem into a number of smaller problems while the global search approaches are capable to improve both feasibility and optimality of a given solution by extensive search. Thus the global search concepts are used in the design of the Lagrangean heuristic and implemented in the relaxation in order to generate a feasible solution with the best objective function value starting from the solution obtained in each sub-gradient optimization iteration. Simulated annealing as discussed in [18] and [7] is selected as the search methodology to be implemented in this context. Two different relaxation schemes are developed in this study: The hierarchical relaxation is obtained by relaxing only the capacity constraints while the second one called the non-restricted relaxation is developed by relaxing both inventory and capacity constraints. Similarly different designs for the Lagrangean heuristic are developed and compared. First a simulated annealing procedure which accepts the non-improving moves with certain probabilities are designed. Then in the design of the second procedure, the acceptance of non-improving moves is prohibited in the search, which is not restricted to the neighborhood of a given solution, but continues exploding the feasible region intensively. This approach is called simulated annealing with only improving moves. Then in order to enhance the solution of the Lagrangean heuristic, another procedure is developed to attain capacity feasibility in case of hierarchical relaxation before the simulated annealing procedures. This is called a Phase-1 procedure since it acts as an initial phase of the Lagrangean heuristic. Different combination of relaxation schemes and search procedures are tested by using the problems given in [9], and the results indicate that the hierarchical Lagrangean relaxation with Phase-1 and simulated annealing with only improving moves outperforms the other designs. The paper is organized as follows: A generic MLCLSP formulation is provided in Section 2. The different Lagrangean relaxation schemes are described in Section 3 while the details of simulated annealing procedures and the recursive heuristic as the Lagrangean heuristic are provided in 4 and 5, respectively. Computational results are given in Section 6, and Section 7 states the concluding remarks.

This study develops a heuristic approach for solving the MLCLSP which is very frequently encountered in real life and which is still of great interest to the operations researchers. The advancements in the area of metaheuristics has mainly motivated this study which aims to integrate simulated annealing concepts with the classical Lagrangean relaxation methodology. In fact this research is one of the first attempts integrating these two well-known approaches. Different procedures are designed and tested upon the benchmark problems available in literature, and the results are compared with the Lagrangean relaxation procedure proposed in [9]. The preliminary results indicate that the solutions obtained in this study are satisfactory with respect to the deviations from the known optimal solutions and the computational times. Hence the integration of Lagrangean relaxation schemes with meta-heuristics prove to be mutually beneficial for both approaches.