For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1998/06/25
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>>
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.