1. Introduction

Hybrid flow-shop scheduling problem (HFSP) was first proposed based on the background of petrochemical industry [1]. HFSP has a strong engineering background, scheduling problems in mass production, manufacturing, assembly, transportation, synthesis, as well as Internet services, container handling and other issues can all be attributed to HFSP. Therefore, it is of great theoretical significance and practical value to study the algorithm of HFSP.

Therefore, this paper analyzes the Chinese and foreign literature of HFSP in recent years, and divides it into precise algorithm, heuristic algorithm, meta-heuristic algorithm and learning algorithm according to the algorithm[2]. In addition, considering the actual processing and production technology and the complex and changeable processing environment, more extended applications of the algorithm are also within the scope of research. Finally, based on the current situation in the current environment, combined with cutting-edge theories, the problems of algorithm are prospected.

2. Solving Algorithm of HFSP

The complexity, scheduling objectives and solving methods of HFSP, Li et al. pointed out that most HFSPs are non-deterministic polynomial (NP) problems [1]. In response to this problem, the early small-scale scheduling problem mainly adopts the exact algorithm , but in the large-scale scheduling problem, the deterministic method takes too long to solve [3]. Therefore, many heuristic algorithms and meta-heuristic algorithms have been proposed and widely used. In recent years, a considerable number of research works have tried to combine learning methods with traditional algorithms to integrate the generalization of learning methods and the search effectiveness of traditional algorithms, thereby improving the speed and accuracy of solutions.

2.1. .Exact algorithm

When the scale of the problem to be solved is small, the exact algorithm uses enumeration, iteration and other methods to find the optimal solution in feasible time [3]. At the same time, the exact algorithm can not only solve the feasible solution of the problem, but also can be used as the initial solution of a feasible algorithm, such as the initial solution of the heuristic algorithm. However, from the two-stage HFSP derivative at the beginning of the problem to the current k-stage HFSP, the complex constraints between stages and machines make it more and more difficult to solve the exact algorithm. As the dimension increases, the search space grows exponentially, it is difficult to find the optimal solution in a short time[4].

The complexity of k-stage HFSP under multiple constraints leads to a decrease in the solution speed of the exact algorithm. Therefore, the core idea of the algorithm design is changed to incomplete enumeration, and the algorithm framework is a search tree structure. Furthermore, a branch-and-bound method is proposed to obtain the optimal linear relaxation solution for the subproblems in a single stage. Therefore, the branch and bound method limits the lower limit of the boundary by dividing the space, which avoids part of the unnecessary search process and reduces the complexity of the operation.

The commonly used precise algorithms are based on the branch and bound method and carry out related expansion and extension. The main algorithms include dynamic programming method, constraint programming method, A* family algorithm, etc.

2.2.Heuristic algorithm

Most of the flow shop scheduling problems are NP-hard problems, and precise algorithms have great limitations. Therefore, the research focus is turned to approximate or heuristic methods that can obtain suboptimal solutions in limited time, which are widely used to solve practical problems with large problem scales. In the limited computing time, the heuristic algorithm can quickly find a solution that meets the requirements in a way that greatly reduces the number of computations. Based on the above theories, the current heuristic rules are divided into three categories: based on limited dispatch rules (Priority Dispatch Rules, PDR), based on Insertion Methods (Insertion Methods, IM) and based on Shifting Bottleneck Procedure (SBP) [1]. The heuristic rules of these methods are often complex, but they can greatly reduce the number of attempts and quickly obtain sub-optimal solutions to the problem.

Based on the above theory, heuristics usually take the form of dispatching one or more rules, which usually consist of rules of thumb or precedence rules. In the actual production scheduling process, by restricting the dispatching rules, the optimization of workpiece processing sequence, machine selection, start-up time, etc. is realized, and local optimal solutions can be found quickly. Jia et al. studied the problem of minimizing the maximum completion time of batch processing of multiple parallel machines, considering the machine capacity and workpiece size, and proposed the FDD rule and the MMAS algorithm to solve it [5]. Li et al. [6]studied HFSP, in which in a certain stage in the batch processing of parallel machines, the objective function is to minimize the maximum completion time , and for this purpose, a HSGA combining machine sorting rules and batch production rules was proposed.

