الگوریتم ژنتیک اکتشافی برای مشکلات عمومی تعیین اندازه دسته تولید ایجاد شده

The lot-sizing problems address the issue of determining the production lot-sizes of various items appearing in consecutive production stages over a given finite planning horizon. In general capacitated lot-sizing problems, the product structure can be a general acyclic network, the capacity constraints can be very sophisticated, and all the known parameters can be time-varying. This paper proposes heuristic genetic algorithms for these problems by designing a domain-specific encoding scheme for the lot-sizes and by providing a heuristic shifting procedure as the decoding schedule. The main contribution of these genetic algorithms is the presentation technique that encodes only the binary variables for the setup patterns but derives other decision variables by making use of the problem-specific knowledge. Some results from the computational experiments are also given.

The widespread and popular use of material requirements planning (MRP) systems in industry h~ resulted in increased interest in the topic of decision making in capacitated multistage manufacturing systems. However, the lot-sizing procedures used by currently awfilable MRP systems are quite limited in their ability to coordinate production plans of various stages of the manufacturing processes and various capacity constraints. As firms have incorporated MRP concepts into their production planning and distribution systems, the capacitated multistage lot-sizing decision problem has become a problem of prime importance. The lot-sizing problem addresses tile issue of determining the production lot-sizes of various items appearing in consecutive production stages over a given finite planning horizon. The objective of the problem is to reduce the total manufacturing cost (including setup cost, inventory holding cost, overtiming cost, etc.) while trying to satisfy the customers' requirements with the limited capacity. This kind of problem can be classified into different categories according to the product structures (e.g., single level system, serial, assembly, and general systems) and the capacity structures (e.g., uncapacitated, capacitated single resource, and capacitated multiple resources). Many researchers have studied the lot-sizing problems and designed a lot of optimal or heuristic lot-sizing procedures (e.g., references [1 9] are some excellent reviewing papers on lot-sizing problems). Table 1 gives a brief review of some important or reviewing literatures for the different categories of the capacitated lot-sizing problems. Because the problems are NP-hard and even the feasibility problems with setup times are also NP-hard [3], most of the lot-sizing procedures and algorithms use heuristic techniques to solve the problems. However, the heuristic lot-sizing techniques for capacitated production systems usually concentrate on optimizing the production operations stage by stage, and/or only consider some simple product structures and/or simple capacity constraints. For example, the capacitated lot-sizing problems for general product structures and multiple resources are seldom considered. This is obviously an obstacle to the application of these lot-sizing techniques in real productioii planning and scheduling environments. In the last decade, the genetic algorithm (GA), which is a search technique based on the mechanics of natural selection and natural genetics, is recognized as a powerful and widely applicable optimization method, especially for global optimization problems and NP-hard problems [29-31]. Recently, a lot of researchers studied the applications of GA for solving the lot-sizing problems with unlimited capacity [32-34] and with capacity constraints [35-42}. Numerical results obtained using these methods show that GA (probably combined with other meta-heuristics) is an effective approach to deal with the lot-sizing problems. Before using GA to solve an optimization problem, there are two important points which must be addressed clearly: the first is the encoding (representation) scheme for the decision variables of the optimization problem, and the second is the evaluation scheme for the specific individual (chromosome) of the problem. These two schemes are interrelated and their improper combination can make GA unable to deal with the optimization problems efficiently, especially for the optimization problems with nontrivial constraints as in the general capacitated lot-sizing problems. For the capacitated lot-sizing problems, constraints that cannot be violated can be implemented by the penalty method and the decoder method. The penalty method imposes penalties on individuals that violate the constraints, while the decoder method creates decoders of the representation that avoid creating individuals violating the constraints [31]. Since each optimization problem has its own features, it is also recognized that better performance can be obtained when the problem-specific knowledge is incorporated into the simple GA [31]. In fact, there are some fundamental limitations to genetic algorithms according to the so-called No-Free-Lunch theorem [43-45]. One of the most significant implications of the No-Free-Lunch theorem is that algorithms should be matched to the search problem at hand. "If no domainspecific knowledge is used in selecting an appropriate representation, the algorithm will have no opportmfity to exceed the performance of an enumerative search" [43]. Generally speaking, a better solution can be gained with deeper domain-knowledge being incorporated. However, the domain-knowledge of a specific optimization problem is usually too vast to be considered completely with a single algorithm. Even worse; there may be some domain-knowledge which is difficult to be considered explicitly when designing an evolutionary algorithm. These difficulties reveal that when designing a specific evolutionary algorithm for a specific problem domain, a critical issue is how to exploit the domain-specific knowledge and how to incorporate it into the common logic and the general structure of the evolutionary algorithms. According to this philosophy, a heuristic genetic algorithm for the general capacitated lotsizing problems is presented in this paper. The general capacitated lot-sizing problems can be characterized by the following: (1) each stage in the product network may have several predecessors and several successors; (2) the capacity constraints may include the capacity limitations of nmltiple resources; (3) the capacity of each resource can be adjusted by overtiming; (4) besides resulting in setup cost, the setup of each process can also occupy capacity (i.e., setup times are included but the setup times are assumed to be sequence-independent in this study); (5) independent demands can be given to all the items in the product network; and/or (6) all the parameters in the problem can be time-varying. This kind of capacitated lot-sizing problem is more general than those currently considered by most of the researchers and are more applicable to real production environments. The heuristic genetic algorithm proposed in this paper attempts to incorporate the problem-specific knowledge into the conventional genetic algorithms and heuristically optimizes the problem under all the constraints simultaneously. In order to do that, an encoding (representation) scheme for lot-sizes and a shifting procedure with penalty considerations are designed by making use of the critical properties of the optimal solutions to the problem. This kind of method for dealing with the sophisticated constraints can be considered as a fusion of the penalty method and the decoder method. The remainder of this paper is organized as follows. A mathematical formulation of the general capacitated lot-sizing problems considered in this paper is provided in the next section. Then, in Section 3, we present the heuristic genetic algorithms for the problems with and without overtiming considerations, respectively. Section 4 gives some results of the computational experiments. Some general conclusions and further research directions are summarized in Section 5.