The Analysis And Study On A Class Of Flow-shop Scheduling Problem And The Optimization Methods

With the development of science and technology, the production complexity of enterprises increased greatly, and the competition became more and more fiercer, so the management on the factories and the monitor on the production process deserved more research. Production planning and scheduling is the key of Computer Integrated Manufacturing System (CIMS). Scholars have solved some classes of the scheduling problems using the methods of linear programming, integral programming, objective programming and dynamic programming etc.. However, many kinds of scheduling problems are NP-Hard and there are no efficient algorithms to solve them completely, so this research also has important theoretic and practical value.The Permutation Flow-shop Scheduling Problem (PFSP) is a kind of typical production scheduling problem, which has the property of NP-Hard. In the factory, there are many jobs to be proceeded on the same machine and many operations of a job to be operated on many distinct machines, and the processing time of the operations are also distinct, so the different operation sequences of the jobs would result different final completion time. The sequence that minimizes the maximal completion time can enhance the factory's ability to delivery productions with the limited resource, which is very important on improving the work efficiency and the economic value.This paper is focused on the PFSP with the makespan criteria. In Chapter 2, all kinds of different optimization methods on PFSP were classified and reviewed; In Chapter 3 and Chapter 4, the PFSP itself was analyzed to find the tools to develop new heuristics; In Chapter 5 and Chapter 6, the best heuristic up-to-date was studied and modified to obtain more effective algorithms than ever. The experiment was executed and it was presented that the modified heuristics have a better performance and they were very suitable to solve very large permutation flow shop problems. The main contributions of this work are listed as follows:1. The research on PFSP for decades was reviewed and all kinds of algorithms were listed and commented.2. The gird graph was used to analysis PFSP, and the new defined vertical subpath and horizontal subpath made the critical block concept more general and visualized. The different path formulae were offered, several path-changing methods were provided, and the lower bound formulae were drawn and extended. Two kinds of modified NEH methods using the single critical path constructive technique and the dynamic critical path constructive technique were tested on the benchmark instances, and the result verified the elimination ability on non-promising permutations using the classic and the extended lower bound formulae.3. Besides the basic algorithm to calculate makespan, several other different methods were presented and proved. The makespan can be formulated using the forward completion time and the backward completion time, so, when evaluated the similar permutations in the neighborhood search process, many immediate results can be reused to save time and improve the calculating efficiency. In the block insertion neighborhood search, the fast makespan computing method was provided using the extended critical path concept to evaluate the similar permutations. It was proved that the presented method is more effective and can save more time comparing with the technique in the reference.4. Several kinds of ties breaking methods for NEH heuristic were presented. Concerning both the final solution quality and the time cost, NEH heuristic has been the best algorithm for decades. Ties may exist in both the initial permutation forming phase and the new job insertion process of NEH algorithm. Most scholars use the natural method to break the ties. This work provided 42 kinds of extra methods to break the ties in NEH. Most of the modified algorithms have an improvement on the original NEH. In addition, the computation cost comparison was presented, and the result showed that there was no obviously extra time needed. So, the improved methods can be used to replace the original one, and act as the initial permutation for the improvement heuristics and metaheuristics.5. The former studies on NEH heuristics was recalled, and it was pointed that the former ones were mainly focused on the initial sequence. This part devoted its effort on the insertion stage for the unscheduled jobs, and showed that the original procedure is equal to the neighborhood search. On this basis, two kinds of reduced neighborhood search were compared with that in the original NEH. Also, several kinds of enhanced neighborhood search methods are proposed, and better results were obtained. Because of the extra time cost using the enhanced neighborhood, several methods were recommended to save time. Finally, an object function was used to remove a job at the worst position and re-insert it into the more suitable slot, and two kinds of more effective algorithms with an elaborated neighborhood named INEH and BINEH were resulted. Both of them have nice performance, and the main highlight of the two suggested methods is that they have a time complexity of O ( n 2m ), so they can solve the even larger scale instances than ever at high speed with excellent quality.