Abstract: A hybrid algorithm combining chemical-reaction optimization and tabu search (CROTS) for solving the fuzzy job-shop scheduling problem (FJSSP) is investigated. The objective is to minimize the fuzzy makespan, i.e., the maximum fuzzy completion time. In the hybrid algorithm, encoding mechanism is realized through an operation sequence based way. Four improved Chemical-reaction optimization (CRO) collisions are embedded in the proposed algorithm, i.e., on-wall collision, inter-molecule collision, synthesis, and decomposition. An efficient crossover operator is designed and applied into the three elementary collisions, i.e., inter-molecule collision, synthesis, and decomposition. TS based local search is embedded to perform exploitation for the best molecule, which enhances the search ability of the algorithm. The proposed algorithm is tested on the sixteen well-known benchmark instances. Through the comparisons with other three present algorithms, the highly effective performance in exploration and exploitation capability of the proposed CROTS algorithm is concluded. Through the tests on eighteen randomly generated instances, the capability of CROTS for solving large scale problems is verified.

Key words: Chemical-reaction optimization, Fuzzy job-shop scheduling, Hybrid algorithm, Tabu search