Application of Modified Steady-State Genetic Algorithm for Batch Sizing and Scheduling Problem with Limited Buffers

Abstract

Batch sizing and scheduling problems are usually tough to solve because they seek solutions in a vast combinatorial space of possible solutions. This research aimed to test and further develop a scheduling method based on a modified steady-state genetic algorithm and test its performance, in both the speed (low computational time) and quality of the final results as low makespan values. This paper explores the problem of determining the order and size of the product batches in a hybrid flow shop with a limited buffer according to the problem that is faced in real-life. Another goal of this research was to develop a new reliable software/computer program tool in c# that can also be used in production, and as result, obtain a flexible software solution for further research. In all of the optimizations, the initial population of the genetic algorithm was randomly generated. The quality of the obtained results, and the short computation time, together with the flexibility of the genetic paradigm prove the effectiveness of the proposed algorithm and method to solve this problem.

1. Introduction

A genetic algorithm (GA) is a heuristic search that mimics the process of natural evolution. The use of genetic algorithms for optimization was first introduced by Holland [1]. It is a stochastic heuristics technique which encompasses a semi-random search method whose mechanism is based on the evolutionary processes that occur in nature. The search method in a genetic algorithm is not based on improving a single solution, and instead, a genetic algorithm works with multiple possible solutions. The GA as a search mechanism is usually used when there is very little knowledge of the solution space or when there are far too many possible solutions to use the standard search/optimization methods.

Many commonly used genetic algorithms have a major drawback: they have high computational power requirements and some have high demands on the CPU or memory of it, or usually, both, so a modified genetic algorithm based on a steady-state genetic algorithm (SSGA) was developed with the following goals:

• To have reliable results;
• To be fast;
• To be suitable to run in a highly parallelized computer environment;
• To have low demands on the computer memory;
• Keep a low number of genetically identical individuals;

Based on the chosen algorithm, completely new software for testing was written in C#.

The schedule and size of the product batches and buffer configuration are among the major problems in manufacturing since manufacturing systems in a real environment have frequent requirements for change. This is mainly due to today’s turbulent manufacturing environment calls for adaptive and rapidly responding manufacturing systems because there is a high level of market competition. Other reasons for this can be problems in the supply of raw material or energy and there being a long downtime due to the malfunction of production equipment. So, flexibility and re-configurability are becoming more and more important in modern manufacturing [2]. Those who are responsible for making strategic decisions in manufacturing companies must have relevant pieces of information as soon as possible to make relevant decisions on how to use the available resources and retain market competitiveness.

The buffer storage in production serves to decrease and balance the processing times, increase the production flexibility and decrease the impact of the breakdowns in production, but they are at the cost of additional capital investment, the floor space of the line, and using more inventory. Hence, the determining size and allocation of the buffer storage in manufacturing systems has both theoretical and practical interests.

In this paper, the performance of a specially developed software-based modified genetic algorithm was tested on the real-life problem of determining the size and schedule of the product batches with multiple buffer storage configurations in a hybrid flow shop (HFS). The study showed that the proposed approach was highly effective in the finding acceptable solutions for all of the problem sets that were examined.

2. Literature Review

A large number of studies can be found in the literature which solve the problem of determining the batch size and schedule in a HFS. According to Ribas et al. [3], a HFS actually represents the production systems where a larger range of products move unidirectional through several production stages. In each production stage, there are one or more identical production capacities. A literature review on hybrid flow shop scheduling problem was given by Ruiz and Vázquez-Rodríguez [4] and Tosun et al. [5]. This type of manufacturing system is characteristic of many processes and discrete manufacturing companies from the real environment [6], such as automobile manufacturing, machinery manufacturing, etc. For this reason, this type of manufacturing system was chosen as the subject of research.

A HFS scheduling problem is a complex combinatorial problem. There are many different variations of this problem, i.e., it differs depending on several factors, such as the understanding of the environmental assumptions, constraints or performance measures that are to be achieved [7]. For example, many authors have used different methods to minimize the makespan [8,9,10,11]. Makespan is one of the most frequently used performance measures because makespan directly affects the performance of the manufacturing efficiency in the form of there being satisfying delivery that is on time and reducing the production costs. Additionally, other performance measures have been observed, as can be seen detailed in [12,13].

Market uncertainty and a change in the production philosophies, where the stocks represent direct losses for many processes and discrete manufacturing companies, necessitate the production of a wide range of products within the timeframe. This leads to an increasing challenge in terms of determining the batch size and schedule. With this realization, the research attention focused on making both decisions at the same time has increased [14]. In addition, there is an increasing number of papers that deal with these problems using real-world examples [15,16,17].

