Second type computer assembly line balancing optimization method based on migration genetic algorithm

Patent metadata

Field	Value
Publication number	US-12518232-B2
Application number	US-202117912807-A
Country	US
Kind code	B2
Filing date	Dec 3, 2021
Priority date	Nov 18, 2021
Publication date	Jan 6, 2026
Grant date	Jan 6, 2026

Abstract

A second type computer assembly line balancing optimization method based on a migration genetic algorithm, and related to the technical field of assembly line balancing. The method uses assembly experience of similar assembly lines, the feasible solution set of the known assembly lines is transferred to the initial solution set of the assembly line balancing problem to be optimized, due to the migration of high-quality feasible solutions. The method can effectively reduce the sensitivity of the algorithm performance to the initial value and parameters, and improve the lower limit of the local optimal feasible solution of the heuristic algorithm to solve the assembly line balancing problem.

First claim

What is claimed is:

1 . A second type computer assembly line balancing optimization method based on a migration genetic algorithm, comprising the following steps:
Step 1: acquiring data of a production line assembly process of a type-A computer and a type-B computer, and expressing data of operation sequence, standard operation time and operation interval in a matrix form; Step 2: according to a matrix branch expressing the operation sequence of the assembly process of the type-A computer, constructing a priority relationship matrix Matrix of the assembly process of the type-A computer; Step 3: according to the priority relationship matrix Matrix of the assembly process of the type-A computer and the operation interval expressed in the matrix form, initializing the population of the genetic algorithm, initializing relevant parameters of the genetic algorithm, wherein each chromosome in an initial population obtained by the initialization corresponds to one feasible solution to an assembly line balancing problem of the type-A computer, and the relevant parameters of the genetic algorithm comprise number of the initial populations, population size, number of exchange genes, crossover probability of the populations, and mutation probability of the populations; Step 4: reproducing the initial populations, and searching and storing high-quality feasible solutions in the populations in the process of population reproduction, wherein all of the high-quality feasible solutions form an external solution set of the assembly line balancing problem of the type-A computer; Step 5: splitting or merging assembly operation units of the type-B computer, making corresponding processing to assembly operation units of the type-A computer, to obtain new operation sequence and operation interval of the assembly process of the type-B computer, and after such processing, adjusting the external solution set of the assembly line balancing problem of the type-A computer, so that the adjusted external solution set meets the technological requirements of the assembly line of the type-B computer, including the operation sequence and the operation interval of the assembly line of the type-B computer; Step 6: calculating a similarity of the assembly process of the type-A computer and the type-B computer by comprehensively considering three factors of the standard operation time, the operation sequence and the operation interval; Step 7: calculating a value of a fitness function of each chromosome in the external solution set obtained in the Step 5, selecting W chromosomes with the largest values of the fitness function from the external solution set, and forming a high-quality feasible solution set to an assembly line balancing problem of the type-B computer, wherein W is determined according to the similarity of the assembly process of the type-A computer and the type-B computer calculated in the Step 6; Step 8: initializing U chromosomes according to the new operation sequence and operation interval of the assembly process of the type-B computer, and combining the high-quality feasible solution set of the assembly line balancing problem of the type-B computer with the U chromosomes to form an initial population of the assembly line balancing problem of the type-B computer, wherein each chromosome in the initial population corresponds to one feasible solution of the assembly line balancing problem of the type-B computer; and Step 9: performing a preset number of reproduction operations on the initial population of the assembly line balancing problem of the type-B computer, and selecting preset Q feasible solutions with the largest values of the fitness function in each population reproduction process to optimize the feasible solution of the assembly line balancing problem of the type-B computer by replacing the Q feasible solutions with the smallest values of the fitness function in the next reproduction population so as to obtain the optimal solution set of the assembly line balancing problem of the type-B computer.

2 . The second type computer assembly line balancing optimization method according to claim 1 , wherein the data of the production line assembly process in the Step 1 comprises number of assembly line workstations, the operation sequence, serial number of the operation units, the standard operation time, and the operation interval.

3 . The second type computer assembly line balancing optimization method according to claim 1 , wherein in the Step 1, when the operation sequence is expressed in the matrix form, each operation unit and an immediate predecessor operation thereof are arranged in pairs in a matrix to obtain the matrix branch.

4 . The second type computer assembly line balancing optimization method according to claim 1 , wherein a method for establishing the priority relationship matrix Matrix of the assembly process of the type-A computer is as follows: if the operation unit i is the immediate predecessor operation of the operation unit j in the matrix branch, setting the i th row and the J th column in the matrix Matrix as 1, or else, setting the values as 0.

5 . The second type computer assembly line balancing optimization method according to claim 1 , wherein a method for initializing the population of the genetic algorithm according to the priority relationship matrix Matrix of the assembly process of the type-A computer and the operation interval expressed in the matrix form defined in the Step 3, comprises the following steps:
Step 3-2: initializing the population of the genetic algorithm by using the operation sequence and the operation interval as constraints to ensure that each chromosome corresponds to one feasible solution of the assembly line balancing problem of the type-A computer; Step 3-2-1: taking the total number of the operation units in the assembly process of the type-A computer as a length N of the chromosomes, and executing the Step 3-2-2 from chromosome counting t=1; Step 3-2-2: finding the operation units of which there is no immediate predecessor operation or of which the immediate predecessor operation is assigned to the corresponding chromosomes, and adding the operation units to an assignable operation unit set S; Step 3-2-3: calculating difference between an upper limit high-level of the operation interval corresponding to each operation unit in the assignable operation unit set S and a first gene position n of a currently unassigned operation unit, to obtain a difference set; Step 3-2-4: sorting each difference in the difference set in an ascending order, selecting the operation unit i corresponding to the difference at the first position of the order and assigning the operation unit i to a position of the n th gene of the chromosome, deleting the operation unit i from the operation unit set S, at the same time, updating the i th row of elements of the corresponding columns of all immediate successor operations of the operation unit i in the priority relationship matrix as 0, and making n=n+1; Step 3-2-5: judging whether n≤N or not, if yes, executing the Step 3-2-2, or else, executing Step 3-2-6; Step 3-2-6: making t=t+1, judging whether t≤Z or not, wherein Z is the population size, if yes, making n=1 and executing the Step 3-2-2, or else, executing Step 3-3; and Step 3-3: searching a minimum bottleneck time in an assignment order of the operation units in each chromosome, and according to the minimum bottleneck time, assigning all of the operation units assigned in each chromosome to a given m workstations according to the positions of respective chromosome genes, so that the feasible solution of the assembly line balancing problem of the type-A computer, corresponding to each chromosome, is obtained.

6 . The second type computer assembly line balancing optimi

Assignees

• Univ Northeastern

Inventors

• Gao Hongrui
• Xue Feng
• Zhang Yingwei
• Feng Lin
• Zhang Shengyang
• Li Zubian

Classifications

• G06N3/126

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• G06F2111/04

  Constraint-based CAD · CPC title

• G06Q10/06375 Primary

  Prediction of business process outcome or impact based on a proposed change · CPC title

• G06F30/27 Primary

  using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model · CPC title