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

The multi-level lot-sizing (MLLS) problem in material requirements planning (MRP) systems belongs to those problems that industry manufacturers daily face in organizing their overall production plans. However, this combinatorial optimization problem can be solved optimally in a reasonable CPU only when very small instances are considered. This legitimates the search for heuristic techniques that achieve a satisfactory balance between computational demands and cost effectiveness. In this paper, we propose a solution method that exploits the virtues and relative simplicity of genetic algorithms to address combinatorial problems. The MLLS problem that is examined here is the most general version in which the possibility of time-varying costs is allowed. We develop a binary encoding genetic algorithm and design five specific genetic operators to ensure that exploration takes place within the set of feasible solutions. An experimental framework is set up to test the efficiency of the proposed method, which turns out to rate high both in terms of cost effectiveness and execution speed.

Material requirements planning (MRP) is an old field of study within business, but it still plays an important part in coordinating replenishment decisions for complex finished goods. There are actually reasons to believe that the rise in consumers’ demands and expectations, and the subsequent increase in product complexity will make the need for production coordinating devices even more accurate. However, we are not only in an era of rising product complexity but also in an era of fierce competition which definitely calls for adequate cost-saving tools. For this certainly MRP is not enough, as its basic philosophy is only to ensure that the right number of components is planned at the right time to meet the demand for end items. MRP therefore only provides a feasible solution to the multi-level production inventory problem, whereas ideally one would aim at a sequence of replenishment quantities through time at the various levels of manufacturing that keeps the total relevant cost as low as possible while satisfying the demand for end items. Therefore, determining a proper lot-sizing policy definitely is a key dimension of inventory control, as placing proper batches can allow for significant reductions in inventory-related costs. Optimal solution algorithms exist for this problem [1], but only very small instances can be solved in reasonable computation time for the problem is NP-hard, not mentioning the mathematical complexity of the technique that might deter many potential users. Several approaches to solve variants of the MLLS problem have been developed, with further assumptions made on the product and/or cost structure (see [2], [3], [4] and [5]), but execution times remain desperately high. Last, it should also be added that even when the time constraint is made as slack as possible, branch-and-bound algorithms available from standard software packages sometimes fail in finding optimal solutions. Hence heuristic techniques that offer a reasonable trade-off between optimality and computational feasibility are highly advisable. One alternative, which is often implemented in practice, consists in applying single-level decision rules – just like the economic order quantity – to each level of the product structure (see [6] and [7]). Though simplicity surely obtains, neglecting the fact that placing a lot for an item somewhere in the product structure often triggers lots for the subcomponents of this item has dramatic consequences in terms of cost effectiveness. Of particular interest are the approaches in which the multi-level nature of the problem is explicitly taken into account. Blackburn and Millen [8] suggested several cost modifications to account for interdependencies among levels of the product structure. Coleman and McKnew [9] developed a four-pass procedure based on the incremental part period algorithm (IPPA). The procedure embeds an original look-down routine used to compare at each level the net benefit resulting from the lumping of each period's requirement, until the bottom of the product structure is reached. Contrary to both previous approaches, the method developed by Bookbinder and Koch [10] is not only designed to address pure assembly product structures but also general structures, a feature being extremely common in real settings. Dellaert and Jeunet [11] resort to randomization as a means of accounting for interdependencies among stages and achieve fairly good results compared to the previous techniques. However, although these approaches usually outperform sequential methods, they are unable to guarantee an optimal solution. In this paper, we develop a hybrid genetic algorithm (GA) to solve the MLLS problem with no capacity constraints and no restrictive assumption on the product structure. Our primary incentive for this study is to find a solution method which is relatively moderate in CPU-time and intuitively appealing to potential users for a problem field of which Segerstedt [12] says ‘MRP and other methods without clear capacity constraints will no doubt continue to be used in practical installations for decades to come’. We consider the most general statement of the problem in which costs may vary from one time period to the next. Though the possibility of allowing time-varying costs could be considered a striking assumption, it should be recalled that the cost of carrying items in inventory includes the expenses incurred in running a warehouse, the costs associated with special storage requirements, deterioration, obsolescence and taxes, and primarily the opportunity cost of the money invested which is very likely to fluctuate as a result of changes in investment opportunities. Similarly, the set-up cost attached to replenishment decisions embeds learning effects (getting used to a new set-up, procedures and material has a cost in terms of scrap costs) and evolves in response to changes in the work force, especially when it is subject to frequent turnover. Our strategy here has been to design specific genetic operators that constrain search to the set of feasible solutions rather than letting the algorithm explore any possibility and relying on sophisticated penalty schemes. To increase search-efficiency, we have further reduced the set of solutions to the MLLS problem by defining adequate bounds on the ordering periods. We first tested our technique against optimality, and then moved to larger problems for which only heuristic methods can be employed. When small instances are considered, the GA almost instantaneously (1 second on average) provides solution of very high quality. Larger instances confirm the performance of the GA, as it easily beats the sequential techniques we incorporated for the sake of comparison while keeping the computational demand extremely reasonable. The paper is organized as follows. Section 2 is dedicated to the presentation and mathematical formulation of the MLLS problem. Section 3 gives the building blocks of the genetic algorithm: encoding, feasibility constraints, genetic operators and principles of evolution. Section 4 presents the experimental framework and the parameter settings. Numerical results are discussed in Section 5 and in Section 6 conclusions and practical implications are derived.

Though the world of manufacturing is experiencing ongoing change both in terms of consumer needs and the organization of planning and control systems, a number of issues did not fade out. The necessity of carefully selecting adequate inventory control policies certainly is one of these issues. Solving the uncapacitated MLLS problem is left a daily concern for the vast majority of companies engaged in manufacturing production. But the computational requirements imposed by optimizing routines tend to preclude their implementation in realistic size settings. Actually, despite the fact that the MLLS problem is encountered very often in practical installations, most solution methods are faced with severe difficulties in case the problem size grows. One problem in selecting a lot-sizing procedure is that substantial reductions in inventory-related costs can generally be achieved only by using increasingly complex procedures. Optimal models not only demand mathematical prerequisite but also prove unable to solve problems pertaining to complex product structures. For time-varying cost parameters, there is even a lack of simple heuristic rules. By contrast, the relative simplicity of the heuristic offered in this work, together with its cost-efficiency, makes it an appealing tool to industrials, as documented by our simulation results. We designed specific genetic operators and purposefully constrained search to the set of feasible solutions. The first experimental test phase appraised the effectiveness of the GA in reference to the solutions provided by GAMS. In most cases the best performance was achieved by View the MathML source. Not only did the GA prove to be a very good cost-saving device, but it also maintained a computational requirement much less stringent than that needed by GAMS. For larger problems, the GA again showed its ability to improve on initial solutions within reasonable time frames. From a practical perspective, the heuristic offered in this work is significantly easier to understand and implement than optimal mathematical methods. It offers a very satisfactory trade-off between algorithmic complexity and optimality, and as such we believe it can be a powerful near-optimal method for actual settings as well as a useful benchmark to evaluate future heuristic methods.