Study Of Scheduling Problem Based On Genetic Algorithm

As the manufacturing system becomes larger and larger, and the production operation environment becomes more and more complex, the resource waste, the low efficiency and other problems are increasingly outstanding. The scheduling problem is usually defined as planning the jobs of the production process, for example, the processing sequence of the work pieces processed by the machines, the division of the production lot size and so on. The optimized scheduling strategy is helpful to solve the low efficiency of the manufacturing system and improve the economic benefit. According to the computational complexity theory, most scheduling problems are proved to be NP-hard (Nondeterministic Polynomial hard, NP-hard) problems, and the genetic algorithm is adopted to solve two kinds of scheduling problems, which are the scheduling problem of the FMS (Flexible Manufacturing System, FMS) and the JSP (Job-shop Scheduling Problem, JSP).Firstly, the current situation and research methods of the scheduling problem home and abroad are introduced, and then the Petri net theory and the related knowledge of Genetic Algorithm are described.Secondly, the scheduling problem of the FMS is studied, and then a scheduling method which combines the modeling method based on the Petri net with the improved genetic algorithm. The timed place Petri net is used to model the FMS, and then the improved genetic algorithm is used to solve the FMS model. The proposed algorithm mainly improves the genetic operators of the basic genetic algorithm. Through the simulation experiment based on the MATLAB, the effectiveness and advantage of the proposed improved genetic algorithm are verified in solving the scheduling problem of the FMS.Finally, the JSP is studied. Another new improved genetic algorithm is proposed by improving the coding method and operators of the basic genetic algorithm. The MATLAB is used to realize the algorithm, and then the algorithm program is compiled to become DLL (Dynamic Link Library, DLL) file. Based on the mixed programming thought of MATLAB and VC++6.0, the VC is used to develop the scheduling system software, which can realize the input, output, the dynamic display interface of the scheduling problem and the calling of the improved genetic algorithm DLL file to solve the scheduling problem. According to the related simulation examples, it is proved that the improved genetic algorithm has good optimization effect in solving JSP and the scheduling system software is practical.