Algorithm based on composite neighborhood search for job shop scheduling problems

Job shop scheduling problem is a kind of typical production scheduling problems. The majority of this kind of problem is NP-hard computational complexity. Local search are easily trapped into local optima. This paper has a deep research on neighborhood structure of job shop scheduling problem. Then proposed a new algorithm based on composite neighborhood that combine the merits of two classic neighborhoods. The algorithm search neighbor solutions that generated by one of the two classic neighborhood structure according to real-time condition. At last, several groups of experiments have done for algorithm validation and comparison. Experiments results show that the search algorithm proposed in this paper can get better results than some classic algorithms and the algorithm is fit for large scale job shop scheduling problems.