A Hybrid Algorithm For Job Shop Scheduling Problem

Job shop scheduling problem (abbreviated to JSP) is one of the classic combinatorial optimization problems. It considers the problem that finding a schedule with minimum makespan given n jobs and m machines. In this paper, a hybrid algorithm was proposed. The algorithm combined genetic algorithm and local search. As for local search which influenced the effectiveness of the algorithm seriously, a local search method named block-by-block searching algorithm was designed. And aimed at the problem that diversity of colony may reduced by local search, the crossover procedure was improved using Zorbrist key.Block-by-block searching algorithm was improved on the basis of local search algorithm that based on critical block. A critical block is some operations that decided the makespan on given schedule. Local search algorithms, based on critical block, search for a proper transform on critical blocks in order to improve given solution. The neighborhood these algorithms search on, is a union of transforms of different critical blocks. Common approaches that search the total neighborhood required calculation and update on a lot of data every iteration. As for the problem, the search method was improved to a manner that search block-by-block and quit once a proper transform was found leaving the rest of the blocks unsearched. Calculations relative to the search is also designed to proceed block by block according to the search.Using local search to improve offspring, increases the risk that offspring moving into the same local optima, hence reduces diversity of the colony and affects effectiveness of the algorithm. In this paper, crossover procedure was improved using Zorbrist key such that it made crossover offspring differ from recent searched solutions as far as possible in order to keep diversity of colony and make the search cover more area.According to experiment, the efficiency of GSS algorithm was confirmed.