Besides batch sizing and scheduling, the problem of accumulating product units between the manufacturing stages is also a major problem. Therefore, it is important to know what capacity of buffer storage to provide for the smooth running of the production. Leisten [18] spoke about the influence of a limited buffer in 1990. Makespan minimization problems for a two-stage flow shop with a limited buffer were considered in [19,20]. Jiang and Zhang [21] were investigated an energy-oriented scheduling problem deriving from a hybrid flow shop with limited buffers. A solution for multi-objective permutation flow-shop scheduling problems with limited buffers was presented by Qian et al. They proposed an effective hybrid algorithm based on differential evolution [22]. For the same type of problem, Liang et al. [23] developed a multi-objective hybrid self-adaptive differential evolution optimization algorithm. Zohali et al. [24] developed a metaheuristic algorithm, which was called the discrete fruit fly algorithm, to solve a batch scheduling problem in a hybrid flow shop with limited buffers. Marinelli et al. [25] dealt with capacitated batch sizing and a scheduling problem with parallel machines and shared buffers. Batch sizing and scheduling problems with buffer constraints were also presented by Sundaramoorthy and Maravelias [26].

For solving the batch sizing and scheduling problems and buffer configuration problems, one of the most commonly used methods and techniques is GA. GA has proven to be a relatively good optimization tool. An example of that is given by Shen, K. et al. [16]. Han et al. [17] proposed an improved compact genetic algorithm in a hybrid flow shop with a multi-queue buffer. Amjad et al. developed and implemented a modified GA for makespan optimization, where the GA was initialized based upon global, local and random selection techniques, and adaptive reproductive operators were applied to intelligently evolve the algorithm [27]. For solving the multi-objective optimization problem in HFS, Chen and Zhao [28] introduced new constraints and improved the traditional GA. By combining a Random Key Genetic Algorithm (RKGA) and a Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS), Karacan et al. [29] proposed a new integrated methodology.

However, many of the proposed ones do not give results enough fast or some modifications are needed to ensure that it is easier to apply them. Therefore, this paper proposes a modified steady-state GA to solve this type of problem, which will serve as a kind of tool for the fast and efficient determination of the batch size and schedule.

So, the first step in this study was to create a modified GA that would be easy to apply and give results quickly. Additionally, the second step was to apply the modified GA to a real-world example with the aim to determine the batch size and schedule and the required buffer configuration.

3. The problem Formulation

3.1. Notation

The production system and all the data used in this article are based on data from the real world. The problems of the manufacturing company are to find the appropriate batch size for each product type, to order the allocation of the production capacities to each batch of products and to determine the necessary buffer configuration to ensure that smooth production occurs and to ensure that the delivery is on time.

The parameters used in this paper are given in Appendix A.

3.2. Description

The plant is producing groups of technologically similar products. The technologically similar products are those that have a high degree of similarity in the order of processing and duration of the operations. In this case, the plant is producing three types of technologically similar products (which are labelled as D, E and F) and the delivery is scheduled every two weeks. The targeted two-week production for each product is given in

Table 1. Two-week production goal.

j	D	E	F
qj	4616	3232	2616

as q_j (q_D, q_E, q_F).

The working week lasts for five days and in two shifts. Each shift lasts eight hours, so the maximum availability of the production equipment, in this paper, was 160 h (C_goal = 160 h). The makespan C_calc must be lower than the maximum availability of the production equipment (1) or there will be a delay in the delivery, which should definitely be avoided.

C_calc < C_goal,

(1)

Delivering on time is a condition that has to be satisfied, but it is not required that the makespan must be as small as possible. Every value that satisfies that the delivery is on time is acceptable. The processing times p_ijk for the operations o_ij are given in

Table 2. Processing times (in hours).

oij	D	E	F	Mi
1	0.028	0.035	0.036	3
2	0.031	0.035	0.036	3
3	0.012	0.010	0.010	1
4	0.020	0.019	0.017	2
5	0.008	0.012	0.014	1

.

This production system is typically a hybrid flow shop. Precisely, this production system has five stages, where each stage consists of the M_i number of the same machines. All three types of products pass unidirectionally through the production system and are processed at each stage.

The arrival time of each batch at the stage where the type of product that is produced is different from the previously processed one, and this means that there is a need to setup the workplace. The setup times are defined as being relatively long, in this case, this is mainly because of the client’s request. Since, there are technologically similar products, the same setup time was used for all of the possible combinations of product changes at the same stage. Therefore, the setup time ST_i for each stage is defined, as can be seen in

Table 3. Setup times (in hours).

