A local search based on simulations of fish school behavior and its application to an optimal scheduling problem

In this paper, an improved local search (ILS) method is proposed based on the idea obtained from the simulations of fish school behavior and is applied to an optimal scheduling problem of parallel machines. A rough definition of cooperation and diversity of job data is given for describing the characteristics of the system. A neighborhood of a solution is defined based on the system characteristics. A checking set is presented for avoiding overlapping local searches and unnecessary computation efforts. Computation results show that the quality of the suboptimal solution critically depends on the size of the neighborhood. By comparing ILS with the autonomous decentralized (ADS) algorithm and the genetic algorithm (GA), we observe that the proposed ILS has better convergence property than ADS and GA under an assumption that the total number of search points is limited and fixed irrespective of algorithm