© B. Bao et al., Published by EDP Sciences 2023

1 Introduction

Flexible manufacturing system (FMS) is a technically complex and highly automated system, which relies on limited shared resources to realize the production of diversified parts, with the advantages of improving equipment utilization, increasing system flexibility and reducing production costs. A flexible manufacturing system requires an organic combination of control systems, CNC equipment and workpiece storage and transport systems to process workpieces in a task sequence, the core of which is the job shop scheduling [1]. It is the allocation of the limited resources of the workshop to a number of tasks within a certain period of time to achieve or optimize one or more objectives, which has a major impact on the production efficiency. Comparisons among multiple objectives often need to be made in this process, which may lead to contradictory problems. Therefore, the design of a reasonable scheduling algorithm has long been a question of great interest in flexible manufacturing systems. Especially in the mixed-flow processing scenario, a flexible manufacturing system contains many types of processing equipment. Due to differences in equipment types, tool types and machining processes, the processing time for the same process on different types of equipment for the same part varies. Because of this variation, the choice of which machine to process each task on and in which order plays a key role in the overall machining time for the entire batch of tasks. The selection and design of scheduling algorithms are consequently of great significance for job shop scheduling in mixed flow machining scenarios.

Scholars have conducted a number of in-depth investigations on the design of scheduling algorithms for flexible manufacturing systems. For flexible job shop scheduling problem, Xingquan Zuo et al. used multi-objective variable neighborhood immune algorithm to model and study the FJSSP problem (Flexible Job Shop Scheduling Problem) of a set of workflow models [2]. Jinghe Sun et al. proposed a hybrid multi-objective evolutionary algorithm to solve the flexible job shop scheduling problem of multi-objective flexible processing shop, which optimization objective was to minimize the manufacturing time, total workload and workload of key machines, as well as reward and punish the advance and delay of completion time. Local search power was improved by forbidden search with a neighborhood structure, which in turn guides the algorithm in exploratory approximations to the pareto optimal frontier [3]. Caldeira and Gnanvelbabu proposed an improved Jaya (Multi-objective Jaya algorithm, MOJAYA) algorithm, in which an effective initialization mechanism and local search technology were added. The improved Jaya algorithm could improve the problem that the meta-heuristic algorithm falls into local optimum when searching for the best solution [4]. For flexible job shop scheduling in uncertain environments, Shen et al. developed an improved decomposition-based multi-objective evolutionary algorithm, which employed a sub-problem update method utilizing global information, allowed the elite offspring to remain in the population, and used sub-problem selection and suspension strategies to concentrate more computing on sub-problems with better adaptability. The genetic operator of a particular problem is used to mutate the offspring for better convergence to the optimal solution [5]. For the complex job shop scheduling problem using genetic algorithm, Zhao et al. proposed a genetic algorithm based on the encoding operation and the neighborhood search to optimize job shop scheduling scheme [6]. Wang et al. proposed an open shop scheduling optimization scheme based on diversity-enhanced adaptive genetic algorithm [7]. Min et al. proposed a hierarchical hybrid genetic algorithm with the objective of minimizing total drag time [8]. Zhang et al. took processing time, adjustment time and moving time respectively as independent time factors into the flexible job shop scheduling model to establish a flexible job shop scheduling model considering multiple time constraints with the objectives of minimizing maximum completion time, total adjustment time and total moving time, and proposed an improved genetic algorithm to solve the model [9]. Hong et al. designed a genetic algorithm and simulated annealing algorithm hybrid algorithm to quickly search for the optimal or sub-optimal change occurrence sequence of the time-delayed Petri net model, so as to obtain the system processing optimization path, and proved the effectiveness of the method through simulation [10].

Genetic algorithms are the most widely used method for solving the scheduling problems, researchers have improved their performance by improving various elements of genetic algorithms over the past thirty years. However, most of the procedures in the above literature were arranged in the part order which failed to make the scheduling complicated enough. In order to improve the performance of the scheduling algorithm, this study was carried out based on the genetic algorithms. Five aspects of the scheduling results were compared respectively, including the number of overdue jobs, total overdue time, comprehensive machine load rate, maximum machine load rate and job completion time. Then a better production scheduling was selected by adjusting the population number, the number of iterations, crossover and variation probability of the genetic algorithm.

