A biased random key genetic algorithm approach for inventory-based multi-item lot-sizing problem

Abstract

In this article, we have explored multi-item capacitated lot-sizing problem by addressing the backlogging and associated high penalty costs incurred. At the same time, penalty cost for exceeding the resource capacity has also been taken into account. Penalty cost related to both backlogging and overutilizing capacity has been included in main objective function. The main objective is to achieve such a solution that minimizes the total cost. The ingredients of total cost are the setup cost, production cost, inventory holding cost and aforementioned both the penalty costs. To solve this computationally complex problem, a less explored algorithm “biased random key genetic algorithm” has been applied. To the best of our knowledge, this research presents the first application of biased random key genetic algorithm to a lot-sizing problem. To test the effectiveness of proposed algorithm, extensive computational tests are conducted. The encouraging results show that the proposed algorithm is an efficient tool to tackle such complex problems. A comparative study with other existing heuristics shows the supremacy of proposed algorithm in terms of quality of the solution, number of generation and computational time.

Introduction

In the present era of continuously varying customer requirements and intense competition, manufacturers are striving for delivering quality products at minimal cost and least lead time. In such a scenario, manufacturers need to refine their production strategies by scheduling their operations in an efficient manner. Nowadays, an efficient production plan plays a critical role in the success of any manufacturing company. The main goal of production planning is to fulfill the customer demand at minimal cost while taking the resource and inventory capacity into consideration. In real-life manufacturing environment, the production planning problems are intractable due to various realistic constraints. ¹ Being a critical part of planning and management of manufacturing processes, lot-sizing problem coupled with resource capacity constraint is a key aspect of production planning problem.

It is a decision-making problem of manufacturing the products in different lot sizes with varying degree of demand such that the demand be fulfilled at minimum cost. Single-item lot-sizing is a well-known problem, in which a certain amount of product is produced to satisfy known and deterministic or stochastic demand over a finite planning horizon. Pochet and Wolsey, ² Piperagkas et al. ³ and others have considered only a single-item lot-sizing problem. Computationally speaking, a single-item lot-sizing problem that optimizes the lot size by producing items at minimum cost is quite complex problem. A multi-item capacitated lot-sizing problem (MICLSP) involves both the production planning aspect related to parameters such as production time, shortage cost, setup cost, production cost and holding cost with resource capacity and need for meeting the market demand over multiple time horizon. The MICLSP seeks to devise an efficient production plan that minimizes the sum total of setup, production and holding cost by considering the resource capacity and demand shortage over the complete planning horizon. Therefore, the MICLSP is computationally a challenging lot-sizing problem. Due to its complexity, it attracts a number of researchers to provide an effective production plan.^1,4–8 If the problem size is small, it can be easily modeled and solved using integer programming. However, converging at a near optimal solution becomes difficult if solution space expands exponentially due to an increase in the planning horizon in a number of items in the lot. Due to competitive pressure of achieving a reasonable execution time, the decision maker has to seek for a near optimal solution within a reasonable time.

In the last decade, meta-heuristics were widely used to solve mixed integer programming problem having exponential solution space. Although the global optimum solution is not always guaranteed, the time to search a near optimal solution is quite reasonable in the case of meta-heuristics. ⁹ The main feature of these meta-heuristics is to enable them to solve various lot-sizing problems for which exact methods do not exist. For lot-sizing problems, various meta-heuristics have been applied. Some researchers have introduced simulated annealing approach to address the complex issues related to a lot-sizing problem.^10,11 Researchers have pursued solving lot-sizing problem by using nature-inspired algorithms such as genetic algorithm (GA) and particle swarm optimization (PSO). Recently, few researches have addressed the application of PSO to reveal the complexity of the lot-sizing problem.^3,11 Whereas a lot of researchers have focussed on employing GA to solve the different versions of lot-sizing problem with different objectives and issues.^12–14 Therefore, plenty of research studies have been carried out using GA to solve lot-sizing problem. To evolve new algorithms for faster convergence and better quality solutions, biased random key genetic algorithm (BRKGA), a modified version of GA, has been employed in this study to solve the intricacies of lot-sizing problem.

