Multi-strategy improved sparrow search algorithm for job shop scheduling problem

As a new swarm intelligence algorithm, sparrow search algorithm (SSA) has the advantages of fewer parameters, simplicity, strong global and local search capability, and has been successfully applied in continuous problem and its engineering applications. Meanwhile, SSA for job shop scheduling problem (JSP) is studied rarely and would arise new problems such as conversion from continuous space to discrete space, falling into local optimum, etc. To address these issues, considering the features of SSA and JSP, the multi-strategy improved sparrow search algorithm (MISSA) is devised to solve minimum makespan of JSP. First, the operation sort based encoding transformation method of SSA for discrete problems is devised. Second, tent chaotic mapping is instead of random generation to initialize sparrow population to expand space of solution. Third, the crossover operation of genetic algorithm is introduced in producers and scroungers positions updating to maintain the population diversity and improve the algorithm search ability. Fourth, the mutation operation of genetic algorithm is adopted in the position update of the vigilance to enhance the local searching capability. Fifth, the simulated annealing algorithm was adopted to avoid the local optimal solution and reach the global best solution. In the end, using 10 classical examples of JSP and one practical scheduling example, comparisons of MISSA with other algorithms are simulated, and the results show that MISSA effectively solves JSP.