2 Problem description

The experiments were conducted on a flexible automated production line, which consisted of two horizontal machining centers, one four-axis machining center, two three-axis machining centers and three CNC lathes. It was assumed that twelve parts were processed using this flexible automated production line. A series of production scheduling plans were then obtained by the algorithm simulation. The processing equipment and parts are shown in Table 1.

2.1 Problem description

The Flexible Job Shop Scheduling Problem can be described as: a job set defined as Jop is arranged on a machine tool set defined as M, and the job set J is denoted as: Jop = {Jop0, Jop1, ..., Jopn}; the job Jop_i contains n_i processing processes, and the value of i is from 1 to N; there are M production machines available in the shop, denoted as: {M1, M2, ..., Mn}; each procedure of the workpiece can be completed on any processing machine that meets the processing requirements. Given the machine work calendar and the work processes, production times and lead times, try to find the optimal scheduling solution with a balanced equipment load and the shortest production cycle.

2.2 Constraints

• Each job (workpiece) is scheduled to be processed only once on the production line; the job procedure is processed only once on a single machine tool; the job process cannot be interrupted or suspended.

• The sequence of job processes does not change with the plan of scheduling, but the processing time may change with the choice of machine tool.

• The machine tool can only process one procedure at a time.

2.3 Objective function and mathematical model

(1)

Among:

(2)

Among:

(3)

(4)

(5)

F1: Number of overdue jobs. Number of jobs that cannot be completed within the delivery date. Job Completion Time C_i is the time at which the last procedure in the work calendar is completed and d_i is the delivery time.

F2: Total overdue time. Actual overdue time for all overdue parts on the production line.

F3: Comprehensive load rate of machine tool. The machine tool load rate describes the workload of each equipment, i.e. the ratio of the actual processing time to the total working time before each equipment stops. The comprehensive load rate of a machine tool is the sum of the load rates of a machine tool and describes the general situation of the workload of the equipment on the production line. B_ij (i = 0,1, …, n) is the processing time of all the completed processes on machine tool J. T is the downtime of machine tool J.

F4: Maximum load rate of machine tool. Describe the maximum load rate of bottleneck machine tools on the production line.

F5: Job completion time.

3 Algorithm design

Genetic algorithms are proposed based on the simulation of genetic mechanisms and natural selection processes in nature, including encoding, crossover, variation, selection and other operations [11]. In this study, genetic algorithms were used to design and compare the scheduling schemes for the specificity of multi-constraint and multi-dimensional solutions to the production scheduling problem.

3.1 Chromosome pair encoding

There were two problems to be solved in job shop scheduling: (i) the matching of productive process and production equipment; (ii) the sequencing of procedures [12]. Both kinds of information need to be incorporated into the encoding of chromosomes when utilizing genetic algorithms. On the basis of the genetic mechanism of biological chromosome, two chromosomes with workpiece information were designed: one chromosome represents workpiece process information, called the process gene chain; another chromosome represents the information of the processing equipment in which the workpiece is processed, called the equipment gene chain.

Assuming that there are three workpieces to be processed, of which workpiece 1 has three processes, workpiece 2 and workpiece 3 have two processes and processing equipment has four, a feasible scheduling scheme is shown in Figure 1.

The first row is the process gene chain, where the numbers represent the number of workpieces, and the number of occurrences represents the number of procedures required for the workpiece processing. The second row is the equipment gene chain, where the numbers in the gene chain correspond to the numbers in the process gene chain and the number represent the processing equipment No.

Fig. 1 The chromosome-encoding mode.

3.2 Crossover operator

The gene fragments in the chromosomes were crossed based on the proposed chromosome encoding structure in this study [13]. A random number was generated by the program to determine the starting and ending points of the crossed gene fragments, and then the corresponding fragments of the two sets of chromosomes were crossed over as shown in Figure 2.

