Research On Heuristic Algorithms And Their Applications In The Permutation Flowshop Sequencing Problem

For NP-complete problems, global optimal solutions can not be found at a reasonable cost. These problems are usually solved by heuristic algorithms with the objective of finding a solution as good as possible in an acceptable time. Shop scheduling problems have many features, such as constraint, non-linear, large-scale, multi-objective, and usually NP-complete. Solving these problems often encounters combinatorial explosion. Traditional methods, such as linear programming and branch&bound, are not very useful to solve shop scheduling problems with a little large scale, and these problems are usually solved by heuristic algorithms.Shop scheduling is an interdisciplinary field and attracts many researchers from operations research, mathematics, management science, decision science, automation science and computer science, etc., and at the same time, shop scheduling and control are key techniques to realize high efficiency, high flexibility and high reliability of producing. The research and application of effective and practical scheduling methods and optimizing techniques have become the basis of advanced manufacturing technology. So, the research of heuristics for solving shop scheduling has practical sense.The application of heuristic algorithm in the permutation Howshop sequencing problem (a classic problem of shop scheduling) is studied in this paper, and the main results are as follows:1. As for the problem with makespan criterion, an improved constructive heuristic NEH-D is proposed, which is based on the famous NEH heuristic. The NEH-D heuristic improves the NEH in two aspects: firstly, the jobs are sorted by a more effective priority rule, in which the sum of processing times of a, job is considered, in addition to the standard deviation of these processing times; secondly, a tie-breaking strategy is presented in the constructing phase. The priority rule is beneficial to the improvement, while the strategy is the key point to the improvement. Experimental results show that the performance of the NEH-D is not only statistically significantly better than that of the NEH, but also statistically significantly better than that of the NEHKK and NEHKK1 heuristics proposed recently;2. As for the problem with makespan criterion, the effects of several components in tabu search algorithm are studied. The results show that the proposed search strategy has obvious effect on the performance of the algorithm, while the proposed tabu list structure, tabu status and different initial solution have little effect on it;3. As for the problem with total flowtime criterion, an iterated local search algorithm is proposed. The initial solution has little effect on the algorithm: when the algorithm is trapped into a local optimum, it needs to perturb the best-so-far solution and continue the searching process, while the perturbation strength has significant effect on the performance of the algorithm. Comparisons are carried out and the results show that the performance of the proposed ILS is statistically significantly better than that of those existing algorithms. It improves the best known solutions for 47 out of 90 benchmarks;4. A multi-objective local search algorithm (MOLS) is proposed for solving the problem with bi-objectives of makespan and total flowtime. The MOLS is to start from two initial solutions, which are constructed by existing heuristics with respect to both objectives, respectively; then to search new Pareto optimal solutions in a greedy way until the process is trapped into a local optimum. The conditions of choosing a new Pareto solution are that the solution is not dominated by the original solution and the solution from which the original solution was generated, and at the same time, the solution has minimal value with at least one of the two objectives. When all the Pareto optimal solutions are trapped into local optima, perturb the Pareto optimal solutions and restart the search process. The initial solutions and method of choosing new Pareto optimal solution have significant effect on the performance of the MOLS. The results of comparison with existing algorithms on benchmarks show that the MOLS performs better, especially for relatively large instances. The performance differences have statistical significance.