Abstract: Among all kinds of production scheduling problems, job shop scheduling problem (JSSP) is a key one with extensive engineering application background. The minimization of maximum completion time or makespan for JSSP is addressed. Based on some properties associated with the blocks of jobs on the critical path in the direct graph of JSSP, the way to generate feasible solution by an interchange or insertion operator is presented, and two specific search neighborhoods are obtained. Then a discrete differential evolution (DDE) algorithm with operation-based representation is developed for solving JSSP. The proposed DDE algorithm adopts a newly designed mutation and crossover operators and it can directly generate feasible solutions in the search space. An effective local search based on the newly obtained neighborhoods is presented and imbedded in the DDE algorithm to enhance the local search ability. Computational simulations and comparisons demonstrate the effectiveness and superiority of the proposed DDE algorithm.

Key words: Differential evolution algorithm, Job shop scheduling problem, Local search algorithm, Maximum completion time