From the above theory and research, it is not difficult to find that the heuristic algorithm can solve the hybrid workshop scheduling problem in the medium range in a relatively short time. However, the setting of actual goals is often complicated, and even includes some complex expansion problems. Due to the constraints of dispatch rules, the algorithm will fall into a local optimum, and the quality of the solution cannot be guaranteed.

2.2. Meta-heuristics algorithm

Algorithm based on process determination, the meta-heuristic algorithm integrates " random factors" into the solution process. Because of its simple implementation and fast convergence speed, meta-heuristic algorithm has been widely used in the solution of HFSP. The algorithm is inspired by various behaviors of nature and developed by humans, and it is an algorithm for humans to imitate the survival of the fittest mechanism in nature to better solve the scheduling problem of mixed flow workshops. Meta-heuristic algorithm has significant biological characteristics, and has the characteristics of high algorithm efficiency, not easy to fall into local optimum, and strong adaptability.

At present, there are more and more meta-heuristic algorithms that simulate the evolution of biological populations, such as genetic algorithm, migratory bird migration algorithm, and empire competition algorithm. The genetic algorithm studied by Mu Jianhui et al. [7]is a meta-heuristic algorithm that simulates the evolutionary characteristics of the chromosomes of biological populations in nature. Zhang Biao's paper[8], the migratory bird migration algorithm is used to simulate the iterative law that migratory birds are flying with the strongest head geese and alternately updated left and right. The empire competition algorithm studied by Tao Xinrui et al. [9]draws on the competition, occupation, and competition among imperialist countries in human history. The process of annexing colonies, etc.

In order to solve the workshop scheduling problem more efficiently, many scholars use two or more meta-heuristic algorithms in combination to achieve the effect of "1 + 1 > 2". For example, Wang Shengyao et al. [10]proposed a distribution estimation algorithm based on the update probability of the dominant population to solve the mixed flow shop scheduling problem; Jia Zhaohong et al. [11]proposed an optimal solution based on the dual-objective collaboration of ant colonies; Xuan Hua et al [12]proposed an adaptive improved genetic algorithm to solve the HFSP problem ; CAI et al. [13]proposed a hybrid leapfrog algorithm using global search and dynamic multi-neighbor search for distributed HFSP, which greatly improved the Search quality; ÖZTOP H [14] proposed a dual-objective mixed integer linear programming (MILP) model and a dual-objective constraint programming (CP) model for HFSP , and designed seven meta-heuristic algorithms for dual objectives.

2.3. Learning algorithm

Above three traditional algorithms, whether they are accurate algorithms represented by branch and bound, heuristic algorithms or meta-heuristic algorithms, all have common shortcomings: they rely heavily on expert knowledge and pilot experience, and their generalization is relatively insufficient. The search efficiency is not high [15]. Therefore, in order to make up for the related defects, many scholars have begun to try to introduce the learning mechanism into the traditional algorithm [1]. Combined with the strong generalization of the learning mechanism, the design of the search framework and search operators is simplified, and the dependence on expert experience is reduced. so as to enhance the search efficiency and improve the solution quality.

In recent years, with the rapid development of computer science, a considerable number of scholars have devoted themselves to the study of combining learning methods with traditional algorithms to form new algorithms, which have both the generalization of reinforcement learning and the effectiveness of traditional algorithms. For example, Ni Fei [15]designed an algorithm model that combines learning mechanism and reward mechanism, so that the algorithm can be adjusted for different instances; Gu Wenbin et al. [16]used the whale optimization algorithm for the HFSP problem of feature selection ability and prediction accuracy . As the basis, combined with probabilistic neural network, the optimization algorithm WOA-PNN was proposed; Sebastian Lang et al. [17]studied the application of neuroevolutionary broadening topology (NEAT) to HFSP problem, and proposed artificial neural network (ANN), through 14 kinds of Different experiments are conducted to evaluate how ANN is applied to HFSP and compared with the traditional algorithm, it is concluded that the search efficiency of the algorithm is much better than the traditional algorithm.