In this article, the MICLSP is characterized by varying customer demand, different setup times and various cost parameters. The main objective of this study is to minimize the total cost, which is the sum of setup cost, production cost and holding cost. To mimic the real-life situation, a penalty cost is introduced in case of failing to fulfill the demand. Another penalty is incurred in case of insufficient resource capacity to manufacture the required number of products. Total cost is modified to include both the penalty costs. Therefore, this study proposes multidimensional objectives: (1) minimize the total cost, (2) fulfill the customer demand and (3) satisfy the capacity constraints. To solve this nondeterministic polynomial-time (NP)-hard problem, a meta-heuristic BRKGA is applied. To show the effectiveness, BRKGA has been applied on a numerical example of MICLSP taken from the existing research literature. The results have also been compared with that of other existing heuristics to demonstrate its efficacy. From the numerical analysis, it can be concluded that BRKGA can efficiently tackle the lot-sizing problem by providing better results with less number of generations.

The remainder of this article is organized as follows: section “Literature review” presents the related literature review in lot-sizing problem, whereas the description of lot-sizing problem with mathematical modeling is presented in section “Problem description.” Section “Background of BRKGA” describes the background of proposed algorithm and the steps for application in presented model. Section “Numerical analysis” illustrates the numerical analysis along with various complex-natured numerical examples. Finally, in section “Conclusion,” the future scope of the research is discussed.

Literature review

In this section, we present some of the recent research in the area of MICLSP. Gopalakrishnan ¹⁵ developed a capacitated lot-sizing problem (CLSP) modeling variant that differs in terms of modeling of setups. Quadt and Kuhn ¹⁶ have used aggregation and decomposition technique to solve a CLSP that is formulated for bottleneck resources in a multi-stage production system.

A CLSP is computationally complex and is considered as NP-hard problem. Many researchers have proposed a lot of optimal or heuristics lot-sizing procedures to evaluate such complex problems. To show the complexity of lot-sizing problems, Liu et al. ¹⁷ have modeled an algorithm for a lot-sizing problem with bounded inventory, lost sales, nonincreasing production cost function and nondecreasing inventory capacity with respect to the time period. Chu and Chu ¹⁸ have addressed a single-item dynamic lot-sizing problem arising in a refinery for crude oil procurement. They have considered two models. In one model, backlogging is allowed with a backlogging penalty with no possibility of outsourcing. In the other model, all of the customer requirements are satisfied in time (i.e. without backlogging), but outsourcing is possible. Absi and Kedad-Sidhoum ¹ proposed a Lagrangian relaxation of the resource capacity constraints and developed a dynamic programming algorithm to solve MICLSP. Ma et al. ¹⁹ have presented a framework of the knowledge evolution algorithm (KEA) for CLSP. They concluded that KEA has higher search efficiency and better stability than the GA and the annealing penalty hybrid genetic algorithm (APHGA). To fulfill deterministic demand of each period, without exceeding available capacities (leading to expensive backlogging cost), Wu and Shi ²⁰ proposed a new heuristic algorithm for CLSP. Gaafar and Aly ⁹ investigated the applicability of PSO to the dynamic lot-sizing problem with batch ordering. They have carried out a comparative study using both modified Silver–Meal Heuristic and GA. The comparison was based on the relative frequency of obtaining the optimum solution and the percentage deviation from the optimum solution. Wu et al. ²¹ have proposed hybrid nested partitions and mathematical programming (HNP-MP) approach to achieve feasible high-quality solution for MICLSP with setup times.

This article investigates the applicability of BRKGA to the targeted problem and compares its performance with simple GA, ²² APHGA ²³ and KEA. ¹⁹ GA has been successfully applied to several production planning problems including lot-sizing. Xie and Dong ²⁴ have proposed heuristic GA for lot-sizing problem by designing a domain-specific encoding scheme for the lot sizes and by providing a heuristic shifting procedure as the decoding schedule. GA meta-heuristic has been used by Aytug et al. ²⁵ to solve production and operation management problems. GA has been compared to that of a modified Silver–Meal heuristic based on the frequency of obtaining the optimum solution and the average percentage deviation from the optimum solution. ²⁶

