An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem

The Distributed and Flexible job-shop Scheduling problem (DFJS) considers the scheduling of distributed manufacturing environments, where jobs are processed by a system of several Flexible Manufacturing Units (FMUs). Distributed scheduling problems deal with the assignment of jobs to FMUs and with determining the scheduling of each FMU, in terms of assignment of each job operation to one of the machines able to work it [job-routing flexibility) and sequence of operations on each machine. The objective is to minimize the global makespan over all the FMUs. This paper proposes an Improved Genetic Algorithm to solve the Distributed and Flexible job-shop Scheduling problem. With respect to the solution representation for non-distributed job-shop scheduling, gene encoding is extended to include information on job-to-FMU assignment, and a greedy decoding procedure exploits flexibility and determines the job routings. Besides traditional crossover and mutation operators, a new local search based operator is used to improve available solutions by refining the most promising individuals of each generation. The proposed approach has been compared with other algorithms for distributed scheduling and evaluated with satisfactory results on a large set of distributed-and-flexible scheduling problems derived from classical job-shop scheduling benchmarks. (C) 2009 Elsevier B.V. All rights reserved.