Some Intelligent Algorithms For Permutation Flow Shop Scheduling Problems

Permutation flow shop scheduling problem is a classical combinatorial optimization. In recent ten years, with the development of intelligent optimization algorithm, It once again become the focus of research. In this thesis, to minimize the makespan in permutation flowshop scheduling problems, some intelligent optimization algorithms are presented.The main works can be summarized as follows:1、(1) To minimize the makespan in permutation flowshop scheduling problems, an ant colony optimization algorithm is presented. The key point of the algorithm is to integrate NEH heuristics with ant colony optimization algorithm. The algorithm is tested on benchmarks. Experimental results show the algorithm has better performance.(2) To minimize the makespan in permutation flowshop scheduling problems, a multi-construction ant colony optimization algorithm is proposed. In the algorithm, solutions are constructed through two modes, which is based on NEH heuristics and Rajendran heuristics, respectively. Then, the proportion of construction modes is adjusted adaptively accord to quality of solutions constructed. Experimental results based on benchmarks show the algorithm has better perform.2、(1) To minimize the makespan in permutation flowshop scheduling problems, a particle swarm optimization algorithm is proposed. First, each sequence of jobs is generated by greedy randomized adaptive search based on heuristics. Second, the initial best position of each particle is no longer the initial position of each particle, which is converted from above sequence of jobs through a novel method. A local search is added to improve the performance. Experimental results based on benchmarks show the algorithm has better performance.(2) To minimize the makespan in permutation flowshop scheduling problem, a hybrid electromagnetism-based algorithm is proposed. First, the part of initial solutions generated randomly is changed into high quality solutions, through the job sequences generated by greedy randomized adaptive search based on heuristics. A local search is added to improve the performance. Experimental results based on benchmarks show the algorithm is effective.3、(1) To minimize the makespan in permutation flowshop scheduling problems, a hybrid estimation of distribution algorithm is presented. First, the initial distribution of probability is generated from a novel method based on NEH heuristics. Second, the solu-tions are sampled from the distribution of probability, and local search is applied to the best one. Third, a new distribution of probability is estimated from the previous better individuals through a special method. Then, new solutions are sampled from the esti-mated distribution. The presented algorithm is tested on scheduling problem benchmarks. Experimental results show the algorithm has better performance.(2) To minimize the total flow time in permutation flowshop scheduling problems, a hybrid estimation of distribution algorithm is presented. First, the initial distribution of probability is generated from a novel method based on FL heuristics. Second, the solutions are sampled from the distribution of probability, and local search is applied to the best one. Third, a new distribution of probability is estimated from the previous better individuals through a special method. Then, new solutions are sampled from the estimated distribu-tion. The presented algorithm is tested on scheduling problem benchmarks. Experimental results show the algorithm is effective.4、To minimize the makespan in permutation flowshop scheduling problems, a hybrid discrete artificial bee colony algorithm is presented. In the algorithm, the initial popu-lation with certain quality and diversity is generated from greedy randomized adaptive search based on NEH heuristics. Second, the discrete operators and algorithm are adopted to generate new solutions for the employed bees, onlookers and scouts. Moreover, local search is applied to the best one. The presented algorithm is tested on scheduling problem benchmarks. Experimental results show the algorithm has better performance.5、An algorithm based on genetic algorithm is proposed for permutation flowshop scheduling problem. In the algorithm, initial population is composed of two parts, one is generated randomly, the other is generated by greedy randomized adaptive search based on heuristics. Longest common sequence crossover is adopted. Local search is added to improve the performance. Computational experimental results based on benchmarks show it’s effective.6、To solve sudoku puzzles, an algorithm based on genetic algorithm is presented. First, a rule is proposed to generate initial population with high quality and diversity. Then, the special designs are made for encoding and crossover and mutation. Then, local search is added to improve the performance. The experimental results show it is effective for all difficulty levels sudoku puzzles.7、 To solve the most popular Rubik’s Cube, an algorithm based on genetic algorithm is presented. In the algorithm, initial population is generate by greedy randomized adap-tive search, the special designs are made for crossover、mutation and local search. The experimental results show it is effective.