An Evolutionary Scheduling Scheme Based on gkGA Approach to the Job Shop Scheduling Problem

Beatrice M. OMBUKI  Morikazu NAKAMURA  Kenji ONAGA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.6   pp.1063-1071
Publication Date: 1998/06/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from ITC-CSCC'97)
Category: Algorithms and Data Structures
genetic algorithm,  gkGA,  job shop scheduling problem,  combinatorial optimization,  

Full Text: PDF>>
Buy this Article

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.