Chromosomes after the crossover operation may cause errors in the number of procedures for processing workpieces. The fourth and fifth positions of the parent chromosome were crossed in Figure 2. The workpiece 2 in the process gene chain has three procedures and the workpiece 3 has one procedure, which contradicts the problem description. Therefore, it is necessary to confirm that the workpiece information contained in the chromosome is correct. In order to ensure the diversity of chromosomes and keep the information of chromosome exchange fragments remained, the chromosome fragments other than the exchange fragments need to be calibrated from left to right.

Fig. 2 Schematic diagram of the crossover operation.

3.3 Variant operator

Variation operations were complemented by crossover operations to complete the evolutionary process to increase the chromosome diversity. The starting and the ending points of chromosome variation fragments were determined by a random number. The selected gene fragments were reversed back and forth, and the corresponding processing equipment is mutated in a workpiece procedure, thus producing as many production scheduling schemes as possible [14]. The variation operation is shown in Figure 3, which provides an effective balance in the workload of the equipment and contributes to shortening the completion time.

Fig. 3 Schematic diagram of the variant operation.

3.4 Select actions

The selection operation, the method of chromosome retention after genetic manipulation, was performed in this study using the greedy criterion [15]. The chromosomes of the offspring after the variation operation were mixed with those of the parent, and the adaptation operation of different chromosomes to the scheduling problem was calculated by means of an objective function. Depending on the adaptation to the objective function, the mixed population was evaluated and ranked: the top half of individuals with stronger adaptability were selected for retention; the remaining individuals with weaker adaptability were removed, where the stability of the population was ensured by the selection operation.

3.5 Scheduling scheme based on the genetic algorithm

• Based on the processing task demands, set the number of workpieces to be processed, the number of procedures for each workpiece, and the production equipment to meet the production requirements of each procedure; determine the parameters of the genetic algorithm, including population number, crossover probability, variation probability, and the number of iterations.

• The initial population is randomly generated and the process gene chain and equipment gene chain are randomly generated in accordance with the number of parts, the procedure and the processing equipment that meets the requirements of the procedure.

• Multiple crossover probabilities and variation probabilities are set according to parameters to perform the cross-variance operations to complete the chromosome evolution process.

• Mix the parent with the offspring and use the greedy criterion to select the individuals reserved for iteration.

• Complete the iteration operation, output the chromosome with the strongest adaptability, and then end the algorithm.

4 Experimental analysis and result analysis

A flexible job shop scheduling task was set up: eight processing equipment were placed in the workshop and twelve workpieces were to be processed; each workpiece contained up to four processing procedures; it was assumed that the batch of parts requires processing within forty hours. The processing time of each procedure on each processing equipment is shown in Table 2.

4.1 Experimental results

To explore the appropriate parameter settings for this scheduling problem, four parameters, including population number, crossover probability, variation probability and the number of iterations, were adjusted to compare the effects of the four parameters on the results of job completion time, machine utilization, overall machine utilization, overdue time and number of overdue parts.

The standard control group was set with the following parameters: population number was 100, crossover probability was 0.8, variation probability was 0.2 and the number of iterations was 1000. In this paper, a comparison test was conducted using three parameters that were kept constant and one parameter was adjusted to illustrate the effect of each parameter on the scheduling results.

The results of the control experimental group are shown in Figure 4. The processing efficiency of each processing equipment is: 80.95%, 95.23%, 35.71%, 95.23%, 92.85%, 71.42%, 78.57%, 95.23%, overdue number is 1, overdue time is 2 h, processing completion time is 42h, and the comprehensive utilization rate of equipment is 80.65%.

Fig. 4 Gantt plot of standard control group.

4.1.1 Adjust of the population number

Ten sets of comparison trials were set up for this experiment, adjusted the population number from 50 to 500, and each set of experimental parameters was set in increments of 50.

As shown in Figure 5, the comprehensive utilization rate ranges from 80%–90% and increases slightly with the population number gradually increasing.

Figure 6 illustrates that the overdue phenomenon decreases obviously and stabilizes as the population number gradually increases. What stands out in this figure is that the overdue phenomenon disappears and the scheduling program is able to complete for a fixed period after the population number reaches 300.

