A hybrid clonal selection algorithm for solving job-shop scheduling problems

An improved clonal selection algorithm (ICSA) combined with neighborhood local search approach is proposed for solving job shop scheduling problems in this paper. In ICSA, the antibody population is decomposed into three subsets: the bests, mediums and worsts. The bests aim to find the local optimum by mutation. The mediums experience crossover with a randomly selected best antibody to explore the global optima space, and the randomly generated antibodies replace the worsts to ensure the population diversity. Only when the ICSA seems stagnating it´s permitted inserting local search procedure based on Nowicki and Smutnicki´s neighborhood to further exploit the local optima while the current mutation scheme is alternated by another. Furthermore, after each generation of ICSA and local search procedure, the population diversity is checked, and then one of candidates with the same schedule is preserved and the others are regenerated randomly. The proposed algorithm is examined using some well-known benchmark problems and numerical results validate its effectiveness.