A self-crossover Genetic Algorithm for job shop scheduling problem

Author

Hou, Shiwang ; Liu, Yongjiang ; Wen, Haijun ; Chen, Yuepeng

Author_Institution

Sch. of Mech. Eng. & Autom., North Univ. of China, Taiyuan, China

fYear

2011

fDate

6-9 Dec. 2011

Firstpage

549

Lastpage

554

Abstract

During the application of Genetic Algorithm (GA) for job shop scheduling problem (JSSP), chromosome representation and evolution strategy are the main consideration in order to guarantee the feasibility of solution. Crossover operation between two feasible solutions (parents) may result in infeasible solution (offspring).Inspired by the existence of self-reproducing in nature, this paper presents a self-crossover genetic algorithm for job shop scheduling problem (JSSP). The chromosome representation of the problem is based on work piece and the crossover operation is based on single individual. The approach was tested on a standard six-job six-machine (6×6) JSSP. The computational results validate the effectiveness of the proposed algorithm.

Keywords

genetic algorithms; job shop scheduling; single machine scheduling; chromosome representation; evolution strategy; job shop scheduling problem; self-crossover genetic algorithm; standard six-job six-machine JSSP; Biological cells; Computers; Genetic algorithms; Job shop scheduling; Processor scheduling; Schedules; Job shop scheduling; genetic algorithms; self-crossover;

fLanguage

English

Publisher

ieee

Conference_Titel

Industrial Engineering and Engineering Management (IEEM), 2011 IEEE International Conference on

Conference_Location

Singapore

ISSN

2157-3611

Print_ISBN

978-1-4577-0740-7

Electronic_ISBN

2157-3611

Type

conf

DOI

10.1109/IEEM.2011.6117977

Filename

6117977