Abstract:

Two neighborhood searching methods for flexible job-shop scheduling problems are proposed, one is extremal optimal neighborhood searching and the other is extended critical block neighborhood searching. These two methods are combined to form a neighborhood searching operator named ECE operator, holding both wide searching space and strong searching ability. An improved genetic algorithm is constructed employing the ECE operator to enhance its local search ability. Besides, a novel coding mode of the algorithm is proposed to create two-part chromosomes: operations permutation code and machines assignment code; the coding method enables both parts of the chromosomes being manipulated by the same genetic operators，which simplifies the algorithm’s structure. The computation results validate the effectiveness of the proposed algorithm.