In this article, BRKGA is employed for solving the MICLSP. First, random key genetic algorithm (RKGA) was introduced by Bean, ²⁷ and he extended it to tackle a wide class of combinatorial optimization problem. BRKGA was first introduced by Gonçalves and Almeida ²⁸ for sequencing problem. Gonçalves and Resende ²⁹ presented a multi-population BRKGA for the single-container loading problem, where several rectangular boxes of different sizes are loaded into a single rectangular container. This heuristic has been used in their problem to determine maximal space, where each box is placed. The main feature of BRKGA is to select one parent from the elite group for crossover; therefore, it performs better than simple GA.

From the literature review, it can be concluded that MICLSP plays a vital role in production planning. This problem has been explored by various researchers, but still it needs more exploration with real-time constraints and real-world manufacturing system environment. This study explores the MICLSP and provides a new insight into the application of meta-heuristic for this problem.

Problem description

The lot-sizing problem deals with the 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 lot-sizing problem is to minimize the total manufacturing cost (including inventory holding cost, setup cost, back ordering cost and production cost) while trying to satisfy the customer requirements within the constraint of limited resource capacity. CLSP deals with capacity constraints, that is, capacity limitations of multiple resources. The deficiency of resources can be adjusted by overtime production and safety stock. The objective of MICLSP is to find a production plan that minimizes the demand shortages, setup cost, inventory holding and production costs all-over the planning horizon.

In this section, we present the mathematical formulation of the multi-item capacitated lot-sizing model. We have considered a CLSP with time-varying deterministic demand for $l$ products over $T$ periods. Several factors have been taken under consideration such as setup cost, holding and shortage cost, capacity constraints and lost sales revenue. In order to take care of resource capacity constraints and backlogging, two penalty cost functions have been added in the objective function (1). The objective of this study is to reduce the total cost that includes setup cost, production cost and holding cost while trying to satisfy the customer’s requirements with the available resource capacity. In order to obtain near optimal results that are not computationally expensive, BRKGA has been introduced for solving. This article addresses MICLSP by including the following assumptions. These assumptions hold for any size of planning horizon for which the demands of individual periods are known to the manufacturer before the first period of production starts.

1. The demand is variable and deterministic.

2. An order for complete planning horizon must be placed in the first period.

3. Cost parameters are independent of time.

4. Inventory levels at the beginning of the planning horizon and at the end are zero.

5. Lost sales costs are larger than the production cost.

6. There will be no back order at the end of planning horizon.

Mathematical model

Given the external demand for I items over a time horizon of T periods, the objective is to find a solution which minimizes total cost including setup, production, holding and lost sales cost based on the above-mentioned assumptions.

For each period, demand must be satisfied and capacities are supposed not to be exceeded, otherwise expensive lost sales or capacity shortage will result in higher total cost. In this section, the notations are presented first before demonstrating basic formulation of the problem.

Indices and index sets

• $i$  items, $i=1,\dots ,I$

• $I$  number of items

• $j$  resources, $j=1,\dots ,J$

• $J$  number of resources

• t periods, $t=1,\dots ,T$

• $T$  number of periods

Parameters

• $C_{\mathrm{jt}}$  total available capacity of resource j in period t

• $G{D}_{\mathrm{it}}$  gross demand of item i in period t

• $H{C}_{\mathrm{it}}$  inventory holding cost for one unit of item i in period t

• M penalty cost for per unit unavailability of resource capacity

• $P{C}_{\mathrm{it}}$  production cost for one unit item i in period t

• $P{T}_{\mathrm{ij}}$  production time required to produce one unit of item i on resource j

• $S{C}_{\mathrm{it}}$  setup cost for item i in period t

• $S{T}_{\mathrm{ij}}$  setup time for item i on resource j

• ${\delta }_{\mathrm{it}}$  penalty for lost sale for one unit of item i in period t

Variables

• $L_{\mathrm{it}}$  amount of lost sales of item i in period t

• $S_{\mathrm{it}}$  inventory of item i at the end of period t

• $X_{\mathrm{it}}$  binary decision setup variable