As can be seen from Figure 7, the utilization rate of each machine tool fluctuates between 60% and 100% as a result of different scheduling schemes, which is relatively stable. Some of the machines reach 100% utilization, which may give rise to machine failure due to overload or increased wear of the machine over a long period of time, so the maximum utilization rate of the machine should be set to improve the processing efficiency on the premise of ensuring the production life of the machine.

Figure 8 presents that there has been a clear decline in the processing completion time and reaches a rebound at 250. After the population number reaches 300, it shows a stable and gradually decreasing trend, which reveals that the completion time is effectively reduced as the population grows.

By adjusting the population number and comparing the changes in the five parameters of machine tool utilization, the number of overdue workpieces, overdue time, processing efficiency of each machine tool and processing completion time, these results suggested that as the population number increased, the processing completion time was evidently shortened, the overdue phenomenon was gradually reduced, the processing efficiency of machine tools increased slightly, and the processing efficiency of each machine tool fluctuated less. It can be concluded that increasing the population number will have an apparent improvement and optimization effect on the scheduling results, with the consequent problem of a sharp increase in the running time of the program.

Considering the need to keep the running time of the program as short as possible in real production problems, the number of populations corresponding to the stabilization of the scheduling results can be set as an optimal parameter. With reference to the fact that the population number in this paper tends to stabilize at 300, this value was taken to be the optimal solution to this scheduling problem.

Fig. 5 Comprehensive utilization rate of the machine tool.

Fig. 6 Number of overdue workpieces and overdue time.

Fig. 7 Utilization rate of each machine tool.

Fig. 8 Processing completion time.

4.1.2 Adjust the number of iterations

In this experiment, ten groups of comparative experiments were set, and the number of iterations was adjusted from 200 to 2000, with each set of experimental parameters increasing by 200 in turn. It is observed from Figure 9 that the overdue phenomenon is obvious when the number of iterations is small. As the number of iterations increases, the number of overdue workpieces and overdue time gradually decrease. The overdue phenomenon disappears and complete the processing tasks on time around 1800.

Looking at Figure 10, with the increase of the number of iterations, the processing completion time of the workpiece processing task has a marked reduction and fluctuates in a small range. There has been a steady trend and complete the processing tasks on time around 1800.

As shown in Figure 11, the comprehensive utilization rate of machine tool fluctuates slightly in the range of 70–90% with the increase of the iterations. The comprehensive utilization rate of machine tool is relatively high and stable, which is conducive to shortening the processing completion time of workpiece.

From Figure 12 we can see that the utilization rate of each machine tool fluctuates greatly and the low utilization rate of some machine tools results in waste of resources and prolonged completion time of processing tasks with the increase of the iterations. Higher load rate of some machine tools will cause wear of the machine tools, which is not conducive to the maintenance of workshop processing equipment. The processing efficiency of each machine tool gradually stabilizes after the population reaches 1800, and the processing efficiency of each machine tool is relatively balanced.

By adjusting the number of iterations and comparing the changes in machine tool utilization, the number of overdue workpieces, the overdue time, the processing efficiency of each machine tool and the processing completion time, it revealed that the number of iterations had a less obvious effect on the completion time of processing tasks and the balance of the utilization of each machine tool, and that the increase in the number of iterations allowed the genes of the best individuals in the population to spread and pass through, which can effectively improve the results of optimized scheduling. Taking the fact into account that increasing the iterations increases the computational time, the iterations of 1800 is deemed to be the optimal solution for this scheduling problem in this paper.

Fig. 9 Number of overdue workpieces and overdue time.

Fig. 10 Processing completion time.

Fig. 11 Comprehensive utilization rate of the machine tool.

Fig. 12 Utilization rate of each machine tool.

4.1.3 Adjust the crossover probability

In this experiment, ten groups of comparative tests were set, and the crossover probability was adjusted from 0.1 to 1. Each set of experimental parameters is incremented by 0.1 in turn. As can be seen from Figure 13, with the increase of the crossover probability, the comprehensive utilization rate of the machine tool fluctuates within the range of 70%∼100%, and fluctuations are more pronounced at 0.9, but there is no distinct trend.

