Presentation 1995/5/25
A Genetic Algorithm with Multi-Step Crossover for Job-Shop Scheduling Problems
Takeshi Yamada, Ryohei Nakano,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Genetic Algorithms (GAs) have been designed as general purpose optimization methods. GAs can be uniquely characterized by their population-based search strategies and their operators : mutation, selection and crossover. In this paper, we propose a new crossover called multi-step crossover (MSX) which utilizes a neighborhood structure and a distance in the problem space. Given parents, MSX successively generates their descendents along the path connecting the both of them. MSX was applied to the job-shop scheduling problem (JSSP) as a very high-level crossover to work on the critical path. Preliminary experiments using JSSP benchmarks showed the promising performance of a GA with the proposed MSX.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Genetic Algorithms / multi-step crossover / job-shop scheduling / neighborhood search
Paper #
Date of Issue

Conference Information
Committee AI
Conference Date 1995/5/25(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Vice Chair

Paper Information
Registration To Artificial Intelligence and Knowledge-Based Processing (AI)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) A Genetic Algorithm with Multi-Step Crossover for Job-Shop Scheduling Problems
Sub Title (in English)
Keyword(1) Genetic Algorithms
Keyword(2) multi-step crossover
Keyword(3) job-shop scheduling
Keyword(4) neighborhood search
1st Author's Name Takeshi Yamada
1st Author's Affiliation NTT Communication Science Laboratories()
2nd Author's Name Ryohei Nakano
2nd Author's Affiliation NTT Communication Science Laboratories
Date 1995/5/25
Paper #
Volume (vol) vol.95
Number (no) 75
Page pp.pp.-
#Pages 8
Date of Issue