| At present, APS (Advanced planning and scheduling) has drawn a lot of attentions as the hotspot of the enterprise management over the world. The FAW has started the APS project for cutting the production costs and improving the competitive power of the enterprise in order to make a advanced scheduling plan of the production lines including welding, pressing, assembly and painting. This paper is one part of the preliminary research work which subjects to the FAW advanced scheduling plan.APS was developed to deal with problems which take capacity constraint, material constraint and transporting resources constraint into account. It is able to response to customers' order within given time and makes scheduling plans according to constraints. An APS system extracts real-time information (bill of material, customer order, machine capacity, inventory, staff and so on) from supply chain, with which to calculate a feasible solution in the form of schedule tables, resulting in a fast, reliable response to the customers.Because in the APS domain the production scheduling problem belongs to the NP problem, the traditional dispatch algorithm is unable for the solving high complexity question effectively. The genetic algorithm demonstrates the superiority gradually as representative's heuristic search algorithm, but still faced some questions, for example the convergence rate was slow, the algorithm efficiency was not high; the solution is not ideal which is unable to meet the production needs; the solution collection does not distribute well and so on.For solving these problems, this paper has proposed a single-objective genetic algorithm (YSGA) and a multi-objective genetic algorithm (YMGA) on the basis of some classical algorithms. We worked on the improvement of fitness assignment, selection, mutation, crossover and proposed a new mutation strategy with local search, also a new strategy which updates the non-dominated sets. The work of this paper include mainly:(1) Analyse the state of art and the meaning in APS field. Introduce the theory of advanced planning and scheduling in detail.(2) Research on the multi-objective optimal theory and application in genetic algorithm. Analyse the popular genetic algorithms in APS field.(3) Design and implement the single-objective genetic algorithm (YSGA) on the basis of improving the algorithm which is proposed by Lee. And then make experiments.In 2002, Lee has proposed a single-objective genentic algorithm in APS field which considers operation constraint, alternative machines, due date. The result got by Lee is better than other algorithms at that time by improving the choromosome structure and crossover, mutation operations. But Lee just considered operation constraints in each job. This will bring needless constraints which is reducing the number of alternative operations. Along with the growth of scale, Lee' algorithm can not meet the requirement of production.To deal with this model, a new algorithm called YSGA is introduced which is on the basis of improvement of Lee's algorithm in APS field. Our main job is to change the strategy of operation constraint which imposed unnecessary precedence constraints on operations in the same customer order. It can extend the solution space by generating all feasible solutions.YSGA uses two points'crossover operations. An improved operation sequence strategy and a new fitness evaluation method with penalty factor was introduced, also including a local search based on heuristic mutation operator by means of analyzing local information. The local search space is generated by the total ordering of priority in the mutated positions in chromosome. In this paper we just choose three points to be muteted so as to reduce the complexity of local search. A new fitness function is redesigned in order to avoid premature which is generated by super chromosome with large fitness.The experiments were first carried out by comparing the sample which is described in Lee's paper. Results show that YSGA is much better than Lee. After that, various sizes of numerical experiments were carried out to demonstrate the efficiency of the proposed GA and it was found that the YSGA performs much better than Lee's.(4) Design and implement the multi-objective genetic algorithm (YMGA) on the basis of improving the algorithm which is proposed by Jose. And then make experiments.In 2004, Jose has proposed a multi-objective genetic algorithm for flowshop. It has following feathers: restore non-dominated solutions inouter set; classify Pareto fronts by dominated relations; introduce crowding distance to fitness assignment which can get the information of population density; use local search to change non-dominated set based on Pareto. JOSE has made great progress, but it does not normalize the crowding distance in different object. This results in premature situations.In each generation, we use a deterministic approach to select certain solutions from populations and outer set in order to form the mating pool. In the selection procedure, we use following preferences: for solutions in different non-dominated front, the one in the front with smaller rank number is better; for solutions in the same non-dominated front, the one with larger crowding distance is better.We use different mutation operator on each vector of the chromosome to enhance global and local search ability. For the machine assignment vector, we used perturbation operator, which randomly selects several operations and reselects their machines. The mutation operator used for the priority assignment vector is the insertion operator, which randomly selects a priority and inserts it into a random position of the priority sequence. Some genetic positions which are not mutated will move right so as to form feasible solutions.We have proposedε-equal concept at first. The YMGA algorithm reduces the non-dominated set byε-distance. This makes the non-dominated front well-distributed with expending the area controlled by non-dominated set.(5) Experiments.We have made a lot of experiments on different samples. We combine four Pareto results generated by four algorithms to form set R and then remove dominated solutions from it. Results shows that the solutions generated by YMGA can dominate other three classical algorithms in a great portation and behave well in inversity. With the growth of our sample's scale and complication, YMGA have better performance.This paper has a matter of certain significance in APS field especially with complicated and large scale problems. |
PDF Full Text Request