3 proposed a new priority order combined with a simple tie-breaking method named NEHNM. In view of the superiority of NEH algorithm in solving FSP and the deficiency of heuristic algorithm, researchers proposed many extensions of the NEH. Studies show that NEH 2 proposed by Nawaz, Enscore and Ham in 1983 is the best heuristic algorithm to solve this problem 3, 4, 5. These algorithms generate solution based on problem-specific experience and construction rules, which may not get the optimal operation sequence, but can guarantee the local optimality of the processing sequence to a certain extent. Due to the limitation of precise methods in such large-scale problems, a large number of heuristic methods have been widely used, e.g., Gupta, Johnson, Palmer, NEH, RA. The flow manufacturing model rises and the process of products becomes more complicated in sync with the wide application of automation in industry. Most of the early researches on scheduling problems use mathematical methods such as integer programming, branch and bound, etc., focusing on theory and trying to get the exact optimal solution. Therefore, the study of this problem has important theoretical significance and engineering value, and it is also the most widely studied type of typical scheduling problem. It belongs to NP-hard problem category 1. The terms “machine”, “job” and “operation” in scheduling problems are abstract concepts that can represent a wide range of real objects.įlow shop scheduling problem (FSP), which is a typical combinatorial optimization problem and exists widely in production system and service system. Resources are usually called machines, and tasks are called jobs, and sometimes jobs may be composed of several basic tasks linked by sequence constraints, called operations. Early work in the field of scheduling was driven by manufacturing, and although considerable progress has been made on scheduling problems in many non-manufacturing fields, manufacturing terminology is still use. Scheduling is a decision-making process in which re-sources are allocated to different tasks under certain constraints. The results of compared with NEH heuristic algorithm and standard genetic algorithm (SGA) evolutionary metaheuristic algorithm after testing on 101 FSP benchmark instances show that the solution accuracy has been significantly improved. A concrete application scheme of the proposed method is introduced.

It is strengthened in the following three aspects: NEH algorithm is used to optimize the initial population, three crossover operators are used to enhance the genetic efficiency, and the niche mechanism is used to control the population distribution. In order to improve the solving accuracy of flow shop scheduling problems, a computational efficient optimization approach combining NEH and niche genetic algorithm (NEH-NGA) is developed. Evolutionary algorithms make up for this defect in small-scale problems, but the solution performance will deteriorate with the expansion of the problem scale and there will be premature problems. Although heuristic algorithms have high solving speed, the solution quality is not good. Heuristic algorithms and evolutionary metaheuristic algorithms are commonly used to solve this kind of problem. Flow shop scheduling problems are NP-hard problems.

Minimizing permutations