Symbiotic Genetic Algorithm For Job Scheduling Research

In recent years, genetic algorithm (GA) has been a research focus in the area of science. Many researchers have done much work on genetic algorithm. As a class of typical production scheduling problems, job shop scheduling problem (JSP) is one of the strongly NP-complete combinatorial optimization problems.This paper addresses the integrated problem of process planning and scheduling in job shop flexible manufacturing systems. Due to production flexibility, it is possible to generate many feasible process plans for each job. The two functions of process planning and scheduling are tightly interwoven with each other. The optimality of scheduling depends on the result of process planning. The integration of process planning and scheduling is therefore important for an efficient utilization of manufacturing resources. To deal with the job shop scheduling problem (JSP), a method using an artificial intelligent search technique, called symbiotic evolutionary algorithm, is employed as the underlying framework, which is presented to handle the two functions at the same time.It is hard to evaluate an individual's contribution in symbiotic evolutionary algorithm. In this paper, a new definition of individual's fitness function is proposed in this paper. Simulation results demonstrate the effectiveness of the proposed definition, whose optimization performance is markedly superior to those in the literature and can get much better solutions and costs less time.The scope of adjacent area that adopted in coevolutionary algorithm is also hard to evaluate. Simulation results demonstrate that the scope of adjacent area is unimportant, but small scope of adjacent area can reduce computation of the algorithm.For the performance improvement of the proposed algorithm, it is important to enhance population diversity and search efficiency. We adopt the strategies of localized interactions and random symbiotic partner selection. Efficient genetic representations and operator schemes are also considered. While designing the schemes, we take into account the features specific to each of process planning and scheduling problems.An effective crossover operation-MSX- is adopted to improve the performance of the algorithm. A decoding algorithm based on famous GT algorithm guarantees the feasibility of the solutions, which are decoded into active schedules during the search process. Simulation results demonstrate the effectiveness of the...