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.

This paper presents an evolutionary scheduling scheme for solving the job shop scheduling problem (JSSP) and other combinatorial optimization problems. The approach is based on a genetized-knowledge genetic algorithm (gkGA). The basic idea behind the gkGA is that knowledge of heuristics which are used in the GA is also encoded as genes alongside the genetic strings, referred to as chromosomes. Furthermore, during the GA selection, weaker heuristics die out while stronger ones survive for a given problem instance. We evaluate our evolutionary scheduling scheme based on the gkGA approach using well known benchmark instances for the JSSP. We observe that the gkGA based scheme is shown to consistently outperform the scheme based on ordinary GAs. In addition the gkGA-based scheme removes the problem of instance dependency.