Evolutionary Computing of Petri Net Structure for Cyclic Job Shop Scheduling

Morikazu NAKAMURA  Koji HACHIMAN  Hiroki TOHME  Takeo OKAZAKI  Shiro TAMAKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.11   pp.3235-3243
Publication Date: 2006/11/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.11.3235
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: Concurrent Systems
Keyword: 
Petri net,  evolutionary computation,  Job Shop Scheduling,  Cyclic Job Shop Scheduling,  mark graph,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper considers Cyclic Job-Shop Scheduling Problems (CJSSP) extended from the Job-Shop Scheduling Problem (JSSP). We propose an evolutionary computing method to solve the problem approximately by generating the Petri net structure for scheduling. The crossover proposed in this paper employs structural analysis of Petri net model, that is, the crossover improves the cycle time by breaking the bottle-neck circuit obtained by solving a linear programming problem. Experimental evaluation shows the effectiveness of our approach.