3. Practical application of HFSP algorithm

With the increase of customer's personalized product demand, various new requirements are also put forward to the manufacturing workshop, so many new production modes, constraint rules, etc. have also been introduced into the research of HFSP. This paper introduces green production (energy consumption constraints) and resource constraints from the perspective of actual production.

3.1. Green production (energy consumption constraint)

Traditional workshop scheduling only considers constraints such as production process and assembly line machines, and seldom pays attention to constraints that are closely related to actual needs such as energy consumption, load conditions, and environmental pollution. For the energy consumption problem, DAYONG HAN [18]et al. An integer linear programming model was established for this problem to coordinate the time correlation, and then the optimization algorithm for migratory birds was improved, and the energy consumption was reduced by 1.21% under the same conditions. For environmental factors, Zhong Yuchong [19]took into account the economic index of the maximum completion time (Make-span) and the total carbon emission (TCE) of environmental factor indicators, a hybrid cuckoo algorithm (HCS) is designed.

Although there are not many studies on the green scheduling problem of complex workshops, with the globalization of manufacturing, the green production algorithm based on the HFSP problem has broad prospects. Therefore, the modeling of green-produced HFSP and related research on solving algorithms have strong practical significance.

3.2..Resource constraints

Due to the lack of relevant production materials in some areas in different regions, the fluctuation of the supply of imported raw materials, the reduction of workers due to the aging of the population, etc., there are a lot of resource constraints in actual industrial production. KAIFENG GENG et al. [20]proposed an Improved Multi-Objective Memetic Algorithm (IMOMA) for workers' dominance in the production process, with the goal of minimizing the operator's maximum completion time, total delay time and workload balance. to solve the HFSP problem; in the case of limited human resources, Costa et al. [21]established a mixed integer model and proposed a new discrete mixed backtracking search optimization algorithm. For the shortage of raw materials, when Sun Rui [22]established the algorithm model, the method of penalty coefficient was used to associate a single HFSP algorithm with the raw materials in stock, and the obtained solution could balance the relationship between time and raw materials.

4. Future outlook

Looking at the research literature of HFSP over the years, many achievements have been made in the research of mixed flow shop scheduling problem, but with the rapid development of production technology and manufacturing industry, there is still a certain gap between theoretical research and actual production . This paper discusses the future direction of the HFSP problem from three aspects: problem, algorithm, and practical application.

4.1. Problem aspect

At present, most algorithms only consider the time constraints in the mixed flow workshop, but the production situation in the actual production workshop must be more complicated, and other various conditions require constraints. Therefore, the mixed flow shop problem based on two or more constraints is one of the directions of future research.

The existing HFSP is a full connection in an ideal state, but in practice, there are redundant connections in this problem, and the parallel machines at each stage also have different working conditions. Therefore, it is also one of the future research directions to study the connection mode and machine configuration strategy of adjacent stages of HFSP.

4.2. Algorithmic aspect

algorithm combines traditional mathematical methods and modern meta - heuristic algorithms and shows great advantages in solving speed and solving accuracy. Search capabilities, etc, still need further exploration.

The research on solving HFSP by learning algorithm is still in its infancy, and there are few research literatures. However, learning algorithms stand out among many algorithms with their strong self-learning and adaptive capabilities. Therefore, how to combine traditional algorithms with deep learning algorithms will also be one of the directions of future research.

4.3. Application aspect

With the popularization of digital workshops, the combination of hybrid flow workshops and intelligent manufacturing systems will also be one of the future research directions. Taking the combination of digital twin workshop and mixed flow workshop as an example [1], the digital twin workshop realizes the real-time connection between the real workshop and the virtual workshop, while the mixed flow workshop realizes real-time scheduling and control, thus meeting the requirements of today's society for intelligent manufacturing.