یک الگوریتم ژنتیک ترکیبی برای مشکلات برنامه ریزی تولید کارگاهی

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.

Scheduling problems vary widely according to specific production tasks but most are NP-hard problems. Scheduling problems are usually solved using heuristics to get optimal or near optimal solutions because problems found in practical applications cannot be solved to optimality using reasonable resources in many cases. Since the early 1980s, much interest has been devoted to the development and application of the meta-heuristic algorithms. Among the meta-heuristic algorithms, the Genetic Algorithm (GA), inspired by the process of Darwinian evolution, has been recognized as a general search strategy and an optimization method which is often useful for attacking combinational problems. In contrast to other local search methods such as simulated annealinG&Tabu search, which are based on handling one feasible solution, the GA utilizes a population of solutions in its search, giving it more resistance to premature convergence on local minima. Since Davis (1985) proposed the first GA-based technique to solve scheduling problems, GA has been used with increasing frequency to address scheduling problems. Classical GAs use a binary string to represent a potential solution to a problem. But such a representation is not naturally suited for ordering problems such as the Traveling Salesman Problem (TSP) and Job Shop Scheduling Problem (JSSP) because a classical GA representation using simple crossover or mutation on strings nearly always produces infeasible solutions. Thus, to address this problem, Bierwirth, 1995 and Syswerda, 1991 proposed a new chromosome representation. Dorndorf and Pesch, 1993 and Yamada and Nakano, 1992 used some variations on standard genetic operators and the hybridization of some existing algorithms. Bagchi et al., 1991, Davis, 1985 and Uckun et al., 1993 used a decoder or a schedule builder which performed the transition from a chromosome representation to a feasible schedule when a representation did not directly represent a schedule. Nakano and Yamada, 1991 and Tamaki and Nishikawa, 1992 used repair procedure to find feasible schedules from an infeasible string and a treatment called forcing. In these researches, one needs proper representation, repair procedure, forcing and decoder associated with existing algorithms to maintain a feasible chromosome, which requires additional time. If chromosome representation can always maintain feasibility after a genetic operation, the GA can be simplified because it does not need repair procedure, forcing and decoder process. Also, in most researches, the initial population is produced randomly to generate diverse individuals. However, a local search has high possibility of searching an optimal solution if a search starts from a good initial solution. Thus we can obtain a superior solution if the construction method of initial population always produces feasible, diverse and superior individuals; and genetic operators and selection method can be developed to produce a new population that is fitter than the previous one. Also, one common problem in classical GAs is premature convergence. Although classical GAs are more resistant to premature convergence than other local search methods, GAs are not immune. One approach to reduce the premature convergence of a GA is parallelization of the GA (PGA) into disjoint subpopulations. The advantages of a PGA are preventing premature convergence and allowing speedup via the use of parallel processors. The goal of this research is to propose an efficient GA-based scheduling method addressing these concerns.

An efficient GA-based scheduling method is developed to address JSSP in this research. In the scheduling method, the representation, which encodes the job number, is made to be always feasible. Initial population is generated through integrating representation and G&T algorithm. The new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome. And the initial good schedules can be evolved into the better schedules. The proposed scheduling method is tested on standard benchmark JSSP. The superior results indicate the successful incorporation of generating method of initial population into the genetic operators, and show the effectiveness of the scheduling method. The results in the five benchmark problems indicate that the case of crossover 1 and seed selection is more appropriate for small size problem like CAR problem, and the case of crossover 2 and tournament selection is more appropriate for large size problem like ABZ 7-9 and YN problem. However, the case of crossover 4 and seed selection produces the most number of optimal solutions and best solutions at all benchmark problems. Also, PGA improves not only the best solution but also the average solution from results of SGA. When time is limited PGA may produce superior solution effectively. The superior performance of the proposed GA is obtained by the successful incorporation of the chromosome representation, the generating method of initial population, genetic operators and selection method, which are designed to better transmit the temporal relationships in the chromosome. The GA may be very useful for real world scheduling problems because of simplification based on hybridization of GA and existing algorithm and creative evolution procedure.