Dual-resources Job-shop Scheduling Based On Petri Nets And Hybrid Genetic Algorithm

Scheduling problem is the basis of the manufacturing system. Effective scheduling and optimization technologies are crucial to achieve advanced manufacturing and high efficiency of manufacture. Job shop scheduling is a kind of typical production scheduling. From the mathematical programming point of view, job shop scheduling problem (JSP) can be expressed as the optimization of the objective function with equation or inequality constraints. In recent decades, most of the literature on JSP consider only machine as a limitation and ignore the possible constraints imposed by the ability of workers. The fact is that both machine and workers are required to complete a job in a real manufacturing process. This type of JSP, where both machine and worker represent potential capacity constraints, is called Dual Resource JSP. The kernel of JSP is the model and the effective scheduling algorithm. In this thesis, we focus on modeling JSP with Petri nes and applying hybrid algorithm for scheduling. Petri nes, as the graphical and mathematical modeling tools, can provide an integrated modeling, analysis and control environment. It can properly describe the discrete events dynamic process. Using Petri nes for the design of JSP is convenient and efficient. As for hybrid algorithm design, the literature shows that genetic algorithm (GA) and simulated anneling (SA) achieved good performance on solving complex JSP although both algorithms have their limitations. GA uses group parallel searching and tends to expand search space, but its local search ability is poor, and easily converges. SA uses serial optimization structure. Its search strategy can avoid falling into local optimization. However, SA has little information about search space and therefore is unsuitable for large scale search. In this thesis, we design a hybrid algorithm called GASA by combining GA and SA, which can preserve their advantages and throw away their respective disadvantages.This thesis uses Petri nets and GASA as tools to study the Dual-resource JSP with multiple process plants. The result has shown the proposed algorithm is efficient.The principal research results and contents can be outlined as follows:1,Timed Petri net is used to model the Dual-resource JSP. Based on this Petri net modle, deadlock and resource competition problems are handled.2,Based on the Petri net model, the firing sequence stands for a chromosome, and GASA operations are based on the elements of the timed Petri net model. This approach is independent on the elements(reachable states) and hence avoid the hard state space explosion problem.3,Finally the proposed algorithm GASA for Dual-resource JSP is implemented with C++. GASA is compared with GA. The result shows that the GASA is more efficient.