ABACTERIAL EVOLUTIONARY ALGORITHM FOR THE JOB SHOP SCHEDULING PROBLEM

Abstract

The job-shop scheduling problem is one of the most complicated and well-known hardest combinatorial optimization problems. It's purpose is to improve the production efficiency and reduce the processing duration so as to gain profits as high as possible. In addition, it has been illustrated that job-shop scheduling is usually an NP-hard combinatorial problem and is therefore unlikely to be solvable in polynomial time. In this study, a bacterial evolutionary algorithm is proposed for finding multiple optimal solutions to the job-shop scheduling problem. Bacterial evolutionary algorithm is an optimization method that incorporates special mechanisms inspired by natural phenomena of microbial evolution. Gene transfer and bacterial mutation operators are incorporated to improve the performance of the proposed method. Moreover, niche scheme is employed to discover multiple solutions. Numerous well-studied benchmark examples were utilized to evaluate the effectiveness of the proposed approach.