Looking at Figure 14, it is apparent that with the change of crossover probabilities, processing tasks are completed on time, and some scheduling solutions can complete workpiece processing tasks ahead of schedule, with no overdue occurring and processing completion times fluctuating within 35–40 h.

Figure 15 shows that the utilization rate of each machine tool fluctuates is more obvious with the change of the crossover probability. After the crossover probability is greater than 0.7, the utilization rate of machine tool at all levels is more balanced.

By adjusting the crossover probability, comparing the changes of comprehensive utilization, overdue workpiece number, overdue time, machine tool processing efficiency and processing completion time, it has identified that the crossover probability has little influence on the processing completion time. Processing tasks are completed on time, and some scheduling solutions can complete workpiece processing tasks ahead of schedule. When the crossover probability is small, the normal operation of the machine tool is balanced after the crossover probability is greater than 0.7. Improving the crossover probability can make the spread of genes from excellent individuals with more balanced emission results in the population, helping to improve the quality of the emission results in the whole population. Given the spread of superior genes and the variability of individuals prior to ensuring genetic diversity in the population, the crossover probability of 0.7 is regarded as the optimal solution to this scheduling problem in this paper.

Fig. 13 Comprehensive utilization rate of machine tools.

Fig. 14 Processing completion time.

Fig. 15 Utilization rate of each machine tool.

4.1.4 Adjust the probability of variation

In this experiment, ten sets of comparative tests were set, and the variation probability was adjusted from 0.1 to 1, and each experimental parameter set was added by 0.1 successively. As shown in Figure 16, with the increase of the variation probability, the comprehensive utilization rate of the machine tool fluctuates within the range of 70%∼90%, with a small range of fluctuation and almost remaining steady.

Looking at Figure 17, with the variation probability increases, the number of overdue workpieces and the overdue time decrease first, and the overdue phenomenon disappears when the variation probability is 0.4–0.6, and the processing task is completed on time. When the variation probability is greater than 0.6, the number of overdue workpieces and the overdue time increase noticeably, and the increase is more obvious.

As can be seen in Figure 18, the processing completion time fluctuates from 35 to 40 h with the variation probability changes. When the variation probability is 0.4–0.6, the processing task is completed on time. After the variation probability is greater than 0.6, the overdue phenomenon occurs and the fluctuation range is relatively large.

In Figure 19, with the variation of variation probability, the utilization rate of each machine tool fluctuates evidently. When the variation probability is greater than 0.6 and less than 0.4, each machine tool is unbalanced. When the probability of variation is 0.4 to 0.6, the utilization difference is small and the distribution of each machine tool is relatively balanced.

By adjusting the variation probability and comparing the changes in the five parameters of machine tool overall utilization, number of overdue workpieces, overdue time, processing efficiency of each machine tool and processing completion time, the most obvious finding to emerge is that too large or too small a variation probability would lead to an increase in processing time, thus causing the overdue phenomenon, and would lead to an uneven distribution of the scheduling results on each machine tool, resulting in a more obvious difference in utilization between machine tools, and the variation probability would have less impact on the overall utilization. However, the variation probability has a small impact on the overall utilization of the machine.

A small variation probability results in a homogeneous population with a low probability of new genes appearing, and a large variation probability results in the retention of good genes in the population, leading to a weakening of the quality of the scheduling results. With reference to the influence of the variation probabilities on the parameters, it is concluded that the parameters perform better when the probability of variation is 0.5. It is considered that the probability of variation of 0.5 is the optimal solution to the scheduling problem.

Fig. 16 Comprehensive utilization rate of the machine tool.

Fig. 17 Number of overdue workpieces and overdue time.

Fig. 18 Processing completion time.

Fig. 19 Utilization rate of each machine tool.

4.1.5 Optimum parameter operation results

