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

In this paper, genetic algorithms are applied to the deterministic time-varying lot sizing problem with batch ordering and backorders. Batch ordering requires orders that are integer multiples of a fixed quantity that is larger than one. The developed genetic algorithm (GA) utilizes a new ‘012’ coding scheme that is designed specifically for the batch ordering policy. The performance of the developed GA is compared to that of a modified Silver-Meal (MSM) heuristic based on the frequency of obtaining the optimum solution and the average percentage deviation from the optimum solution. In addition, the effect of five factors on the performance of the GA and the MSM is investigated in a fractional factorial experiment. Results indicate that the GA outperforms the MSM in both responses, with a more robust performance. Significant factors and interactions are identified and the best conditions for applying each approach are pointed out.

This paper addresses the deterministic time-varying batch ordering lot sizing problem with backorders. The objective is to determine the optimum ordering plan to satisfy a set of known demands over a specific planning horizon. The optimum ordering plan is the one that minimizes the total cost. Cost elements include the ordering cost (P) charged every time an order is made regardless of the quantity, the holding cost (h) per piece per period (charged on any quantity left at the end of the period), and the backorder cost (g) charged as a shortage penalty per piece per period. In the case addressed in this paper, it is assumed that any order must be an integer multiple of a fixed quantity (Q,Q > 1). Other assumptions of the problem include: 1. the replenishment quantity is unconstrained, 2. cost factors are time independent, 3. replenishment is instantaneous, 4. backorders are only allowed to make up for quantity discrepancies that result from batch ordering, and 5. an order must be placed in the first period. As an example, assume that the demand for a planning horizon of six periods is 10, 7, 6, 9, 11, and 5 for periods one through six, respectively, and that P = $30, h = $2, g = $4, and Q = 6. This demand may be covered by orders of 24, 18, and 6 in periods, 1, 4, and 6, respectively. The total cost of such a plan is $158. A dynamic programming algorithm to obtain the optimum solution to a simpler version of this problem (assuming a variable order quantity with no backorders) was developed by Wagner and Whitin (1958). Several extensions of the original Wagner–Whitin (WW) algorithm were developed over time (Elsayed & Boucher, 1993). Of relevance to this paper are the extensions by Vander Eecken, 1968, Elmaghraby and Bawle, 1972, Webster, 1989 and Li et al., 2004. Vander Eecken (1968) extended the WW algorithm to the case where orders must be integer multiples of a fixed quantity (Q > 1), with the restriction of no backorders. Elmaghraby and Bawle (1972) extended Vander Eecken’s work to the case where backorders are allowed, but with the restriction that the ordering cost is constant over time. Webster (1989) developed a backorder version of the WW algorithm using dynamic programming. Several authors provided extensions to Elmaghraby and Bawle’s work ( Bitran & Matsuo, 1986), but the most general extension was developed by Li et al. (2004) to the case where all cost elements are time varying with allowance for backordering. Although the WW algorithm and its extensions provide the optimum solution for various versions of the lot sizing problem, they are not widely used. Instead, practitioners prefer other algorithms that are simpler, even though they may generate suboptimal solutions for the following reasons: 1. Exact algorithms are often difficult to understand by practitioners due to their complexity (Silver & Peterson, 1985). 2. Heuristics are easily tailored for various extensions of the lot sizing problem, for which no optimization algorithm has been developed yet (Jans & Degraeve, 2004). 3. In a rolling horizon situation, an optimization algorithm becomes a heuristic too, and is often surpassed by simple heuristics (Stadtler, 2000). One of the most commonly used suboptimal algorithms is the Silver-Meal (Silver & Peterson, 1985). The original Silver-Meal (SM) algorithm finds the number of periods for which the total inventory costs per period is minimized and then orders the exact quantity to cover the demand for those periods. In this paper the SM is modified (MSM) so that whenever the total demand for a group of periods is not an integer multiple of the fixed quantity (Q), the closest two integer multiples are tried out. In the previous example, when testing the cost of an order to cover the first three periods that have a total demand of 23, the two quantities of 18 and 24 are considered. The MSM solution for the example given above is to order 18 and 30 in periods 1 and 4, respectively, for a total cost of $140. This paper investigates the applicability of genetic algorithms (GAs) to the targeted problem and compares its performance to that of the MSM. The research is motivated by the fact that GAs have been successfully applied to several production planning problems including lot sizing. GAs have several desirable features including: generality, ease of modification and parallelism (Reeves, 1997). Aytug, Khouja, and Vergara (2003) attribute the popularity of GAs to several factors. First, GAs only require a computable objective function with no requirements of linearity, convexity, or differentiability. GAs are also easy to implement as they require no bookkeeping mechanism or theoretical bounds. Furthermore, empirical evidence shows that GAs are quite successful on computationally intractable problems, mostly with discrete solution spaces, which is usually the case with problems addressed using dynamic programming (Papadimitriou & Steiglitz, 1998). GAs generally provide good solutions to large problems in a reasonable time (Aytug et al., 2003). Several authors have applied GAs to various versions of the lot sizing problem. As an example, Ozdamar and Birbil (1998) utilized GA, simulated annealing (SA), and tabu search to solve the capacitated lot sizing problem on parallel machines. Hung and Chien (2000) also utilized the three approaches (GA, SA, and tabu search) to solve the multi-class multi-level capacitated lot sizing problem. Khouja, Michalewicz, and Wilmot (1998) investigated the use of GAs to solve the economic lot size scheduling problem using the basic period approach. Prasad and Krishnaiah Chetty (2001) applied GAs to multilevel lot sizing and observed that under a rolling horizon environment, the performance of GAs is superior to the popular heuristics. Dellaert and Jeunet (2000) developed a hybrid GA for solving large unconstrained multilevel lot sizing problems. Their approach utilizes GAs to improve initial solutions generated from the part period algorithm, period order method, and the Wagner-Within approach. Also, Dellaert, Jeunet, and Jonard (2000) proposed a GA to solve the general multi-level lot sizing problem with time-varying costs. Staggemeier, Clark, Aickelin, and Smith (2002) presented a hybrid GA to solve a lot sizing and scheduling problem by minimizing inventory and backlog costs of multiple products on parallel machines with sequence-dependent set-up times. Basnet and Leung (2002) presented a multi-period inventory lot sizing scenario, where there are multiple products and multiple suppliers. Sarker and Newton (2002) develop GA code with three different penalty functions to determine optimal batch sizes for products and the purchasing policy of associated raw materials. GA results were compared to optimal solutions, and the GA with a static penalty function obtained the global optimum 100% of the time. Moon, Silver, and Choi (2002) developed a hybrid genetic algorithm to address the lot scheduling problem with time-varying lot sizes. A numerical experiment showed that the hybrid genetic algorithm outperformed Dobson’s heuristic for the problems considered. Dimopoulos and Zalzala (2000) and Aytug et al. (2003) provide a general survey on the use of GAs for manufacturing and operations management optimization. Dellaert and Jeunet (2003) provide an overview of various heuristics and propose a new heuristic for the multi-level lot sizing problem. Jans and Degraeve (2004) provide a wider survey of meta-heuristics applications in dynamic lot sizing. In all cited applications of GAs to the lot sizing problem, the quantities under consideration were variable. However, Shittu (2003) used GAs to address the lot sizing problem with batch sizing and compared their performance to that of the MSM. Comparisons were based on the best resulting solution. Shittu used a ‘01’ coding for the GAs where a ‘0’ indicates no order in the corresponding period and a ‘1’ indicates an order in the corresponding period for its demand and the demand of all subsequent periods with a ‘0’ code. Order quantities on the final GA solution were rounded to the nearest multiple of Q randomly in a post processing algorithm. This coding imposes a restriction that may have led to the poor performance that Shittu (2003) reported (a 4.5% average deviation from the best solution). Shittu’s results may also contain an error as the reported performance of the Silver-Meal heuristic (8.1% average deviation from the best solution) is out of sync with established results in the literature. This paper investigates the performance of GAs in the batch ordering case, with the assumptions stated at the beginning of this section, using a ‘012’ coding that will be explained in Section 2. The performance of the GAs is compared to that of the MSM. A View the MathML source2V5-1 fractional factorial experiment is used to compare the performance of the two approaches and identify the significant factors that affect the frequency of obtaining the optimum solution and the average percentage deviation from the optimum solution. As the experiment implies, the effects of five factors and some of their interactions on the performance of the GA and the MSM are investigated. In evaluating the performance of the GAs, optimum solutions are chosen as obvious benchmarks. Comparisons against the MSM provide a good indication of the GAs’ performance. The MSM was chosen because it is one of the most commonly used methods with reasonable accuracy. The choice of the MSM is also justified by the simplicity/accuracy scale comparing various approaches to the lot-sizing problem developed by Zhiwei, Heady, and Lee (1994). In the reminder of this paper, Section 2 introduces the research approach and describes the development of the GA. Section 3 describes the experiment used for performance evaluation. Section 4 discusses the research results. Finally, Section 5 presents the research conclusions and points out directions for future research.