i	1	2	3	4	5
STi	0.233	0.233	0.267	0.267	0.267

.

As mentioned before, the products travel in batches through the production system. Due to the simplicity of production management and control, the quantity of products in each batch of the same type of product B_jb is set as equal (2). Except in the last batch B_jl, where the quantity of product is equal to the remaining difference between the production goal of the same type of product and the quantity of product that has been produced so far (3). The order in which the batches of products enter the system is not defined, but it is completely random.

B_j1= B_j2  = … = B_{j(l − 1)},

(2)

B_jl = q_j − B_j · (l − 1),

(3)

After finishing the processing at the previous stage, the batch is sent directly to the next stage if that stage is not occupied. Otherwise, the previous stage is blocked. For this reason, a buffer f is needed between each stage that can receive a certain amount of product. There are a total of four buffers where each can receive a different amount of product. It is worth noting that several different batches can be on the same buffer at the same time. The buffer can be recharged until the moment that it can no longer receive the entire batch. In that case, the batch is waiting in the previous stage for the space in the buffer to be freed up. After the next stage is empty (releasing the previous batch), then it is occupied by the batch that first arrived on that buffer (according to the FIFO principle).

The batch size directly affects the required buffer size. On the other hand, the buffer size takes up space in the production plant. When the problem of batch scheduling is added to all this, it is necessary to adjust these values in order to achieve optimal results. First of all, this is performed to satisfy the on-time delivery demand.

In the first step, it is necessary to determine whether the defined production goals can be produced. If it is possible to deliver them on time, we must determine which buffer configuration is required at which position. After that, it is necessary to determine the batch size and the order for the proposed buffer configurations, and observe which one gives the best result in terms of satisfying that the delivery is on time.

In the optimization process, the following statements were also taken into account:

• All stages, machines and buffers are available at time 0;
• All jobs are released at time 0;
• Every operation is a part of a chain of operations;
• The order of operations must be followed;
• All of the operations of a given job have to be processed in a given order;
• Two operations of a job cannot be processed at the same time;
• Each machine can process at most one operation at a time;
• Once processing starts on a given machine, it must complete on that particular machine without any interruption;
• The utilization of each machine is set as 0.85;
• Each operation has a fixed duration.

4. Genetic Algorithms Parameters

4.1. Initial Population

In all of the calculations for this paper, the initial population has been created completely randomly. Such an approach in the process of creation of the initial population, in some cases, can result in a longer search time and require more computational resources, but this approach provides the initial population with a high genetic diversity and a larger pool of genetic material. Such as in real life, in nature, a high level of the genetic diversity of a certain species increases the likeliness that that species will find (better) solutions for the challenges of evolution. Therefore, population sizes of 100 individuals were used.

4.2. Coding and Decoding of Organisms (Solutions)

The first step in constructing a genetic algorithm is to define an appropriate genetic representation and coding. Choosing a good representation is very important because this step significantly affects all of the other steps in the algorithm, and consequently, it has a big impact on the quality of results and speed of the algorithm. In determining the genetic representation, the goal was also to obtain flexible code representation for further research and software development.

A set of three 2D (two-dimensional) integer arrays were used for the chromosome representation:

• Product sequence array—Integer type;
• Batch quantity array—Integer type;
• Fitness array—(real number) double-precision floating-point type.

The usage of one 3D (three-dimensional) array is less challenging from a programmer’s point of view, but with the 2D arrays, the computer program runs significantly faster. Before the final decision could be made on how to define the genetic representation, another computer program was written to test memory operations speed, and the test showed that usage of 2D arrays runs approx. 20 percent faster.

4.3. Solution Decoding

For better software efficiency, the GA population (possible solutions) were coded, and at the end of the GA, the best solution has to be converted into a more readable format. The decoding was performed by connecting the corresponding values from two arrays—Figure 1. The first array contains the product designation and the second batch size. By combining these two values, we obtain results that are in an easily readable format.

4.4. Crossover (and Selection)

In the genetic algorithm that was used in this research, the processes of selection and crossover are combined — Figure 2. This approach is inspired by nature: a habitat with strict boundaries can support only a certain number of species, and this number is limited by the habitat’s resources, and also, the species tend to grow until the habitat’s limit is reached. Individuals that are more adjusted to the environment tend to outlive the individuals that are less adjusted to the habitat parameters. As it was inspired by this idea, in this algorithm, there is no selection for a standalone GA operator in which part of the population is removed, and instead, the removal of the individuals is integrated with the crossover GA operator, and only one individual is removed in each step. The emptied space is fulfilled with an individual that is created during the crossover operation. Also, during this process, the removal of identical individuals is integrated to keep the genetic diversity within the population as high as possible. If two parents that are selected for the crossover operation have the same fitness, then their genome is compared, and if they are identical, one of them is removed from the population to make space for the new individual that will be created in the crossover process.

