Research On Methods For Multi-objective Flexible Job-shop Scheduling Problem

Manufacturing sector is an important part and the main force of national economy. However, several objectives must be considered simultaneously in the real-world production situation and these objectives often conflict with each other. For an enterprise, different departments have different expectations in order to maximize their own interests. Moreover, as the international competition becoming more and more intense and the growing of personalized product demand by the market, process time, completion time, delivery time and so on in the real production have been unable to describe as determined parameters as they were used to be. Meanwhile, there may be some dynamic events, such as machine malfunction, late arrival of raw materials, emergency insertion or cancel of order and so on. In this situation, people need to research on scheduling problems under uncertainty immediately and wildly to guide the real production, not only the theory but also its application. In this background, combined with the uncertain and dynamic optimization problems in the real plant and production, main research of this thesis is about multi-objective flexible job shop scheduling problem. And some meaningful conclusions and results are pointed out from this research.The Flexible Job-shop Scheduling Problem (FJSP) is an extension of the classical job-shop scheduling problem (JSP). This paper presents a hybrid genetic algorithm and tabu search (GATS) which incorporates the principle of "the survival of the fittest" from genetic algorithm (GA) into tabu search (TS) to solve the FJSP. According to the characteristics of the FJSP, an extended operation-based representation which simultaneously describes the sequence of operations and the assignment of operations to machines is applied to represent solution for GATS, and solutions are constructed using a procedure that generates active schedules. Two effective crossover and mutation operators are proposed to adapt to the chromosome structure. After individuals of GA are obtained, TS is applied to improve these solutions. The neighborhood structures of TS are designed by extending proposition proposed by Balas and Vazacopoulos to FJSP. The hybrid algorithm is tested on a set of standard instance taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.An improved multi-objective evolutionary algorithm (MOGA) is proposed for solving the mulyi-objective FJSP. Firstly, the multi-objective FJSP optimization model is put forward, which the makespan, the mean flow-time, total tardiness, total workload of machines, workload of the critical machine and production cost widely concerned in complex manufacturing system are considered. In order to ensure convergence and the diversity of the solutions, an improved non-dominated sorting genetic Algorithm (NSGA-II) is proposed and the immune and entropy principle is used to keep the diversity of individuals and overcome the problem of premature convergence. The proposed MOGA is evaluated on some representative instances and the comparison with other approaches in the latest papers validates the effectiveness of the proposed algorithm. Finally, the analytic hierarchy process (AHP) approach is used to select the satisfied solution.For the undetermined environment, fuzzy set is introduced to solve multi-objective FJSP with undetermined processing time and due date. Based on the improved MOGA proposed, we solved the multi-objective flexible job shop scheduling problem with fuzzy processing time and fuzzy due date. The computational results validate the effectiveness of the proposed algorithm.MOGA based on rolling-horizon procedure was proposed to solve the multi-objective dynamic FJSP. In this procedure, periodic and event driven rescheduling strategies were employed and the dynamic scheduling problem was decomposed into a series of continual and static scheduling problems, then the improved MOGA was applied to optimize each of the static scheduling problems. According to the characteristics of the dynamic scheduling problem, the efficient decoding procedure and genetic operators were presented for the improved multi-objective genetic algorithm, and the objectives of rescheduling were to minimize the makespan, total tardiness, the mean flow-time, deviations from the pre-schedule. In order to adapt to the complex manufact uring environment and sustain the stability of production, a human-computer collaborative scheduling procedure was presented for the implementation of the scheduling process. The approach was tested on the instance, and the simulation results validate the effectiveness of the proposed strategies.Real production workshop oriented scheduling prototype system is designed and developed based on the research findings above. The system architecture, development principles and function modules are described.Finally, the research in the whole dissertation is summarized and future work is generalized and looked forward.