A hybrid biogeography-based optimization algorithm for job shop scheduling problem

• A hybrid biogeography-based optimization (HBBO) is proposed for JSP.
• An effective encoding procedure is used to build the schedule.
• Experimental results show that HBBO could attain good performance for JSP.
• Comparative experiments with CPLEX and 14 other algorithms are conducted.
• The results show that HBBO outperforms other state-of-the-art algorithms.

In this paper, a hybrid biogeography-based optimization (HBBO) algorithm has been proposed for the job-shop scheduling problem (JSP). Biogeography-based optimization (BBO) is a new bio-inpired computation method that is based on the science of biogeography. The BBO algorithm searches for the global optimum mainly through two main steps: migration and mutation. As JSP is one of the most difficult combinational optimization problems, the original BBO algorithm cannot handle it very well, especially for instances with larger size. The proposed HBBO algorithm combines the chaos theory and “searching around the optimum” strategy with the basic BBO, which makes it converge to global optimum solution faster and more stably. Series of comparative experiments with particle swarm optimization (PSO), basic BBO, the CPLEX and 14 other competitive algorithms are conducted, and the results show that our proposed HBBO algorithm outperforms the other state-of-the-art algorithms, such as genetic algorithm (GA), simulated annealing (SA), the PSO and the basic BBO.