Convergence analysis of the new hybrid genetic algorithm for job shop scheduling problem

Lục Trí Tuyên, Nguyễn Hữu Mùi, Vũ Đình Hòa

Abstract


In the recent our paper, we proposed a new hybrid genetic algorithm (NHGA) for the job shop scheduling problem (JSP). The method of encoding we used was Natural coding instead of traditional binary coding. This manner of coding has a lot of advantages but its convergence is still an open issue for years. This paper analyzes the convergence properties of the NHGA by applied properties of  Markov chain. Based on the Markov chain analysis of genetic algorithm, we point out the proposed method leads to convergence to the global optimum in case of Natural coding.

Keywords


Job shop scheduling, genetic algorithm, global convergence, Markov chain



DOI: https://doi.org/10.15625/1813-9663/29/2/1260

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology