Research On Methods For Flexible Job Shop Scheduling Problems

With global market competition intensified, customer demands transform to the personalization and diversification. Enterprises increasingly concern on how to design a reasonable schedule scheme to shorten production cycle and reduce work-in-process inventory and deliver just-in-time, etc. so as to enhance the competitiveness and improve customer satisfaction. Flexible Job-shop Scheduling Problem (FJSP) is an extension of classic job-shop scheduling problem, and it is also one of the most difficult combinatorial optimization problems. FJSP is paid more and more attention by researchers and technicians.FJSP contains two sub-problems: the routing sub-problem and the scheduling sub-problem. When utilizing evolutionary algorithms to solve job-shop scheduling problems, how to design efficient chromosome encoding scheme for FJSP is very important. Based on analyzing and summarizing existed chromosome encoding schemes, integer encoding based chromosome encoding scheme MSOS (Machine Selection and Operation Scheduling) which could reduce the generation of illegal solutions and decrease the storage space of chromosome is designed. Moreover, the method, without needing setting parameters, could easily express partial flexibility FJSP and total flexibility FJSP.Based on full consideration of balancing the workload of each machines, global selection and local selection methods are proposed for generating reasonable scheme for machine selection. The two methods are used to initialize population with random method, which make solutions distribute more widely in solution space, so as to improve the quality and diversification of initial solutions and promote the solving efficiency. Integrating with the proposed encoding scheme and novel initialization method, the improved genetic algorithm is tested by standard tests. The computational results show the effectiveness and superiority compared with other algorithms. Moreover, the best combinational proportion of global selection, local selection and random method is analyzed.Many studies show that single optimization algorithm is much difficult to solve complex scheduling problem, while the hybrid of some optimization algorithms could provide more powerful search capability. Based on improved genetic algorithm, variable neighborhood search (VNS) algorithm with powerful local search capability is used to mixed. VNS is available for the FJSP with different landscape, and could prevent the algorithm trapping into local optimal. A simple and highly efficient hybrid genetic algorithm is designed to balance the diversification and intensification during the search process, and counterbalance the shortcomings of single algorithm. Fully considering the feature that operations has available machine set, two neighborhood structures are designed for VNS based on the characteristic of FJSP. By the use of external memory with elitism strategy, individuals with good information could retain to the next generation. The hybrid genetic algorithm could obtain good results for the majority of a total of 178 problems in four groups of standard tests.Taking into account the condition that multiple objectives need to be optimized simultaneously in real production, multi-objective FJSP is studied, and multi-objective Pareto hybrid algorithm is designed combining with the relationship among multiple objectives in FJSP.By further using global search capability of genetic algorithm and local search capability of VNS for non-inferior solution, and introducing external archive to restore better non-dominated solutions of every generation, it is effective to slow down the trend of converging on a single individual during the searching process, meanwhile, it could prevent the lost of alternative solutions caused by premature of genetic algorithm, output all available solutions at the frontier of Pareto is output finally. Standard tests are carried out to verify the effectiveness of the proposed algorithm.In the real production environment, there exist unexpected events interfering normal production. In the dissertation, the research findings of static FJSP are extended to dynamic FJSP, and dynamic FJSP is studied intensively. Making full use of the advantages of the computer and man, utilizing mechanism of man-machine cooperation, and adopting cycle and event driven based scheduling strategy to deal with dynamic events, a dynamic scheduling algorithm based on hybrid genetic algorithm is proposed, which could enhance the handling capability for emergencies to ensure a smooth production. Finally, the proposed algorithm is applied to several dynamic events in real production to verify the feasibility and effectiveness of the scheduling optimization strategy.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. Meanwhile, the operating example of the system is exhibited.Finally, the research in the whole dissertation is summarized and future work is generalized and looked forward.