• $Y_{\mathrm{it}}$  number of item i produced on period t

The general formulation of MICLSP can be given as follows

$$min(\sum _{i=1}^I\sum _{t=1}^T(P{C}_{\mathrm{it}}*Y_{\mathrm{it}}+S{C}_{\mathrm{it}}*X_{\mathrm{it}}+H{C}_{\mathrm{it}}*S_{\mathrm{it}}))$$

(1)

Considering the penalties for lost sales and exceeding resource capacity, equation (1) can be modified. This modified objective function is shown in equation (2)

$$min\left(\begin{array}{c}\hfill \sum _{i=1}^I\sum _{t=1}^T(P{C}_{\mathrm{it}}*Y_{\mathrm{it}}+S{C}_{\mathrm{it}}*X_{\mathrm{it}}+H{C}_{\mathrm{it}}*S_{\mathrm{it}}+{\delta }_{\mathrm{it}}*L_{\mathrm{it}})+\hfill \\ \multicolumn{1}{c}{M*(\sum _{j=1}^J\sum _{t=1}^{T}max(0,\sum _{i=1}^I(S{T}_{\mathrm{ij}}*X_{\mathrm{it}}+P{T}_{\mathrm{ij}}*Y_{\mathrm{it}})-C_{\mathrm{jt}}))}\end{array}\right)$$

(2)

s.t.

$$\begin{array}{c}\multicolumn{1}{c}{S_{i(t-1)}+Y_{\mathrm{it}}-(G{D}_{\mathrm{it}}-L_{\mathrm{it}})=S_{\mathrm{it}},}\\ i=1,\dots ,I,t=1,\dots ,T\hfill \end{array}$$

(3)

$$\begin{array}{c}\multicolumn{1}{c}{\sum _{i=1}^I(S{T}_{\mathrm{ij}}*X_{\mathrm{it}}+P{T}_{\mathrm{ij}}*Y_{\mathrm{it}})\le C_{\mathrm{jt}},}\\ j=1,\dots ,I,t=1,\dots ,T\hfill \end{array}$$

(4)

