Research On Application Of Improved Genetic Algorithm To Scheduling Problem

Manufacture based on network is the advanced manufacturing mode of enterprises in 21st century, and its final aim is the customer-like products made at the lowest cost. Under the mode, it is becoming more necessary that how to utilize the limited resources, to decrease the produce cost, to shorten the produce circle, to ensure the delivery before due date, to upgrade the credit standing, to widen the clients and so on. Thus, it is a forland task to optimize the scheduling problems, and we can find its magnitude application value in produce engineering.Genetic Algorithms are search algorithms based on the mechanics of natural selection and natural genetics. It is widely used in many kinds of fields because of its less-dependency of optimization problem, simplicity, robustness and implicit parallelism. While applied to scheduling problems, it has some limitations to be solved. The paper is dedicated to the application of improved GA to scheduling problems emergenced nearly. The main creative results are as follows:1. Aiming at the limitations of GA on coding while applied to machine scheduling problems, the paper proposed the code expression of job-machine based, the coding is not subjected to the restrictions and is free of modification.2. Solved the earliness/tardiness scheduling problems with the restrictions of due date with the given algorithm above. The solved problems belong to the most universal kind, so it is fit for other cases.3. Aiming at the limitation of Simulated Anneal Genetic Algorithm on a high computation while applied to flow shop scheduling problems, the paper presented selected simulated anneal genetic algorithm. The algorithm can not only find the more optimal value, but also accelerate the convergence rate. Then, found its application in flow shop scheduling problems with two objects.4. Aiming at the limitaion of parallel genetic algorithm on premature convergence whie applied to job shop scheduling problems, the paper gave out the bi-mode parallel genetic algorithm, and found its application in maximum the grade of satisfaction of job shop scheduling promblems.The problems involved in this paper are all static state, hence it is not subjected to the computing time. While in practise, dynamic scheduling problems and the cases with restrictions should deserve more attention.On methods of scheduling, though genetic algorithm has found its wide application, it still has a long way to overcome the limitations of premature convergence and a large mount of computing. Although various methods have beenproposed such as self-adopt GA, simulate anneal GA, parallel GA, orthodoxy GA and so on, they are superior in only one side. How to develop the method which can not only accelerate the evolve rate, but also fight premature convergence is the main task of researchers active in times.