Step 1: In the first step, two individuals from the population are selected, and they will be used as the parents. Their genetic material will be used in the process of the crossover and the creation of a new individual. The selection of parents is completely random, and all of the individuals in the population have equal chances to be selected.

Step 2: In this step, the fitness of two individuals that were selected as parents are compared. In the first stage of comparison, their fitness is compared, and if they do not have the same fitness, they do not have an identical genome, and their genetic material can be used in the creation of a new individual, and so the algorithm continues on to step 3a. However, if they have the same fitness, an additional check is made, and their complete genome is compared. In the case of two non-identical individuals, the algorithm continues on to step 3a. Otherwise, the algorithm continues on to step 3b.

Step 3a: Since the parents are not identical, the individual with the worst fitness is removed from the population to make space for the individual that will be created in step 4. (Since it has the lowest fitness in the population, it is most likely that the usage of genetic material from this individual will not produce competitive offspring.)

Step 3b: Because in step 2, two genetically identical parents were selected. The result of the crossover process would be the creation of a new individual that is genetically identical to its parents. To avoid this, one of the parents is removed from the population, and randomly selected individuals take its place. This mechanism not only prevents the creation of identical individuals, but it can also remove individuals with identical genomes. The usage of this mechanism also prevents the loss of genetic material (and consequently, it increases the chance to obtain better final algorithm results).

Step 4: The new individual is created as a result of the combination of the genetic material of its parents, and the newly created individual takes the place of the removed one, and the population again has a size determined by the habitat. After the new individual is created, its fitness is calculated, and if it has the best or worst fitness in the population, it is marked as such. This is the approach to selection in the genetic algorithm:

• It ensures the minimum loss of material from the genetic pool, and consequently, it has a higher chance to produce better results;
• It has minimum requirements towards the computer memory since needs space for only one population in computer memory;
• There is no need to sort the population-based on fitness and/or to make many comparisons of fitness within the population.

4.5. Mutation

A mutation introduces new genetic material into the population to enhance the diversity of a population. In GA, a mutation is applied with a small probability since a large probability of a mutation may lead to loss of good genetic material, and as a result, a downgrade in the quality of results, and it may make the algorithm slower.

In this case, there are two possible types of mutation: the change of the batch order or the change of the batch size. In the first case, the case change of the batch order mutation process is fairly simple. Only two genes replace their position. However, in the case of a change of the batch size, additional modifications are required. To maintain the predefined quantity of the product, in most cases, it is necessary to correct the number of batches and size of the last batch. Batches that had to be added or removed and their position are determined randomly.

This approach to the genetic algorithm enables us to make multiple mutations (modification of genome) and/or multiple selections and crossover operations at the same time.

4.6. Definition of the Fitness Function

After the creation of the initial population, the fitness of each individual in the population C_fitness (4) is calculated.

C_fitness = C_calc + C_penaltyl,

(4)

Since, in this case, the delivery condition has to be satisfied, penalization of the possible solutions (5) that do not satisfy this condition was introduced into the fitness formula as C_penalty.

C_{calc, penalty} = C_calc − C_goal

if C_{calc, penalty} > 0

– C_penalty = (1 + C_{calc, penalty}) · (C_calc − C_goal)

else

(5)

– C_penalty = 0

end,

5. Results and Discussion

5.1. Computational Time

The computer program was launched 100 times with different population sizes on the personal computer with AMD Ryzen 7 2700X Eight-Core Processor at 3.70 GHz CPU, 16 GB RAM and Windows 10 operating system. The population size was 100 individuals. The mutation rate was 2%, and the crossover rate was 75 % of the population (the number of selection/crossover operations in each generation was 0.75 of the population number) in 200 generations. The average running time is shown in

Table 4. Running time.

		Population Size [pcs]
		50	100	200	300	500
Generations	100	00:09.273	00:20.211	00:44.316	01:01.513	01:46.551
	200	00:12.772	00:35.135	01:26.321	02:17.244	03:00.225

. The software has two modes: “normal” and “log”. In the “log” mode, the software keeps logs of some operation/calculation, and that makes it approximately 30 % slower. The values in Table 4 were achieved in the “normal” mode.

Increasing the GA parameters over 200 generations and 100 individuals in the population did not produce better results, and the calculation time was still acceptable, so these GA parameters were used in the further calculation.

