Genetic Algorithm Design Based On Uniform Integer-Encoding And Its Application To Job-Shop Scheduling Problems

The production planning and scheduling system directly affect the efficiency and cost of enterprise. Effective planning and scheduling algorithms can improve benefit. But scheduling problem is combinatorial optimization problem, which belongs to NP problems and is difficult to solve by regular method. In recent years, some intelligent algorithms have been used for this problems, such as GA (genetic algorithm) and SA (simulated algorithm) etc. Among many intelligent algorithms, GA is an active member. It is widely used in many kinds of fields because of its less-dependency on optimization problems, simplicity robustness and implicit parallelism.Job Shop Scheduling Problem(JSSP) is one of the most difficult combinatorial optimization problems,which allocates resources in order to perform a number of tasks,such as tasks collocating and ordinal restriction. To realize modern manufacture and promote production efficiency,research on effective production scheduling methods and optimization techniques and its application are the fundamental and essential problems. As early as in the 1950's much research have been done and the main solving methods are heuristic algorithms, which based on priority, that's arranging operations from the special subsets of unordered operations. The main research work in this thesis is as follows:Firstly, introducing the class and characteristics of job-shop scheduling problem, the thesis reviews historical developments on JSSP domesticallyand internationally, introduces existing methods solving JSSP , because of its complexity,randomicity and restriction and other characteristics ,the researchers have put forward several hundreds scheduling algorithms .This thesis mainly introduce affirmatory optimization algorithm,the scheduling algorithm basing on heuristic regulation and the scheduling algorithm basing on information and so on.It also analysed these algorithm's strongpoints and shortcomings,at last confirms using GA as the primary method.Secondly, expounding GA's basic concepts,theory and methods, it summarized GA's character and main approach.at the same time it analyzed GA's three basic operations: selection,crossover and mutation. GA is a sort of non-numerical account optimizing method which is based on natural choice and colony genetics. GA express the answer of the problem as character string ,and regard such these character string as manual chromosome or individual, many individual make up of one population. Producing some individual at random form the initial population, through evolving the population continuously and using the natural selection mechanism,which make the individual of the population move to the way where the classic answer of the problem is, finally search them. The individual create individual through genetic arithmetic operators and through defining the individual's evaluating function which we call fitness we can evaluate whether the individual is good or not .The individual's fitness can reflect its acclimation ability, the bigger fitness the stronger the individual's viability. According to the fundamental of natural selection the individual whose fitness is bigger have more chance to be selected to rise upseed. GA is one of the intelligent searching techniques, also the best used dynamic scheduling at present, its advantage is that it can jump from one scheduling to another randomly, thereby it may solve the problem of easily getting into local excellent answer which other technique meet. But GA also has its obvious shortcoming,such as its searching space is big and searching time is long for large-scale combinatorial optimization problem, and also may appear earliness and constringency etc.Thirdly introduce JSSP's mathematic model and its denotation way. One of the most important work which job-shop scheduling problem study is how to process the coding of GA, because JSSP have discrete,dynamic and many other attribute. So the coding of JSSP basing on GA has determinate difficulty which is a bottleneck all along that GA is applied to GA directly. Due to be restricted by the machining courses of working procedure, JSSP is not easy to ensure one nature expression as TSP. One very important subject of GA which is constructed by JSSP is to design a suitable method that can express solution and design a genetic arithmetic operators which base on specific problem, so that all the chromosome which come into being during the evolvement process will produce feasible scheduling, moreover this will be key phase which affect GA's every phase. In the past several years, some JSSP's expression technique has been put forward such as the expression technique basing on working procedure,the expression technique basing on workpiece,the expression technique basing on priority list and so on, which about nine kind methods. This dissertation namely adopt the expression technique basing on working procedure in coding mode.Fourthly this paper puts forward an improved GA that is a sort of GA basing on united integer coding, its main character is to settle a corresponding connection during JSSP's working procedure and a natural subclass, this connection make the process that GA seek the solution same as TSP ,the project this paper puts forward regard all of the working procedure as coding object, uniformly code one replacement from one to p and permit the same workpiece's working procedure use the same machine repeatedly and permit each workpiece have different numerary working procedure. Under the effect of the project which is coding and decoding put forward in This paper, TSP's genetic algorithm basing on city integer coding may be applied on JSSP conveniently. Finally, by testing the standard examples like FT, the announced makespans are obtained, which can prove the new algorithm is better performance on JSSP. This paper also primarily analyze the connection which is problem's complexity and colony size and mutation probability and the generation of evolution ,thus conclude four rules that adjust the running parameters of the genetic algorithm, also offer efficient and intuitionistic reference to adjust running parameters.