As a typical transportation tool in the intelligent manufacturing system, Automatic Guided Vehicle (AGV) plays an indispensable role in the automatic production process of the workshop. Therefore, integrating AGV resources into production scheduling has become a research hotspot. For the scheduling problem of the flexible job shop adopting segmented AGV, a dual-resource scheduling optimization mathematical model of machine tools and AGVs is established by minimizing the maximum completion time as the objective function, and an improved genetic algorithm is designed to solve the problem in this study. The algorithm designs a two-layer coding method based on process coding and machine tool coding and embeds the task allocation of AGV into the decoding process to realize the real dual resource integrated scheduling. When initializing the population, three strategies are designed to ensure the diversity of the population. In order to improve the local search ability and the quality of the solution of the genetic algorithm, three neighborhood structures are designed for variable neighborhood search. The superiority of the improved genetic algorithm and the influence of the location and number of transfer stations on scheduling results are verified in two cases.
With the change of market demand, the current manufacturing industry presents the characteristics of multi-variety, small batch and short cycle, which puts forward higher requirements for the optimization of the production process and the formulation of the production plan. How to shorten the manufacturing cycle and improve the utilization rate of production resources has become the key to the development of the manufacturing industry under the background of intelligent manufacturing. In the traditional flexible job shop scheduling problem, the transfer time of the workpiece is not considered or assumed to be a fixed time considered within the processing time of the workpiece, which does not conform to the actual processing situation [
For the dual-resource scheduling problem of machine tools and AGVs in flexible job shops, many scholars have carried out a lot of research. Aiming at the integrated scheduling problem of machine and AGV, Philippe et al. [
However, few studies can truly integrate the traditional flexible job shop scheduling problem with the task allocation and path planning problem of AGV, owing to the complexity of the machine tool and AGV dual-resource scheduling problem. Two common strategies are used to study the dual-resource scheduling problem: one is solving the problem of machine allocation and process arrangement first, then scheduling AGV, and the dynamic programming method is mainly adopted to solve these problems. The other is scheduling the machine and AGV simultaneously under the assumption that the AGV path is known without collision, and genetic algorithm, simulated annealing algorithm, particle swarm optimization algorithm, tabu search algorithm, and other intelligent optimization algorithms are used to solve the problem [
There is no collision conflict in the transport process of the segmented AGV studied in this paper, and the configuration of the transportation system is flexible. The position and number of the transfer station can be adjusted according to the different processing tasks and the number of used machine tools, to ensure the transportation efficiency and load balance of each AGV as far as possible, and promote the production efficiency of small and medium-sized processing workshop to maximize. To realize the real integrated scheduling of segmented AGV and the machine tool, an improved genetic algorithm is designed to solve the problem. The transfer time of the workpiece and the task allocation of AGV is embedded in the decoding process, and the optimal scheduling scheme is solved by iterative optimization. The superiority of the improved genetic algorithm in this paper is verified by solving the extended case of Brandimarte scheduling example MK02, and the extended case based on MK04 verified that setting different locations and the number of transfer stations has a greater impact on scheduling results.
There are
The assumptions are as follows:
Each process cannot be interrupted after it begins processing. The loading and unloading time of the machine tool is included in the processing time, and the processing time is known. The material buffer area of each machine tool and the transfer station is infinite, and the transfer station allows two AGVs to be parked at the same time. The AGV can be bidirectional in their respective sections, and the driving speed is not affected by no-load or load. Before processing, all workpieces are in the warehouse. In the segmentation containing the warehouse, AGV is parked at the Outbound platform of the warehouse, and AGVs in other segmentations are docked at the transfer station. AGV power, breakdown, and other factors are not considered. The time of AGV loading and unloading the workpiece is calculated within the transfer time.
Before establishing the mathematical model of dual-resource scheduling, the introduced symbols and decision variables are defined and explained as follows:
Decision variables:
Aiming at the flexible job shop scheduling of segmented AGV, a mathematical model is established to minimize the maximum completion time
Objective function:
Constraint conditions:
Among them,
For solving flexible job shop scheduling problems, scholars have tried to use many intelligent algorithms, such as genetic algorithm, simulated annealing algorithm, particle swarm optimization algorithm, tabu search algorithm, and so on. Among them, the simulated annealing algorithm has a simple calculation process, strong robustness, and global search capability, but the convergence speed of the algorithm is slow, and the initial value and parameter setting of the algorithm have a great influence on the performance of the algorithm [
Therefore, For the dual-resource scheduling problem of segmented AGV flexible job shop, a single intelligent optimization algorithm is difficult to solve the optimal solution. Since the genetic algorithm has been very mature in solving the flexible job shop scheduling problem, an improved genetic algorithm is designed in this paper to solve the problem. Local selection, random selection, and hill climbing algorithm are used to generate the initial population to improve the quality of the initial population [
In this paper, the two-level coding method based on process coding and machine tool coding is adopted.
When initializing the population, the process-based coding is combined with the hill climbing algorithm to improve the quality of the initial solution and the convergence speed of the algorithm. Based on machine tool coding combined with random selection and local selection strategy, random selection can promote the initial population to be distributed in the solution space evenly, maintain the diversity of the initial population, and improve the global search ability of the algorithm. And the local selection is conducive to promoting the load balance of machine tools. The details are as follows.
Starting from process 1 of workpiece 1 in the workpiece set, randomly select a machine tool from the set of optional machine tools for this process, then record the machine number and fill in the corresponding gene position, and so on, until the last process of the last workpiece has selected the processing machine.
First, the process 1 of workpiece 1 is given as the current process, and the processing time corresponding to each machine tool in the set of optional machine tools is added to the time value in the corresponding array position of the machine tool. The machine tool with the smallest sum obtains the task of processing the current process, and the machine tool number is recorded to the corresponding gene position, then the processing time of the machine tool is accumulated to the corresponding array position of the machine tool. The next process of the workpiece is selected to perform the same operation until all processes of the current workpiece are selected to process the machine tool, and the time records in the corresponding position array of the machine tool are cleared. Then select the next workpiece, and continue to perform the above operations until all processes of the workpiece are selected to complete the processing machine.
The process-based coding uses a random way for initialization first, then randomly selects some individuals to use the hill climbing algorithm. The specific steps are as follows:
Step 1: Select one of the individuals in the group that needs to be operated by hill climbing algorithm, and calculate the fitness of the individual;
Step 2: Two genes were selected randomly for exchange on the gene sequence based on process coding to obtain new individuals;
Step 3: Calculate the fitness of the new individual, if it is better than the original one, replace it, otherwise do not change;
Step 4: Repeat Step 2 and Step 3 until the number of iterations is met;
Step 5: Perform the above operations on other individuals who need to perform the mountain climbing algorithm operation, and return to the original population when all is completed.
In this paper, a mixed selection strategy of elite retention and tournament method is adopted. Firstly, an elite pool is established with 10% of the population size to determine whether there are individuals in the population that are better than those in the elite pool. If there are, the worst individuals in the elite pool will be replaced, and the elite pool will be updated. Then the individuals in the elite pool are directly copied to the cross pool. Secondly, according to the tournament method to select individuals into the next generation of population, until the selected individuals amount to the appropriate number, and then mutation operation will be taken to maintain the diversity of the population and prevent falling into local optimum.
According to the above coding characteristics, the gene sequence based on process coding adopts Improved Precedence Operation Crossover (IPOX), and the gene sequence based on machine coding adopts Maximal Preservative Crossover (MPX).
As shown in All workpieces are randomly divided into two sets Copy Copy
As shown in Randomly generate a set The processes corresponding to the position of number 1 in
The mutation process and schematic diagram are as follows. Randomly select two genes for exchange from the gene sequence based on the process coding, as shown in Since there are multiple machine tool options for each process, a gene is randomly selected from the gene string based on the machine code, and its corresponding workpiece and process number are determined. Then another machine tool is randomly selected from the set of optional machines for the process to replace. The current machine tool is shown in
In order to prevent the genetic algorithm from falling into the local optimum, the following three neighborhood structures are used to design the variable neighborhood search algorithm, so as to improve the local search ability and the quality of the solution of the genetic algorithm. Variable neighborhood search algorithm steps are as follows:
Step 1: Given the initial solution
Step 2: The neighborhood structure
Step 3: If
Step 4: If
Step 5: Output the optimal solution
As shown in
As shown in
As shown in
In this paper, a decoding scheme is designed for the dual-resource scheduling model of segmented AGVs and machine tools. In the decoding process, the transfer time of the workpieces and the task allocation of AGVs are considered, and the real integrated scheduling of machine tools and AGVs is realized. The specific steps are as follows:
Step 1: Initialize the time record table of each machine tool, the processing time record table of each process, the AGV position node record table
Step 2: The gene sequence based on process coding is transformed into the corresponding process sequence; from left to right read the sequence of genes in the process, and the corresponding process
Step 3: Judge the number of AGVs required by this transfer task. If 0 AGVs are required, it means that the same machine tool is used for this process and the previous one, go to Step 13. If 1 AGV is required, it means that this process is processed in the same segmentation as the previous one, go to Step 8. If more than one AGV is required, it means that the processing is not in the same segmentation, go to Step 4;
Step 4: Read the AGV collection and the transfer station collection in turn from left to right. If the AGV is the first in the collection, go to Step 5, if it is the last one, go to Step 7, and if it is not the first or last one, go to Step 6, until the AGV collection is traversed completely;
Step 5: According to whether the transfer task is the first process, determine the position of the starting point of the AGV that performs the transfer task. If it is the first process, go to Step 9, if not, go to Step 10;
Step 6: The starting position of the AGV transfer task is at the transfer station
Step 7: The starting position of the AGV transfer task is at the transfer station
Step 8: Only one AGV is required for the transfer task. If it is the first process, the starting point is at the warehouse outbound platform, go to Step 9. If it is not the first process, the starting point is on the machine tool where the previous process is located, go to Step 11;
Step 9: AGV takes the position node
Step 10: AGV takes the position node
Step 11: AGV takes the position node
Step 12: The earliest starting processing time of the workpiece is the time node
Step 13: Judge whether the process is the last, if so, terminate; if not, go to Step 2.
The specific process of the improved genetic algorithm in this paper is shown in
In this paper, the extended case based on Brandimarte scheduling instance MK02 is used to verify the algorithm. The workshop layout is shown in
Based on the job shop layout and parameter setting above, the standard genetic algorithm and the improved genetic algorithm in this paper were used for simulation verification with the optimization objective of minimizing the maximum completion time. The basic parameters of the algorithm were set as follows: initial population 100, crossover probability 0.8, mutation probability 0.1, and iteration number 200. The data of 15 runs are respectively shown in
Number of runs | Standard genetic algorithm/Improved genetic algorithm | |
---|---|---|
Optimal solution | Convergence generations | |
1 | 70.55/44.42 | 142/165 |
2 | 73.10/42.81 | 58/153 |
3 | 75.14/42.15 | 106/185 |
4 | 73.44/44.78 | 181/181 |
5 | 77.81/42.46 | 77/187 |
6 | 73.71/44.38 | 44/115 |
7 | 77.03/44.77 | 192/180 |
8 | 74.34/45.96 | 21/179 |
9 | 73.23/40.60 | 174/153 |
10 | 73.16/43.72 | 76/125 |
11 | 74.15/44.22 | 33/175 |
12 | 75.15/43.87 | 88/189 |
13 | 76.70/45.78 | 32/169 |
14 | 70.18/47.97 | 124/154 |
15 | 74.32/44.34 | 139/184 |
Algorithm name | The comparison of statistical data | |||||
---|---|---|---|---|---|---|
Minimum value of optimal solution | Maximum value of optimal solution | Average value of optimal solution | Minimum convergence generations | Maximum convergence generations | Average convergence generations | |
Standard genetic algorithm | 70.18 | 77.81 | 74.13 | 21 | 192 | 99.13 |
Improved genetic algorithm | 40.60 | 47.97 | 44.15 | 115 | 189 | 166.27 |
The above results show that the improved genetic algorithm designed in this paper can avoid the premature algorithm to a large extent when the dual-resource scheduling problem of flexible job shop based on segmented AGV is solved, and the quality of the solution is significantly better than that of the standard genetic algorithm.
Based on the extended case of MK04, the influence of the location and number of transfer stations on the scheduling results is studied in this section. Workshop layout as shown in
Serial number | Location of transfer station | Number of transfer station | Number of AGV | The maximum completion time |
---|---|---|---|---|
1 | None | 0 | 1 | 108.83 |
2 | Z23 | 1 | 2 | 102.54 |
3 | Z34 | 1 | 2 | 103.28 |
4 | Z45 | 1 | 2 | 97.96 |
5 | Z56 | 1 | 2 | 99.54 |
6 | Z67 | 1 | 2 | 101.39 |
7 | Z23, Z45 | 2 | 3 | 96.89 |
8 | Z23, Z56 | 2 | 3 | 100.72 |
9 | Z23, Z67 | 2 | 3 | 97.20 |
10 | Z34, Z56 | 2 | 3 | 99.81 |
11 | Z34, Z67 | 2 | 3 | 98.40 |
12 | Z45, Z67 | 2 | 3 | 99.54 |
13 | Z23, Z45, Z67 | 3 | 4 | 99.88 |
In the above cases, it can be seen from
Based on the traditional flexible job shop scheduling problem, this paper considers the workpiece transfer time and the task allocation of AGV. Aiming at the flexible job shop of segmented AGV, a mathematical model of machine tool and AGV dual resource scheduling is established to minimize the maximum completion time. An improved genetic algorithm is designed to solve the problem, and the task allocation and transfer time of AGV are taken into account when decoding. Finally, the superiority of the improved genetic algorithm in this paper is verified by solving the corresponding cases, and it is verified that the location and number of transfer stations have a greater impact on the scheduling results under the condition that the workshop layout and the processing orders remain unchanged. However, the segmented AGV transport system is mainly suitable for small and medium-sized processing workshops, which has certain limitations. Therefore, the flexible job shop scheduling problem with a more universal AGV transport system remains to be further studied.