تلفیق یک رویکرد بانک اطلاعاتی در مشکل تعیین اندازه دسته تولید چند سطحی در مقیاس بزرگ

Traditionally, optimization for large-scale multi-level lot sizing (MLLS) problems always encountered heavy computational burden. Scholars also indicated that “whatever the optimal method chosen to solve the MLLS problem, standard optimization packages were still faced with computer memory constraints and computational limits that prevented them from solving realistic size cases”. Therefore, the main purpose of this paper is to propose an optimal method to reduce the computer memory while solving the large-scale MLLS problems. The optimal method is designed to implement on a database entirely because the demand for computer memory can be reduced significantly by means of the utilization of database storage. An example is given to illustrate the proposed method and computation capability is tested for the MLLS problems with up to 1000 levels and 12 periods.

In a production-inventory system, practitioners always desire to make a set of production plans (PPs) for minimizing the sum of setup costs and inventory holding costs. By virtue of an optimal set of PPs, practitioners can decide how many quantities have to be produced in which periods at each level. However, this is a classical multi-level lot sizing (MLLS) problem. Till now, the MLLS problems have received considerable attentions in the literature [1], [2] and [3]. The two fundamental optimal methods for the MLLS problem with a serial production structure (each item has at most one direct predecessor and one immediate successor), one was Zangwill’s [4] backward recursive algorithm and the other was introduced by Love [5]. Following that, various production structures were addressed and some optimal methods had also been proposed [1], [6] and [7]. As a general production structure (each item has several direct predecessors and immediate successors) is considered, no optimal method is suitable for the MLLS problems over 50 items and exceeding 24 periods in size [8]. For example, one famous optimal methods, branch-and-bound-based algorithm, proposed by Afentakis and Gavish [1] handled the MLLS problem with up to 40 items and 12 periods for a general production structure and 106 items and 12 periods for a assembly production structure (each item has several direct predecessors but only one immediate successor). Dellaert and Jeunet [8] and [9] also pointed out that “whatever the optimal method chosen to solve the MLLS problem, standard optimization packages were still faced with computer memory constraints and computational limits that prevented them from solving realistic size cases”. However, if the MLLS problem is a large-scale size case, it will be one of the most difficult problems for decision making. Because of the computational burden of optimization [3], [10] and [11], scholars were usually toward creating the heuristic methods [8], [9], [10], [11], [12], [13], [14], [15], [16] and [17]. Simpson and Erenguc [3] found that many heuristic studies often neglected the use of the optimal solution as a benchmark by which to evaluate heuristics. Without an exact benchmark, scholars must evaluate heuristic techniques relative to other heuristic techniques [3]. From this argument, with respect to solving the large-scale MLLS problems, we are motivated to develop an optimal method rather than a heuristic method. Some MLLS heuristic methods [12], [13] and [14] typically adapted the single-level solution methods, i.e. Wagner–Whitin [18] and Silver–Meal [19] procedures. Blackburn and Millen [13] were the pioneers in introducing a heuristic method to solve the MLLS problems by “improving” the single-level solution methods. One significant result of Blackburn and Millen’s [13] study is that “deviation from the optimality by the heuristics is highly correlated with the ‘depth’ of the production structure” namely the more the level, the larger the deviation from the optimality [12] and [13]. That is, even if a serial production structure is taken into account, as it is a large number of levels, how to explore an optimal solution exactly is still a significant issue. In sum, if the MLLS problem was considered as a large-scale size case, the past research papers indicated that (1) using the optimal methods to deal with it would face the computer memory constraints [8] and [9]; and (2) adopting the heuristic methods to handle it will get a large deviation from the optimality [12] and [13]. Therefore, the main purpose of this study is to propose a solution method to reduce the computer memory for exploring an optimal solution (rather than a sub-optimal solution) while solving the large-scale MLLS problems.

With respect to optimization for the large-scale MLLS problems, scholars had pointed out that both “heavy computational burden [3], [10] and [11]” and “computer memory constraints [8] and [9]” were the significant issues. (Obviously, these two issues relate to each other.) Besides, as heuristic methods are adopted to solve the MLLS problems, the more the level, the larger the deviation from the optimality [12] and [13].Therefore, the main contribution of this study is that a solution method is proposed to reduce the computer memory for exploring an optimal solution in MLLS problems with a large number of levels. The major features of the proposed method are that (1) an optimal solution to MLLS problems can be found exactly without the restriction on the number of levels; (2) even if a large-scale size case is considered, it can be conducted by employing an “economic” computer, meaning a computer without superior CPU and RAM; (3) the solution procedures are not complicated to be understood for implementing in practice. Computer memory constraints and computational limits will no longer perplex practitioners even if they attempt to solve the large-scale size cases. For handling the MLLS problems, the introduced method is a threshold of incorporating the utilization of database storage into the solution procedures. During the computational processes, the feasible PPs are generated entirely and encoded as a zero-one version stored into the database. Therefore, whatever the number of items in each level is considered, the stored PPs can be recalled repeatedly and decoded for calculating the total cost of each one, if necessary. In addition, the PPs (at level 1) and PPSs (at level 2 to M) for each particular successive PP are stored as a set of row indices (a set of gg) corresponding to the created Solving-Process data sheet and stored into the database. Even if many items are taken into account at each level, which PP (or PPS) at level mm have a minimal value for a particular successive PP at level m+1m+1 can be found easy by recalling the set of row indices and comparing the indicated values with each other. A further work will be undertaken to extend the proposed method for handling the MLLS problems with a more complex production structure.