Please click "Follow" before reading the article, so that it is easy to discuss and share, and in order to return your support, I will update the quality content daily.
preface
Production scheduling is an important part of modern manufacturing system, efficient scheduling methods can improve industrial production efficiency, increase the economic profitability of enterprises, and improve customer satisfaction.
But the job shop scheduling problem (JSP) is also one of the most complex problems in production scheduling, while the flexible job shop scheduling problem (FJSP) is an extension of the JSP, which requires the allocation of the appropriate machine for each operation in addition to considering the order of operations.
Since FJSP is more in line with the reality of modern manufacturing enterprises, this problem has been extensively studied by many experts and scholars in the past few decades, and this problem is increasingly used in different environments, such as crane transportation, battery packaging and printing production.
Is there a way to solve the scheduling problem when working on the shop floor? Is the "gray wolf optimization algorithm" the solution?
Flexible job shop scheduling issues
The first scholars to propose the flexible job shop scheduling problem chose to use polynomial graph algorithms to solve this problem, and over time, other scholars have developed various solutions to this problem.
So far, the methods for solving FJSP can be divided into two broad categories: exact algorithms and approximate algorithms.
Precise algorithms (Lagrange relaxation, branching and binding algorithms, and mixed integer linear programming) have the advantage of finding the optimal solution for FJSP, but they are only effective for small-scale FJSP and the computation time required is unbearable once the size of the problem increases.
The second is a large category, which has received more attention in recent research because it can find better solutions in less time, and is currently an approximate algorithm that has been successfully applied to solve FJSP, such as gray wolf optimization algorithm (GWO), genetic algorithm (GA), particle swarm algorithm (PSO), ant colony algorithm (ACO), etc.
At the very beginning, the research on the meta-heuristic algorithm to solve FJSP mainly lies in proposing a new neighborhood structure and using tabu search or simulated annealing algorithm (SA), for which some scholars design a hierarchical algorithm based on tabu search to solve FJSP based on the characteristics of FJSP.
In order to minimize the maximum completion time, some scholars propose an improved SA to solve the problem, and some people also propose two neighborhood structures (Nopt1, Nopt2) and combine them with TS, which verifies the effectiveness of the proposed method.
Recent studies have shown that optimizing the goal of the problem by improving the neighborhood structure is an effective method, and a scholar in China has proposed a hybrid algorithm that incorporates an improved neighborhood structure.
He divided the neighborhood structure into two levels: the first level was used to move processes across machines, and the second level was used to move processes within the same machine.
However, with the expansion of the scale of FJSP, the method of improving the neighborhood structure only often lacks diversity in the solution process, which leads to falling into local optimum, so most researchers currently solve FJSP by mixing swarm intelligence algorithms with constraint rules for scheduling problems.
The former is used to enhance the diversity of the population, while the latter is used to utilize neighborhoods with more optimized solutions, and for GA, an academic proposed a hybrid algorithm (HA) that combines GA with tabu search (TS) to solve FJSP.
Find a solution
Although this scholar's research failed in the end, the parameter setting of GA in the method is of great significance for subsequent research, because a reasonable combination of parameters can better improve the performance of the algorithm.
On the basis of predecessors, a hybrid genetic algorithm (HGA) was proposed, and the parameters of GA were optimized by the Taguchi method.
At the same time, a self-learning genetic algorithm (SLGA) is proposed to solve FJSP and dynamically adjust its key parameters based on reinforcement learning (RL).
Later, someone designed an adaptive population nondominated ranking genetic algorithm III, which combines a dual control strategy with GA to solve FJSP considering energy consumption.
At the same time, for ACO, another group of scholars proposed a multi-objective FJSP hybrid ant colony algorithm based on three-dimensional separation graph model, in which the optimization goals are production span, production duration, average idle time and production cost.
An improved ant colony algorithm (IACO) has also been proposed to optimize the manufacturing span of FJSP and tested it with a real production example and two sets of well-known benchmark examples to verify its effectiveness, in order to solve FJSP in a dynamic environment.
Some scholars also choose to combine multi-agent system (MAS) negotiation with ACO, and introduce the characteristics of ACO into the negotiation mechanism to improve scheduling performance and solve the problem of flexible job shop scheduling of assembly operations.
Gray wolf optimization algorithm
The Gray Wolf Optimization (GWO) algorithm is a population-based evolutionary meta-heuristic proposed by an Australian scholar in 2014, originally used to solve continuous function optimization problems.
In GWO, the scholar simulated the hierarchical mechanism and hunting behavior of gray wolf populations in nature.
Compared with other meta-heuristic algorithms, the GWO algorithm has the advantages of simple structure, few control parameters, and can achieve local search and global search balance.
In recent years, it has been successfully applied to path planning, SVM model, image processing, power scheduling, signal processing and other fields, but the algorithm is rarely used in FJSP.
This is mainly due to the fact that algorithms are continuous and FJSP is a discrete problem, so it is important to consider how to match the algorithm to the problem.
At present, there are two mainstream solution methods, the first method adopts a transformation mechanism to convert a continuous single position vector and a discrete scheduling solution to and from each other, which has the advantage of implementing a simple, retained algorithm update iteration formula.
However, some scholars have proposed a whale optimization algorithm improved by the gray wolf optimization algorithm to solve the FJSP problem, where the ROV rule is used to transform the sequence of operations.
This move is like opening Pandora's box, and a large number of other algorithms have popped up at once, including one scholar who proposed a hybrid harmony search (HHS) algorithm and developed a transformation technique.
This algorithm solves problems such as machine allocation, velocity distribution, and sequence of operations by converting continuous harmonic vectors into discrete bidirectional quantity codes of FJSP.
However, these methods have certain limitations, such as missing some excellent solutions during the conversion process and wasting a lot of calculation time.
Discretization algorithms
However, in the second method, the discrete update operator aims to realize the correspondence between the algorithm and the problem, and for the multi-objective flexible job workshop scheduling problem, some scholars propose a hybrid discrete firefly algorithm (HDFA), which improves the search accuracy and information sharing ability of the algorithm through discretization.
Some scholars also proposed a discrete particle swarm optimization (DPSO) algorithm, and designed the discrete update process of the algorithm by using crossover and variational operators.
Finally, a large number of experimental results show that this algorithm is not an effective way to solve the problem, and a domestic scholar proposes a hybrid algorithm that combines chemical reaction algorithm and TS, and designs four basic operations to ensure the diversity of data.
After that, a discrete cat herd optimization algorithm is proposed to solve the low-carbon flexible job shop scheduling problem, which aims to minimize the sum of energy cost and delay cost, and designs a discrete form of finding and tracking patterns in the algorithm to fit the problem.
Ideal combination for workshop production
FJSP is an idealized combination optimization problem generated from actual shop floor production, originally FJSP is derived from JSP, where the project to be generated is uniformly defined as a job with one or more steps.
The equipment used to process jobs is uniformly defined as the machines in the process, and JSP has the constraint of job sequencing, that is, each job is processed on its corresponding machine according to a certain processing process until all jobs are processed.
Therefore, FJSP can be considered an extended version of JSP because it removes some machine constraints and the number of machines that can be selected for each operation is not limited to one.
Before addressing FJSP, there is one more important classification to clarify, which can be classified according to the number of computers that can be selected for operation: total FJSP (T-FJSP) and partial FJSP (P-FJSP).
As can be seen from the above, FJSP actually breaks through the singularity of the number of machines that can be selected for operation, and if all operations can be handled by any machine, this situation is defined as T-FJSP.
At the same time, if there are operations that cannot be handled on some computers, this situation can be classified as P-FJSP, which is more universal than T-FJSP, so we also focus more on P-FJSP.
Considering the dual-objective FJSP, the main purpose is to assign each job to the corresponding machine according to the processing constraints, and finally obtain a schedule that ensures the minimum manufacturing span and the minimum critical machine load.
The objective function can be represented by equations (1) and (2), but with some constraints, for better understanding, we give the symbols and variables mentioned in the following problem model, as well as some abbreviations that we commonly use.
Symbol definitions and abbreviations in articles
GWO is inspired by the habits of gray wolf packs, which live in groups of 5 to 12 wolves per pack, and the algorithm works by mimicking stratification and prey aggression within the pack.
The characteristics of GWO are described below, in the hierarchical stratification mechanism, all individuals in the group can be divided into four categories according to their status, α, β, δ, and omega wolves in order from top to bottom.
α is the first level, responsible for making decisions about group actions in a crowd.
The second level is β, which assists α wolves, and when α wolves die or grow old, β wolves are promoted to the status of α wolves.
δ wolves play the role of trainer for α wolves in the pack, responsible for strengthening the command of α wolves over the lower wolves.
The final level of the wolves pack is the Omega Wolf, who needs to follow the orders of the first three wolves to complete the tasks they need.
According to these, we can see that the gray wolf optimization algorithm actually has a very strong advantage, if the gray wolf algorithm is used in the mobilization of the workshop, on the one hand, there is no need to worry that the program is not dominant, because even if the α wolf falls, there will be a β wolf on top.
At the same time, because there are δ wolves to train α wolves, α wolves will not make mistakes in most cases, and even if they make mistakes, they will be corrected by δ wolves in time.
Although the gray wolf optimization algorithm is divided into four parts, the largest part of this is the omega wolf responsible for the actual work, so that it can be done without delaying the task that should be completed too much while constantly self-correcting.
From this point of view, although the gray wolf optimization algorithm is inspired by animals, it is very suitable for solving workshop scheduling problems.
conclusion
The gray wolf optimization algorithm is used to solve the FJSP, with the aim of minimizing the manufacturing span and key machine load, and the GWO algorithm has the advantages of few parameters and convenient implementation.
But it may end prematurely, so we design several improvement strategies to enhance the search ability of the FJSP algorithm, and verify the effectiveness of the algorithm by comparing experiments with recent studies, and the experimental and comparative results show that the algorithm can get most problems.
If you like my article, please click "Follow", welcome to discuss with me in the comment area, thank you.
END