The results of the optimal parameter group are shown in Figure 20. The processing efficiency of each processing machine was 80.55%, 100%, 91.67%, 97.22%, 97.22%, 80.55%, 80.55% and 63.89% respectively, with no overdue occurring and a processing completion time of thirty-six hours, four hours ahead of schedule, with a comprehensive equipment utilization rate of 86.46%.

The results of the control group and the optimal parametric group are shown in Table 3.

By comparing the results of the control group with the optimal parametric group, an overdue period was found for the control parameter group, while the optimal group completed the processing task within the specified time and four hours ahead of schedule. By comparing the machine load rate and the overall machine load rate, what is striking is that the overall machine load rate of the optimal parametric group was visibly higher than that of the control test group while the load rate of each machine in the control group differed. In contrast, the optimum parameter group had a more balanced distribution of processing tasks and the difference in load rate was definitely reduced. By comparing two groups of parameter settings, it is concluded that the optimal parametric group has significantly improved the scheduling results, and the optimal parameter setting has yielded more satisfactory scheduling results.

Fig. 20 Gantt plot of the optimal parameter production scheduling results.

5 Conclusion

In this study, a genetic algorithm is used to design production scheduling for a flexible manufacturing system. The following conclusions can be drawn from the present study:

• Increasing the population number and the number of iterations could effectively increase the diversity of the population by adjusting the parameters of population number, the number of iterations and cross-variance probability in the algorithm, which could shorten the job completion time and improve the machine tool loading rate to a certain extent.

• The job completion time as well as the machine tool loading rate did not change much by adjusting the cross-variance probability.

• Increasing the number of populations and the number of iterations can gradually improve the genetic stability of the populations, evidently shorten the processing completion time, significantly improve the overall machine utilization and stabilize the results.

• Increasing the crossover probability within a certain range promotes the spread of genes of superior individuals in the population and contributes to the stability of the population, as well as more balanced scheduling results on each machine and less variation in the utilization of each machine.

• When the probability of variation is small, the genetic diversity in the population is poor, which is not conducive to the generation of new superior scheduling results. When the probability of variation is large, the genes of superior individuals in the population cannot be retained, which is not conducive to the evolutionary stability of the population. A suitable variation probability can ensure both population diversity and population evolutionary stability.

This study can provide a reference for the setting of parameters for subsequent genetic algorithm based multi-objective optimization scheduling algorithms. Subsequent research can be carried out to improve the algorithm so that jobs can be arranged as tightly as possible on each processing machine to increase the machine load rate and shorten the job completion time.

Acknowledgments

Acknowledgement. The authors would like to thank the financial support from Sichuan Province Major Science and Technology Special Project “Key Technology Research and Application Demonstration of Digital Workshop of Complex Precision Parts of Electronic Products” (Grant No. 2020ZDZX0025).

References

All Tables

All Figures

	Fig. 1 The chromosome-encoding mode.
In the text

	Fig. 2 Schematic diagram of the crossover operation.
In the text

	Fig. 3 Schematic diagram of the variant operation.
In the text

	Fig. 4 Gantt plot of standard control group.
In the text

	Fig. 5 Comprehensive utilization rate of the machine tool.
In the text

	Fig. 6 Number of overdue workpieces and overdue time.
In the text

	Fig. 7 Utilization rate of each machine tool.
In the text

	Fig. 8 Processing completion time.
In the text

	Fig. 9 Number of overdue workpieces and overdue time.
In the text

	Fig. 10 Processing completion time.
In the text

	Fig. 11 Comprehensive utilization rate of the machine tool.
In the text

	Fig. 12 Utilization rate of each machine tool.
In the text

	Fig. 13 Comprehensive utilization rate of machine tools.
In the text

	Fig. 14 Processing completion time.
In the text

	Fig. 15 Utilization rate of each machine tool.
In the text

	Fig. 16 Comprehensive utilization rate of the machine tool.
In the text

	Fig. 17 Number of overdue workpieces and overdue time.
In the text

	Fig. 18 Processing completion time.
In the text

	Fig. 19 Utilization rate of each machine tool.
In the text

	Fig. 20 Gantt plot of the optimal parameter production scheduling results.
In the text