Genetic algorithm by employing guided local search for multi-objective optimization problem

Abstract

The invention provides a genetic algorithm by employing guided local search for a multi-objective optimization problem. The algorithm is used for the field of flexible job-shop scheduling. A flexible job-shop scheduling problem belongs to an NP-Hard problem, optimization of multiple objectives often needs to be faced in real production, and the objectives are in interaction and conflict. The genetic algorithm aims at solving the problems of too fast convergence, insufficient population diversity and over-high calculation cost of enumerating all neighborhood solutions caused by continuous cross breeding of close relatives in a genetic operation in the genetic algorithm in the prior art. According to the algorithm, a procedure of calculating a crossover rate and a mutation rate before genetic crossover and mutation and a procedure of searching a movable process and a feasible position by using the guided local search are designed for these problems; and through introduction of the two procedures, the calculation cost is reduced while algorithm premature is avoided. The algorithm is high in practicability and can be well used for actual job-shop scheduling.

Description

[0001] Technical field [0002] The invention relates to the field of job shops, in particular to using an algorithm to solve a multi-objective flexible job shop scheduling problem. Background technique [0003] The flexible job shop scheduling problem is an extension of the classic job shop scheduling problem. Each process is allowed to be processed on a given set of equipment. Therefore, in the flexible job shop scheduling problem, in addition to determining the processing sequence of each process on each device, it is also necessary to allocate a suitable device for each process. The flexible job shop scheduling problem is an NP-Hard problem. In real production, it is often necessary to face multiple optimization goals, and each goal affects and conflicts with each other. Therefore, there is generally no single optimal solution for multi-objective problems that is best for all objectives. At present, many techniques have been used to solve the flexible job shop schedulin...

AI Technical Summary

Problems solved by technology

[0005] The goals of this algorithm are: first, to solve the problem of excessive convergence and insufficient population diversity caused by the continuous cross-breeding of close relatives in the process of genetic algorithm; second, for a given scheme of the flexible job shop problem, its neighborhood usually passes through Obtained by moving the process from one device to another device, but not all moves will improve the current solution; third. The calculation cost of enumerating all the neighborhood solutions is high; fourth. The random weighting method cannot Solve multi-objective problems well

Images