Petri Nets And Hybrid Genetic Algorithm Based Approach For JSP Scheduling Optimization

The present dissertation uses Petri nets (PN) and hybrid genetic algorithms as tool to study the scheduling optimization of job shop with multiple process plants. The algorithm is compared with other scheduling algorithms and is tested by standard benchmark scheduling problem. The result has shown that the proposed algorithm is correct and excellent. To the dynamic dual-resource constrained scheduling problem, new strategies and methods are studied and analyzed. The best strategy is pointed out. The principal research results and contents can be outlined as following:Firstly, A new method of feedback controller design with combined place marking and transition firing constraint based on part net design and Petri net reduction technique is proposed for the first time in this dissertation. The method has the advantage of simpler computation and avoiding searching the entire state space over the reported methods, thus the computation efficiency superiority of the method is evident. The advantage is more obvious especially when the system is large and complex. The control concept of this method is plain and easy to be understood by the control engineers.Based on Petri net with controller , single- resource constraint job shop scheduling optimization problem is studied. A hybrid algorithm combined genetic algorithm and simulated annealing algorithm is applied, which considers process plan and scheduling. The result has shown that the proposed algorithm is correct and excellent.The dual-resource constraints dynamic scheduling is studied based on static scheduling. First, classify for machine breaks down, worker leaves, order cancels based on time and task, then decide whether carry out re-scheduling. Especially important, a new method of disposing urgent jobs is proposed, which deal with remainder and urgent jobs separately. Select optimal results of remainder jobs based on optimal scheduling of urgent jobs. The method realizes not only whole is optimal but also part is optimal too.Finally, a job shop scheduling software is developed using Delphi.