Font Size: a A A

Research Based On Petri Net And Gene Expressing Programming In Job-shop Scheduling

Posted on:2015-05-06Degree:MasterType:Thesis
Country:ChinaCandidate:J YangFull Text:PDF
GTID:2298330434465586Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
With the development of manufacturing industry, the realization process of job-shop scheduling problem is becoming more and more complicated.Job-shop scheduling problem is a combinatorial optimization problem which has different kinds of constrain condition. This problem is a study hotspot for its practical application background, so lots of study methods arise as well as a large number of literature. But this problem has proved to be a NP-hard, so there is no practical solution till now,because of this more and more scholar become interested in this and raised manysignificant scheduling algorithm, which motivates enthusiasm for studying scheduling problem of scholars.Currently, there are over10kinds of research towards scheduling problem, among which simulation modeling for JSP with Petri nets, methods of control and so on. This paper choose Petri net as job shop scheduling problem Modeling Tools. Petri nets development has been60years of history, it’s a very sophisticated mathematical modeling tools, Scheduling system can be real-time simulation model based onPetri nets. Currently Petri nets often discrete event analysis and modeling, Petri nets function can be integrated modeling system. This selection can be seen from thePetri net modeling design provides a convenient shop scheduling. The paper first timed Petri nets use a simple model based on shop scheduling problem described scheduling problem, and subsequently proposed Time Colored Petri nets complex scheduling issues modeling analysis, this article proposed modeling method can directlysee the scheduling complicated scheduling problems, but also to verify the modelingtheory proposed is feasible.Come up with GEP coding which is different from tradition. In the algorithm of this paper, the tail of chromosomal is determined according to the transition sequence of timed Petri model, and a kind of job-shop scheduling plan can be determined according to each tail of chromosomal. In this paper selection, cross and mutation of gene expression to process genetic manipulation. Among them, the cross andmutation is different from prototype Petri, and design the specific genetic manipulation according to scheduling problem. In the end, according to the imitation of job-shop scheduling problem, the corresponding time of each chromosomal was got from transitional time delay. With the preferable search ability of GEP and dynamic process can be well described by Petri net for examples of the simulation experiment. At last compared by the experience data to prove the algorithm mentioned by this paper is feasible.
Keywords/Search Tags:Job-Shop Scheduling, Gene Expression Programming, Timed Petri Net, Timed Colored Petri Net
PDF Full Text Request
Related items