Research On Genetic Algorithms For Advanced Planning And Scheduling Problems

Since 1990s, the China's economy which major in manufacture has gotten rapid development. In global context of subprime lending crisis and financial crisis, the challenge that at the same time China's manufacturing industry future faces coexists with the opportunity. The developed countries shift their manufacturing to China to offset the adverse effect brought by their local economic recession, which will bring historic opportunity for the growing and upgrading of the industrial structure of China's manufacturing industry. However, the situation of China's manufacturing technology, especially the key technology which rely mainly on abroad has still not fundamentally changed. Especially in the context of the global economic slowdown caused by the US financial crisis, the external demand for related departments in China's manufacturing industry will drop off, many industries are faced with readjustment. China's manufacturing industry is facing a huge impact and challenges. To make our enterprise in competition invincible, make our country become a strong manufacture country, China manufacturing industry should strengthen the cooperation in the downstream enterprises, upgradation of the technology, management and informationization construction. Through advanced internal production plan and control technology, shorten the production makespan and procurement time, implement coordination and optimization of external supply chain, reduce stock fund, improve production efficiency, realizing the total management improvement, so as to response the serious and complex situation.For a long time, ERP system was widely used by enterprise to manage enterprise operation, and has created a glorious period of ERP practice. However, ERP is mainly for the management of enterprise internal resources, its core logic is based on the assumptions of infinite capacity and fixed lead time. It lack of optimization function, can not reflect the actual situation in the workshop and changes in order, hard to adapt to the changing demands of the modern enterprise, and also can not coordinate resources in multiple enterprises. In order to overcome the shortcomings of traditional ERP planning model, in the mid 1990s, the Advanced Planning and Scheduling (APS) system emerged.APS is the true supply chain optimization engine, it contains a large amount of mathematical models, optimization and simulation technology. It can respond to customer demands promptly, rapidly synchronize plan, provide accurate delivery date, reduce inventory of work in progress and finished product, considering all the constraints of supply chain, identificate potential bottlenecks automaticly, improve resource utilization, so as to improve the overall management level for enterprise. APS has become one of the main means which supporting inter-enterprise coordination.Some problems in the APS system were considered, which involving resources selection and outsourcing, operation sequencing, and transportation planning, in which the application of genetic algorithm has been primary studied. Through the analysis and comparisons between existing approaches, deficiency was found and improved new methods were proposed and verificated in experiment.For an APS problem with outsourcing machines an improved genetic algorithm LSHGA was proposed. In this problem, four stages are needed to satisfy customer demands: manufacturing, assembling, delivery, customers. Each customer order has a due date. Products in each order were manufactured, assembled, and delivered to customers. Each order consists a set of jobs, each job was composed by a set of operations. There may be precedence constraint exists between two operations. Each operation can be processed by a set of alternative machines. Some machines may be outsourcing ones. The objective is to find the optimal operation sequence and machine assignment, to minimize the makespan of all customer orders.In LSHGA, the topological sort algorithm was utilized to generate operation sequences in an order, and a job sequence relaxation strategy was proposed, in which for each order, the precedence constraint between operations in a job was considered, and there is not sequence constraint for operations in different jobs. Using the same bench mark problems and parameters, LSHGA was compared with a classical algorithms, the results show the effectiveness of the proposed strategy. This strategy can produce more alternative operation sequences, and none of the precedence constraint will be violated. Therefore this is an effectiveness strategy to increase the searching space of the algorithm. The results of experiments based on large size problems verified the effectiveness of the algorithm further. To improve the efficiency of LSHGA, a neighborhood search based mutation operator was proposed. For the chromosome represented by two dimensional vector, the perturbation mutation was employed on the machine assignment vector, and the neighborhood search based mutation was employed on the priority assignment vector. Experiment shows that, in LSHGA the mutation operator is the main operator which guide the search direction and plays an important role on improving the search ability of the algorithm.Based on an integrated resource selection and operation sequencing model, a multi-objective APS model. In this problem, an order consists of a set of uninterrupted operations. An operation can be processed on a set of alternative machines. Setup time and teardown time must be considered for each operation and machine. Transportation time must be considered for two machines. There isn't precedence constraint exist for two orders, and there may by precedence constraint between two operations. Each order has lot size. An operation can start as early as its all precedent operations have produced a certain number items, don't need to wait all its precedent operations completed. The process of an operation cann't be interrupted, a machine is nonpreempted. The objectives are: minimizing the makespan, minimizing the total transportation time, and balancing the workload.For this model, a multi-objective genetic algorithm Y-MOGA was proposed. In order to find an approximation of the Pareto optimal set, the proposed algorithm has made use of the principle of nondominated sorting, the fast nondominated sorting algorithm was used to divide the population into several nondominated fronts, then a deterministic selection strategy was employed to form the mating pool. In the choice procedure, for solutions belong to different nondominated fronts, the one belongs to smaller rank number will be preferred, for solutions belong to the same front, the one withe the larger crowding distance will be preferred. In the crowding distance computation procedure, considering the different range for each objective, the value of crowding distance for each objective was normalized, that is, to be scaled to the same range, so as to avoid the crowding distance be dominated by one objective. After crossover and muatation operators were applied on the mating pool, a new population was generated. To improve the search efficiency of the algorithm, a local search procedure was proposed and applied on the nondominated solutions of the new population. In the procedure, based on the crowding distance, only a specified number of solutions were selected for local search. The neighborhood of a solution is generated through insert operator applied on priority assignment vector, and perturbation operator was also applied on machine assignment vector. A nondominated solustions set was kept and updated at each generation. Y-MOGA was compared with the other related algorithms on different size of problems. The results show that, compared with the other two algorithms, Y-MOGA obtained most of the nondominated solutions, and the solutions were closer to the Pareto optimal front. In addition, the experiments based on the practical data verified the effectiveness of Y-MOGA further, and shows that the algorithm can be applied to the practical problems.For a two-stage transport problem, an effective two-population co-evolutionary algorithm TPCEA was proposed. In this problem, there are two stages transportation network. The product are manufactured in plants, and then transported to the distributation centers (DCs), and then to the customers. The maximum number of DCs is constrained due to the limited resource of enterprise. The objective is to determine the subsets of DCs to be opened and to design the transportation network that will satisfy all capacity constraints and the customer demand with minimum cost.In TPCEA, the chromosome is presented by priority based encoding. Each chromosome consists of two segments. Each of the segment is used to obtain a transportation tree of a stage. For each segment, the value of a gene is used to represent the priority of the node for constructing a tree among candidates. The chromosome is decoded on the backward direction. Firstly, transportation tree between opened DCs and customers is obtained with decoding of the second segment of chromosome. Secondly, transportation tree between plants and opened DCs is obtained with decoding of the first segment of chromosome. The transportation tree is generated by sequential arc appending between sources and depots. At each step, only one arc is added to tree by selecting a source or depot with the highest priority and connecting it to a depot or source considering minimum cost. The method of computing cost function affects deeply the overall performance of the algorithm. Therefore, 6 heuristics for computing the cost function were proposed. Through experiments the best combination of heuristics was adopted in the chromosome decoding procedure, That is, for the 2nd stage, unit transportation cost from DCs to customers combined with unit fixed cost of DCs is utilized to calculate the cost, for the 1st stage, unit transportation cost from plants to DCs is utilized as cost. Considering the maximum DCs number constraint, a two-population co-evolution approach was proposed, in which two populations were kept for feasible and infeasible solutions respectively. After crossover and mutation operators applied on the two populations, the new solutions were divided and moved into the two populations by their feasibility respectively, this procedure realized the information interchange between the feasible solutions set and infeasible ones. For the feasible solutions set, roulette wheel selection with elitist strategy was employed as a selection mechanisms. For population consists of infeasible solutions, the solutions were sorted in increasing order of the degree of constraint violation and total cost, then the top best solutions were selected for next generation. This approach make the TPCEA can search solutions from both feasible and infeasible regions, so the optimal solution can be easier to found. The experiments on different size of problems verified the effectiveness of the proposed approach.Comprehensive APS system is complicated. There has been many mature advanced planning systems, but the core of the APS system, i.e. the optimization engine is in still developing. Some domestic enterprises have developed practical systems in manufacturing industry, but only as a supplement of ERP system. There isn't exists domestic APS system which covers all supply chain levels with comprehensive functions. The domestic market is mainly occupied by foreign APS products. There is few research results which has important theoretical and practical significance at home currently. The research work in this paper is expected to play certain promotion effect to domestic APS research, and provides several optional approach for solving practical problems. Therefor, the research in this paper has certain theoretical significance and practical value.