For the comparison, the results and speed of the steady-state algorithm (SSga) that was used in this research were compared with the steady-state generation algorithm (SSGga). After consecutive 100 runs, the average calculated makespan value was lower (better) with the steady-state (SSga) algorithm. On the other hand, the steady-state generation algorithm (SSGga) had a better performance regarding the software run-time, as shown in

Table 5. Makespan and running time (SS-GA and SSG-GA).

Algorithm	avg. Time [sec]	avg. Makespan [h]
steady-state algorithm (SS-GA)	36.778	160.087
steady-state generation algorithm (SSG-GA)	19.181	162.103

.

Despite the much lower computational time of the steady-state generation algorithm, priority was given to the quality of the results of the steady-state algorithm because the duration of the execution is acceptable in both cases.

5.2. Results

The software was also used to test multiple real-world problems in the industry using multiple scenarios. The research was conducted in two stages:

• The analysis of the need for a buffer in production;
• The analysis of the possible buffer configuration scenarios.

In the first step, a set of simulations was conducted to find where the greatest need for a buffer between the operations was. So, in this set of simulations, a GA without buffer limitations was executed 100 times. The ten best results were taken into consideration to find out the buffer needs (

Table 6. Required buffer configuration.

Cfitness	BD	BE	BF	F1_MAX	F2_MAX	F3_MAX	F4_MAX
155.610	119	295	164	595	238	164	357
156.534	123	225	159	680	434	159	492
156.827	161	156	147	591	322	156	322
157.173	230	267	170	526	267	198	340
157.273	229	182	253	676	265	182	482
157.309	224	200	300	704	360	216	448
157.314	201	233	255	605	267	66	468
157.334	137	135	209	643	369	137	542
157.455	184	260	175	568	260	184	368
157.603	178	126	157	544	178	157	304
			Average:	613.2	296.0	161.9	412.3

). The buffer is shown as a number of pieces, and since all three products are similar, the buffer capacity is same for all three products.

As can be seen in the last row in Table 6, the requirements for the buffer are the largest between the first and second operations and between the fourth and fifth production stages. Otherwise, the smallest buffer requirements is between the third and fourth production stages. These results were taken into consideration for the next stage, i.e., determining the optimal buffer configuration.

In the second stage, we tested six possible buffer configurations (BC1-BC6). The configurations were determined according to the data from Table 6, and the situations in the production facility and six possible configurations were taken into consideration (

Table 7. Buffer configurations and results.

Buffer Configuration	F1	F2	F3	F4	BD	BE	BF	Average Cfitness	Best Cfitness
BC1	90	90	90	90	87	86	75	163.787	159.038
BC2	90	60	90	120	60	60	59	171.562	166.604
BC3	90	90	60	120	54	60	60	171.353	165.592
BC4	120	60	90	90	56	60	57	171.526	165.842
BC5	120	90	60	90	60	60	59	171.562	166.604
BC6	120	60	60	120	60	60	53	170.464	165.383

). For each scenario, the GA was executed 100 times with the same parameters as in 5.1.

According to the simulation results, the best makespan was achieved with the BC1 buffer configuration, both in an average value for 100 consecutive simulations and with the best overall result. The BC1 buffer configuration is also the only buffer configuration that meets the specified condition of there being an on-time delivery.

6. Conclusions and Future Research

In this paper, a modified steady-state genetic algorithm was tested to solve the optimization problem. The problem of determining the batch order and the size of three technologically similar products in a hybrid flow shop with a limited buffer capacity was taken from the real environment. The results that were obtained in chapter 5 of this research show that both the performance and speed of this algorithm are quite good, and that the development of highly specialized and custom-made software can be taken into consideration during the process of production planning.

In short, the low execution time of the algorithm allows for the testing of many possible scenarios, and consequently, it obtains a better production process configuration. The results also show that the software based on the developed algorithm can serve as a reliable tool for its use in production planning. This can be very important in cases where there is not much available time to make new production configurations from scratch or to reconfigure existing ones.

Although genetic algorithms have been recognized as effective search algorithms for many years, continuous improvements in computer performances open new possibilities for the further development of genetic algorithms. In future research, the performance of the genetic algorithm that is used in this paper will be tested on even more complex problems to prove the capability of the algorithm to obtain reliable results.

The GA that was developed and used in this research is very suitable for parallelization and its use on modern multicore CPUs. It can be assumed that the parallelization of the computer code for the proposed genetic algorithm could bring significant performance improvements, and that the algorithm can work on highly parallelized computing systems. In this paper, we used a single thread solution, and so, a further reduction of the computational time is possible with some code modifications being performed. In further research, it is possible to investigate single multi-tread vs. multiple single thread solutions.