$$X_{\mathrm{it}}(Y_{\mathrm{it}})=\{\begin{array}{cc}\hfill 1\hfill & \hfill \text{if}{Y}_{\mathrm{it}}>0\hfill \\ \multicolumn{1}{c}{0}& \hfill \text{if}{Y}_{\mathrm{it}}=0\hfill \end{array},i=1,\dots ,I,t=1,\dots ,T$$

(5)

$$Y_{\mathrm{it}}\ge 0,i=1,\dots ,I,t=1,\dots ,T$$

(6)

$$S_{\mathrm{it}}\ge 0,i=1,\dots ,I,t=1,\dots ,T$$

(7)

$$S_{i0}=S_{\mathrm{iT}}=0,i=1,\dots ,I$$

(8)

The objective function (2) minimizes the total cost induced by production plan, that is, production costs, inventory costs, setup costs, penalty cost due to lost sales and penalty cost due to insufficient resource capacity. Constraint (3) represents the material balance for the inventory ensuring the demand satisfaction of all periods for all items. Constraint (4) enforces the capacity feasibility. Constraint (5) implies that the setup cost analogous to an item must be paid before producing the item. Constraint (6) indicates nonnegative condition. Constraint (7) assures nonoccurrence of backlogging. Constraint (8) guaranties that no initial inventory and final inventory is available.

Background of BRKGA

The proposed algorithm was first introduced by Bean ²⁷ for addressing various optimization problems. He proposed the genetic algorithm with random key and called it as random key genetic algorithms (RKGAs). In this algorithm, the representation of chromosomes is in the form of string, or vector, with random numbers in the interval of 0 and 1. Bean ²⁷ proposed a decoder, which takes the chromosome as an input and sorts the best group of chromosomes that represent better solutions for the next generations. This process enhances the performance of the algorithm. In RKGA, after computing the fitness value of each chromosome, the chromosomes are separated in two different groups: elite and nonelite. In the elite group, the chromosomes with higher fitness value are selected, while others belong to the nonelite group. For instance, if the total number of initial population is S and that of elite group is S_e, then population of the nonelite group will be S−S_e, and the elite group should be less than the nonelite group.

In RKGA, the elitist strategy is used for selection. In this strategy, the elite group or best-fit solutions are copied for the next generation without any changes. Therefore, the good solution cannot be lost during the search of optimal solution. In each generation, some mutant solutions (S_m) are introduced resulting from mutation. Mutant solutions are randomly generated chromosomes and are computed for fitness value by decoder function. From Figure 1, it can be seen that $S_m$ mutant solutions have been generated in population i+ 1 as random key vector. After the partitioning of the elite group and mutants, the rest of the group (S-S_e-S_m) will go for crossover. The generated offspring will again fulfill the total number of solutions (S) for the next generation. Hence, a new generation has the elite solutions, mutants and offsprings. The evolution dynamics of RKGA has been shown in Figure 1.

Figure 1.

Transition from generation i to generation i+1 in a BRKGA.

In RKGA, two parents are selected from the S-S_e-S_m group for crossover, whereas BRKGA proposes a different approach as it selects one parent from the elite group and other from the nonelite group.^28,30,31 Therefore, it improves the quality of the new offspring. By applying the approach for crossover in BRKGA, only one offspring is generated after mating. The procedure of crossover in BRKGA has been illustrated by an example in Figure 2.

Figure 2.

Parameterized uniform crossover mating in BRKGA.

From Figure 2, it can be observed that there are two parent chromosomes: first chromosome (X1) belongs to the elite group and other (X2) belongs to the nonelite group. The crossover probability is 0.7, implying that if the randomly generated number (between 0 and 1) for each gene is less than 0.7, the gene will come from elite parent otherwise from nonelite parent. In the example, only third gene has come from nonelite parent, and only one new offspring is formatted in this approach. After completion of crossover, the fitness values are computed using the decoder, and all the solutions are again separated in the elite and nonelite groups for the next generation.

The general working mechanism of BRKGA is shown in Figure 3.

Figure 3.

Flowchart of biased random key genetic algorithm.

From Figure 3, it can be illustrated that BRKGA is divided in two parts: problem independent and problem dependent. The generation as well as selection of random keys, introduction of mutants and crossover are included in problem independent part, whereas decoder is included in problem dependent part. The decoder calculates the fitness value of all the solutions on the basis of main objective of the problem, depending on the nature of the problem. Therefore, if the general framework of BRKGA is developed, the user should have the knowledge of chromosome size and working of decoder.

Therefore, BRKGA provides the better solutions as it has the elite group of the solutions in each generation and keeps an eye on the tracking of the good solution, and on the other hand, it also takes one parent from the elite group and the other from the nonelite group for crossover. This crossover is also helpful to improve the quality of newly generated solutions.

The working mechanism of BRKGA for the present problem is defined, and it is given as follows.

BRKGA for MICLSP

Application of BRKGA on the problem depicted in this article has been discussed in detail in this section. The main components of BRKGA that need to be defined for this problem are as follows:

1. Chromosome representation and encoding.

2. Decoder function and decoding of chromosome.

3. Evaluation of chromosome.

4. Generation of new population.

In the mathematical model, we are planning for the production of $I$ items for $T$ periods. Keeping the production plan in mind and the feasibility of decoding decision variables from their encoded value, chromosome has been designed in a manner which will comprise $I*T$ number of genes as depicted in Figure 4.

Figure 4.

Design of a chromosome for MICLSP.

The decision variables in MICLSP are $Y_{\mathrm{it}},L_{\mathrm{it}},S_{\mathrm{it}}$ and $X_{\mathrm{it}}$ among which $X_{\mathrm{it}}$ can take either 0 or 1 value, and others can take any positive variable of real numbers. Thus, we have encoded the chromosomes in such a way that the genes can take binary values, and these values are the solutions of the binary decision setup variable $X_{\mathrm{it}}$ . After encoding, decoders play an important role in BRKGA heuristics since they make linkage between the solutions in the chromosome and the fitness of their corresponding solutions in the solution space of the combinatorial optimization problem. If the lot-sizing setup pattern variables ( $X_{\mathrm{it}}$ ) are known, the production quantity, inventory quantity and lost sales quantity can be computed by equations (9)–(11)

$$Y_{\mathrm{it}}=\{\begin{array}{cc}\hfill 0\hfill & \hfill X_{\mathrm{it}}=0\hfill \\ \multicolumn{1}{c}{\sum _{w=t}^{t_1-1}G{D}_{\mathrm{iw}}}& \hfill X_{\mathrm{it}}=1,t_1=\underset{q=t+1,\dots ,T}{min}\{q|X_{\mathrm{iq}}=1\}\hfill \end{array}$$

(9)

$$S_{\mathrm{it}}=\sum _{n=1}^t{Y}_{\mathrm{in}}-\sum _{n=1}^{t}G{D}_{\mathrm{in}}$$

(10)

$$\begin{array}{c}{L}_{\mathrm{it}}=(S_{\mathrm{it}}+G{D}_{\mathrm{it}})-(Y_{\mathrm{it}}+S_{i(t-1)})\\ \forall i=1,\dots ,I,t=1,\dots ,T\end{array}$$

(11)

Fitness values are evaluated for each chromosome in the population after the decision variables are calculated from aforementioned equations. The fitness values for the chromosome are the values determined by the objective function that is subjected to various constraints. The set of elite and nonelite solutions is formed based on the sorting of fitness in decreasing order. For the generation of next population, roulette wheel selection technique has been used to select an individual from elite and nonelite solutions. For crossover, one parent has been selected from elite solution and another is selected from nonelite solution. For mutation, the solutions are randomly generated. After getting the next population, repeat the entire procedure until termination criteria (maximum number of generation) are met.

Numerical analysis

To show the efficacy of proposed algorithm in MICLSP, a real-world manufacturing lot-sizing problem with numerical data has been taken into account. The numerical example is identical as that of Ma et al. ¹⁹

In this example, five items are manufactured according to their demand in each period. The production cost for each item in each period is different. The inventory cost and setup cost also vary according to the item and time period. The demand is generated for each period of each item. The data of demand, production cost, inventory cost and setup cost for each item in each period with generated demand are shown in Table 1. There are two resources with different capacities in each time period. The setup time and production time for each item have also been provided. The sum of setup time and total production time should be less than the capacity of the resources. The setup time, production time and capacity of the resources are given in Table 2.

Table 1.

The original model parameters.

Items	Periods
	Demand					Production cost					Inventory cost					Setup cost
	1	2	3	4	5	1	2	3	4	5	1	2	3	4	5	1	2	3	4	5
1	12	11	18	16	10	3	3	4	5	5	1	2	1	1	2	20	35	30	35	20
2	13	11	18	10	10	4	4	5	3	3	1	3	1	2	2	16	30	16	23	30
3	12	11	18	16	12	3	3	4	5	5	3	1	3	2	2	19	20	13	20	23
4	12	11	14	13	12	3	3	4	5	5	2	1	1	1	2	24	31	25	24	30
5	12	11	18	13	12	3	3	4	5	5	3	3	1	1	1	19	24	25	27	28

Table 2.

Time factors and capacity.

Resources	Periods
	Setup time					Production time					Capacity
	1	2	3	4	5	1	2	3	4	5	1	2	3	4	5
1	10	23	24	25	26	2	1	5	1	3	666	600	550	350	480
2	9	6	10	28	26	1	2	3	4	2	666	600	550	350	480

For this problem, the basic parameter setting uses a population size S = 100, elite population of size S_e = 15 and mutant random vector population of size S_m =10, and crossover probability has been taken as 0.7. These parameters are identical as that of Gonçalves and Resende. ³² We have also carried out experiments and observed that convergence is taking place in this value only. Penalty cost for per unit lost sales has been taken as 50 cost units, and penalty cost for per unit unavailability of resource has been taken equal to 45 cost units as per our simulated dataset. Above-mentioned parameters have been used in all the examples discussed below. The detailed working procedure of proposed algorithm is given in section “Background of BRKGA.” The main objective of this study is to manufacture different items with minimal total cost to fulfill the demand. The ingredients of total cost are setup cost, production cost, inventory holding cost and penalty cost for lost sales and insufficient resource capacity. The results obtained from BRKGA for MICLSP are presented in Table 3. Table 3 shows the lots of each item to be manufactured in each time horizon. The obtained near optimal value of performance measure, that is, the total cost, is 1700 cost units. The result provides a valuable insight that the manufacturing for anticipated demand is beneficial in cases, where the inventory cost is not very large but the penalty for lost sale is very high. The convergence rate of BRKGA is high, since the solution converges in only six iterations. The converging trend of BRKGA is depicted in Figure 5.

Table 3.

Lot-sizing result of BRKGA.

Items	Periods
	1	2	3	4	5
1	23	0	44	0	0
2	24	0	18	20	0
3	12	29	0	16	12
4	12	50	0	0	0
5	12	11	43	0	0

Figure 5.

Convergence rate of BRKGA.

Comparison of results obtained from various algorithms (addressed in the literature) with BRKGA establishes superiority of BRKGA in terms of convergence rate. The comparative results are shown in Table 4.

Table 4.

A comparison of the result of GA, APHGA, KEA and BRKGA.

Heuristics	GA	APHGA	KEA	BRKGA
Optimal	1761	1709	1700	1700
Iterations	21	10	10	6
Time of CPU (s)	26	14	1	0.6552

GA: genetic algorithm; APHGA: annealing penalty hybrid genetic algorithm; KEA: knowledge evolution algorithm; BRKGA: biased random key genetic algorithm; CPU: central processing unit.

From the results, it is evident that the proposed algorithm provides the results with minimum cost. It takes minimum number of iterations and less computational time in comparison to other algorithms. The total cost obtained from GA is 1761, and APHGA provides the result with 1709 cost units, whereas KEA provides the similar results as BRKGA. The number of iterations for GA is very large, whereas APHGA and KEA compute the near optimal result in the same number of iterations. ¹⁹ There is small difference in the number of iterations for APHGA and KEA with BRKGA, but there is a huge difference in terms of computational time.

The proposed algorithm is also validated using some large-sized MICLSPs. Initially, the previous example has been extended up to 10 time periods only with five items. The dataset for this problem is given in Appendix 1, whereas the penalty will be identical as the previous example. On increasing the complexity of the problem, the behavior of BRKGA is observed. For this dataset, the obtained near optimal result in the form of total cost is 3185 cost units. The complete lot-sizing schedule obtained by BRKGA is shown in Table 5.

Table 5.

Lot-sizing result of BRKGA.

Items	Periods
	1	2	3	4	5	6	7	8	9	10
1	23	0	18	37	0	0	29	0	28	0
2	13	18	21	0	12	23	0	33	0	0
3	12	24	0	10	18	13	12	10	31	0
4	18	24	0	35	0	0	21	0	23	0
5	12	11	41	0	0	21	0	36	0	0

The BRKGA is also compared with simple GA on the basis of two performance measures, that is, total cost and convergence rate. GA provides the result with 3215 cost units, and it converges in 36 number of generations, while BRKGA converges only in 21 number of generations. The comparative study of BRKGA and GA on the basis of convergence up to near optimal solution is depicted in Figure 6.

Figure 6.

Convergence rate of BRKGA and GA.

The extended version of earlier example is also tested by BRKGA to prove its efficiency and efficacy. The dataset of the problem for 5 items and 16 periods are given in Appendix 2. BRKGA also performs better for such problems with increased complexity. The obtained results are shown in Table 6. By this lot-sizing schedule, the achieved total cost, which is the main objective of the study, is 5523 cost units, and it is achieved only in 32 number of generations. It is again compared with simple GA. The comparative study is shown in the graphical form (Figure 7). From Figure 7, GA provides the minimal solution with 5592 cost units, and it is converges in 49 number of iterations. Therefore, it can be concluded that BRKGA provides better results in less number of iterations.

Table 6.

Lot-sizing result of BRKGA.

Items	Periods
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	23	0	31	0	16	25	0	15	29	0	10	31	0	23	0	10
2	29	0	13	43	0	0	11	28	0	36	0	0	28	0	22	0
3	16	28	0	13	26	0	27	0	36	0	0	17	44	0	0	15
4	10	35	0	0	28	0	10	44	0	0	28	0	22	0	17	13
5	11	40	0	0	18	25	0	26	0	39	0	0	17	15	25	0

Figure 7.

Convergence rate of BRKGA and GA.

The proposed algorithm is tested on a very large-sized MICLSP. The dataset of demand and various costs in 10 time periods for 10 items are given in Appendix 3. The result shows the efficiency of proposed algorithm as it provides the lot-sizing schedule with 6465 cost units. This near optimal schedule is obtained only in 26 number of generations. The obtained schedule is shown in Table 7. On comparison with simple GA, BRKGA proves its supremacy as it converges only in 26 generations compared to 53 generations in GA. The convergence graph for comparative study is shown in Figure 8.

Table 7.

Lot-sizing result of BRKGA.

Items	Periods
	1	2	3	4	5	6	7	8	9	10
1	42	0	0	37	0	0	35	0	28	0
2	18	17	21	0	12	23	0	33	0	0
3	12	34	0	0	18	25	0	10	31	0
4	15	24	0	40	0	0	21	0	23	0
5	13	11	41	0	0	11	18	36	0	0
6	13	29	0	32	0	0	25	0	21	0
7	18	24	0	35	0	0	21	0	23	0
8	23	0	43	0	0	12	11	34	0	12
9	12	21	0	31	0	11	22	0	24	0
10	12	11	41	0	0	25	0	23	0	18

Figure 8.

Convergence rate of BRKGA and GA.

From the above results, it can be concluded that BRKGA is efficient enough to tackle such decision-making problems, which are both computationally complex. BRKGA also proves the superiority over other heuristics as the quality of obtained solution is better and is achieved in less number of generations. For MICLSP, the proposed algorithm is coded in MATLAB programming language, and the experiment has been carried out on Intel core i3 2.13 GHz processor.

Conclusion

Developing a good master production schedule (MPS) is one of the key issues in material requirement planning (MRP)/enterprise resource planning (ERP) system. Some of the problems which the scheduler generally faces are uncertainty in demand, lost sales, backlogging, inventory holding, unavailability of resources and so on. In general, optimized linear programming model for this kind of problems can yield significant improvement in some situations. The main challenge of this combinatorial problem is to satisfy the customer’s demand within the capacity of resources. Among the decision-making problems in the manufacturing environment, the lot-sizing problem is very complex and challenging due to its dynamism and various dependent and independent factors. Therefore, it is very difficult to predict and evaluate the appropriate lot size to fulfill the customer demand with minimal total cost. To solve such a complex combinatorial problem, BRKGA has been proposed. The BRKGA is a modified version of simple GA. To improve the exploration of search space and keeping the quality of the solutions in one generation, an elite group of the solutions is formed. The elite group is carried out for the next generation and is also used as one parent for crossover operation. The present research shows the efficacy of proposed algorithm. It is evident from section “Numerical analysis” that the BRKGA can efficiently handle this complex lot-sizing problem. The comparative study with other algorithms proves the superiority of BRKGA in terms of reduced convergence rate and better quality of solution. The BRKGA has the capability to understand the requirement of the real-world attributes. Therefore, this study will provide a new vision to the managers to achieve the solution in such a way that can fulfill the demand of the customer with minimum total cost while considering the capacity of resources. This research also provides a new managerial insight that the manufacturing for anticipated demand is beneficial in cases where the penalty for lost sale is very high in comparison to the inventory holding and setup costs.

This research provides a new insight to the practitioners as well as researchers about the complexity of MICLSP. As a future scope, this research can be extended by considering other factors such as outsourcing, remanufacturing and back ordering. It is also an interesting aspect to observe the behavior of algorithm with other objectives such as profit margin, customer satisfaction, time minimization and quality improvement. This research can also be applied as multicriteria decision-making problem by considering two or more conflicting natured objectives at the same time. In this study, some other meta-heuristics such as artificial immune system, PSO, and ant colony optimization can also be tested, and their performance can be measured, which can help the managers to develop an algorithm portfolio.