US 2025/0147489 A1 · DUAL-EFFECT SCHEDULING METHOD FOR HETEROGENEOUS ROBOTS IN FLEXIBLE JOB SHOP

Abstract

The present disclosure belongs to the field of flexible job shop scheduling, and relates to a dual-effect scheduling method for heterogeneous robots in a flexible job shop. In a case of strong coupling of processing and transferring, this method comprehensively considers such constraints on selection of flexible manufacturing cells (FMCs), transferring time by automatic guided vehicles (AGVs) and processing resource waste, and improves encoding schemes and genetic operators with order completion time and minimization of resource consumption as evaluation criteria. Additionally, this method can fully apply environmental characteristics of job shop to scheduling design, and automatically design more precise scheduling schemes, overcoming the deficiencies of slow response and prone to local optimal solutions existing in conventional scheduling schemes, and ensuring efficient and green operation.

A dual-effect scheduling method for heterogeneous robots in a flexible job shop, comprising the following steps:

step 1:
encoding each individual in three layers using a symbolic coding method, the encoding of each individual comprising three layers, namely, workpiece procedure-based encoding, processing robot-based encoding, and automated guided vehicle (AGV)-based encoding,
step 2:
acquiring processing robot information, AGV information and to-be-processed workpiece information, integrating two objective functions for respectively minimizing order completion time and minimizing resource consumption into a single composite function using a weighted optimization method, and designing a fitness function,
step 3:
calculating fitness of each individual encoded in step 1 using the fitness function designed in step 2, and selecting individuals for the next generation according to fitness values using a roulette wheel selection method with an elitism strategy,
step 4:
performing crossover operation on the workpiece procedure-based encoding and the AGV-based encoding of the individual in step 1 using precedence operation crossover (POX), and performing two-point crossover operation on the processing robot-based encoding of the individual,
step 5:
performing swap mutation operation on the workpiece procedure-based encoding and the AGV-based encoding of the individual in step 1, and performing uniform mutation operation on the processing robot-based encoding of the individual, and
step 6:
together forming the individual selected in step 3, the individual after the crossover operation in step 4, and the individual after the mutation operation in step 5 into a new population for the next generation, repeating steps 3 to 5 for individuals in the new population for the next generation to obtain optimal scheduling schemes and fitness values, and selecting a suitable scheduling scheme according to the demand preferences to perform dual-effect scheduling on heterogeneous robots in a flexible job shop, wherein
in step 1, the first layer of encoding is based on workpiece procedure, for clarifying the order of various workpieces and various procedures in a processing scheme;
each gene of the individual represents a specific procedure of a specific workpiece;
various procedures of a workpiece are represented by the order in which the workpiece appears in the individual;
and the nth presence of a specific workpiece in the individual represents the nth procedure of the specific workpiece;
the second layer of encoding is based on processing robot, for clarifying the order of selected processing robots corresponding to various procedures of workpieces in the processing scheme;
each gene of the individual represents a corresponding processing robot selected for a specific procedure of a specific workpiece;
and the order of genes follows the order of processing workpiece numbers and the order of procedure numbers of a specific workpiece;
and
the third layer of encoding is based on AGV, for clarifying the order of AGVs corresponding to various workpiece procedures in the processing scheme;
each gene of the individual represents an AGV number corresponding to a specific procedure of transferring a specific workpiece;
and the order of genes corresponds to the order of the workpiece procedure-based encoding;
in step 2, the processing robot information comprises:
the number of processing robots, the process processing capability of processing robots, and fixed-point positions of processing robots;
the AGV information comprises:
the number of AGVs, the running speed of AGVs, and initial positions of AGVs;
and the to-be-processed workpiece information comprises:
the number of workpieces to be processed, the number of procedures of the workpieces to be processed, and available processing robots and processing time for each procedure;
and the fitness function is defined as:
F
⁡
(
k
)
=
ω
×
f
1
⁢
m
⁢
ax
-
f
1
(
k
)
f
1
⁢
m
⁢
ax
-
f
1
⁢
m
⁢
i
⁢
n
+
(
1
-
ω
)
⁢
f
2
⁢
m
⁢
ax
-
f
2
(
k
)
f
2
⁢
m
⁢
ax
-
f
2
⁢
m
⁢
i
⁢
n
,
(
k
=
1
,
2
,
…
,
N
)
where F(k) is a fitness value of a kth individual;
ω is a weight coefficient for completion time, ranging from [0,1], and the allocation of weight is determined by a decision-maker of a job shop;
in a case that 0.6≤ω≤1, the job shop operates in an efficient processing mode;
in a case that 0.4≤ω≤0.6, the job shop operates in a comprehensive processing mode;
and in a case that 0.2≤ω≤0.4, the job shop operates in a green processing mode;
f1max is a maximum order completion time in a job shop of a current population;
f1(k) is an order completion time in a job shop of the kth individual;
f1min is a minimum order completion time in the job shop of the current population;
f2max is a maximum energy consumption of the current population;
f2(k) is energy consumption of the kth individual;
f2min is a minimum energy consumption of the current population;
and N is the total number of individuals in the current population;
in step 3, individuals with the highest fitness values in the current population are elite individuals;
the first quarter of individuals with the highest fitness values in the current population are kept from undergoing the roulette wheel selection, and the remaining three-quarters undergo the roulette wheel selection, crossover, and mutation to generate a new generation of population;
and if a fitness value of an optimal individual in the new generation of population is better than that of a reserved parent, it indicates that the population has been optimized, and the worst individual in offspring is replaced with the reserved elite individual;
in step 4, a method for performing crossover operation on the workpiece procedure-based encoding of the individual using POX is as follows:
randomly dividing all workpieces into two sets Q1 and Q2;
copying workpieces of parent P1 that are contained in Q1 to corresponding positions in an offspring individual C1, copying workpieces of parent P2 that are contained in Q2 to corresponding positions in an offspring individual C2, and fixing the position of each gene in the individual;
and copying workpieces of the parent P2 that are contained in Q2 to corresponding positions in the offspring individual C1, and copying workpieces of the parent P1 that are contained in Q1 to corresponding positions in the offspring individual C2, and keeping the order of genes to obtain two offspring individuals C1 and C2 after crossover;
in step 4, a method for performing crossover operation on the AGV-based encoding of the individual using POX is as follows:
randomly dividing all AGVs into two sets Q1 and Q2;
copying workpieces of parent P1 that are contained in Q1 to corresponding positions in an offspring individual C1, copying workpieces of parent P2 that are contained in Q2 to corresponding positions in an offspring individual C2, and fixing the position of each gene in the individual;
and copying workpieces of the parent P2 that are contained in Q2 to corresponding positions of the offspring individual C1, and copying workpieces of the parent P1 that are contained in Q1 to corresponding positions of the offspring individual C2, keeping the order of genes to obtain two offspring individuals C1 and C2 after crossover;
in step 4, a method for performing two-point crossover operation on the processing robot-based encoding of the individual is as follows:
selecting two different points p1 and p2 as crossover points, and swapping genes g1 and g2 in p1 and p2 of two individuals, respectively;
in step 5:
a method for performing swap mutation operation on the workpiece procedure-based encoding of the individual is as follows:
selecting two different random numbers within the length of two procedures, and swapping genes of the two procedures;
a method for performing swap mutation operation on the AGV-based encoding is as follows:
selecting two different random numbers within the length of two AGVs, and swapping genes of the two AGVs;
and
a method for performing uniform mutation operation on the processing robot-based encoding of the individual is as follows:
randomly selecting a procedure, directly returning without changing the gene if only one machine is selectable for the procedure, otherwise, randomly generating a serial number different from the currently selected machine within a selectable machine set of the procedure, and performing swap;
and
in step 6, a suitable scheduling scheme is selected according to demand preferences, the demand preference referring to the balance between the two objectives of order completion time and energy consumption, a desired scheme is selected and implemented, and a method for obtaining the optimal scheduling scheme is as follows:
gradually iterating, and obtaining the optimal scheduling scheme in a case that the change in fitness values is less than a set threshold or the number of generations is greater than the set number of iterations.

144 more elements

Dual-effect scheduling method for heterogeneous robots in flexible job shop

Life of this patent

Dual-effect scheduling method for heterogeneous robots in flexible job shop

Life of this patent

Abstract

Claims1