A genetic algorithm for job-shop scheduling problems using job-based order crossover

We propose a genetic algorithm for job shop scheduling problems. The proposed method uses a job sequence matrix. This paper introduces a new crossover, the job based order crossover (JOX), which can preserve characteristics very well. JOX preserves the order of each job on all machines between parents and their children, taking account of the dependency among machines. Since the children generated by JOX are not always feasible, we propose a technique to transform them into active schedules by using the Giffler and Thompson method (B. Giffler and G.L. Thompson, 1969). Furthermore, we introduce a mutation for maintaining a diversity of population without disrupting characteristics. By applying the proposed method to Fisher and Thompson's 10/spl times/10 and 20/spl times/5 problems (H. Fisher and G.L. Thompson, 1963), we show its usefulness.