This paper investigated the applicability of GAs to the dynamic lot sizing problem with batch ordering and backorders. A special GA was developed with a new ‘012’ coding approach that explicitly models the batch ordering decisions. The performance of the GA was compared to that of a modified version of the Silver-Meal heuristic. Comparisons were based on the average percentage deviations from the optimum cost and the frequency of obtaining the optimum cost. The GA had an impressive performance with an average deviation of about 0.15% from the optimum over 3200 instances. The deviation was never larger than 3.7% in any of the 3200 instances. On the other hand, the MSM had an average deviation of about 1.5% from the optimum, with deviations as large as 19.3%. Within the investigated ranges, Factors A (demand pattern) and E (planning horizon) have the most influential effects on the responses. Their effects on dSM and nSM are more pronounced. Factor C (the ratio of the ordering cost to the carrying cost) also has a significant effect on the MSM responses. Factors B (batch size) and D (the ratio of the carrying cost to the backorder cost) were involved through interactions in affecting some responses. The GA demonstrated a more robust performance than the MSM as it was affected by fewer factors and interactions. In general, the MSM performs at its best when the ratio of the ordering cost to the carrying cost is small. On the other hand, the GA performs at its best when the planning horizon is short (small solution space). This may indicate that a better GA performance may be obtained by using an adaptive approach that increases the number of objective function evaluations as the solution space gets larger. Many assumptions were imposed in this paper to facilitate obtaining the optimum solution to evaluate the GA’s performance. The excellent performance of the GA in the evaluated instances may now motivate future research to investigate the performance of the GA on other batch ordering problems for which the optimum solution does not exist or is hard to obtain. Future plans are to extend the developed GA to the multi-level and the rolling horizon cases.