Application And Study Of Genetic Algorithm In Program Evaluation And Review Technique

Program Evaluation and Review Technique is one kind of the science plans management technology origin from 1950's,which considers from the mission progress,describes the ideas of the technology adopted in the process and their inherent coordination relation,and give the organization management technique harmonizing balance between needing and may unceasingly in an attempt waiting for resource to the technology by building strict system of post responsibility and giving full scope to mass line sufficiently.It's core is network planning techniques.While in network planning techniques,the core and the most complicated problem are optimization of the network plan,which decides the profit of the project.Generally,in the long-term practice,the methods of network plan technologyand Mathematics Planning are used in network planning optimization usually.However,there are many shortcomings in those methods.Genetic algorithm is an efficient method of parallel searching.Genetic algorithm is used to deal with the problem of separated optimization search.Usually,it does not request the continuity of question space and the gradient information.Meanwhile it's robustness has been confirmed.It has got remarkable achievements in the handling optimization issues of large and complex.So it has incomparable advantages compared with other methods in addressing the large network optimization problem.In the program evaluation and review technique,the network optimizing problem is a straggling combinatorial optimization problem as for the angle optimizing a problem classifying.In many years of experience application,the network planning optimization has adopted fundamental method such as network planning techniques and mathematics plan.By now there are some methods to solve the network planning optimization problem such as network planning techniques, branch and bound algorithm,heuristic algorithm,intelligent optimization algorithm and so on.1.Network planning techniquesThe most common method of network planning progress optimization is that the sustained time forcing to shorten algorithm,adopting measure uses the network plan brought forward by Bai Sijun as far as possible in 2003.Studying the train of thought is also centered on the ceaseless improvement at present about that the time limit for a project rate of progress optimizes method's forcing to shorten algorithm,striving for the project time limit while optimizing,makes what be increased by extra cost minimal.Wu Yuhua has suggested that route of cut set of equal rank differences follow the algorithm resolving the time limit for a project optimization.Liu Jinming applies "the maximum stream minimum to intercept" the algorithm train of thought that the time limit for a project optimizes when theory has studied time limit for a project one cost nonlinearly change.With modern information technology gradually mature,use the Management scientist and so on to be able to promptly seek out the optimum result optimizing based on compelling the algorithm compressing.2.Branch and bound algorithmBranch and bound algorithm is one kind of effective method to solve NP-hard problem,whose fundamental thought is to make use of reconnaissance tree with problem solution space according to that certain regulation carves up branch process,the method making use of the rational demarcation again removes those carrying out the demarcation process who searches for unnecessarily again,realizes the purpose reducing effective searching space.3.Heuristic algorithmThe heuristic algorithm has preferential regulation-based heuristic algorithm and sampling algorithm mainly.Owing to preferential regulation heuristic algorithm,this is composed of two key elements:The plan generates the scheme and preferential regulation.The plan generates a scheme but is serial controller scheme(Serial Scheduling Scheme mark,is called SSS)and the concurrence controller scheme for short(Parallel Scheduling Scheme,shorter form PSS),(two methods all are to carry out expansion on a incomplete plan,until generating a complete plan. Sampling Algorithm using one kind of plan to generate the scheme and a preferential regulation. Use the priority modulus directly,do not but be that v(j)calculates the probability~φ(j)that the j working is managed,basisφ(j)manages job in En again according to priority modulus in the process of controller.Different according toφ(j),the sampling algorithm may be random sampling algorithm(Random Sampling mark,being called RS)for short,as well as random sampling algorithm(Biased Random Sampling having preference,be called BRS for short)and regret that the value random sampling is algorithmic because of(Regret-Based Random Sampling, shorter form RBRS).4.Intelligent optimization algorithmIn recent years simulating anneal(Simulated annealing,is called SA),taboo for short searching for(Tabu Search,is called TS)and the inheritance algorithm(Genetic algorithm for short,shorter form GA)and other intelligent optimization algorithms have demonstrated stronger ability in the respect of finding the solution constituting the optimization problem,having also had a few to apply in the network plan optimizes aspect in finding the solution.Include the following key element mainly specifically for the intelligence that the network plan optimizes an algorithm:(1) encode,according to that some kind of rule of correspondence and feasible controller only plan a group of code responding to relatively;(2)decode,adopt certain regulation to change code into the process that the feasible controller plans;(3)The initial solution,adopt a group of code that method gets others,corresponding initial can be carried out manages a plan;(4)neighborhood,all new coded aggregation can by the operation that the solution,a group of code define especially process single-step.Especially among them,the application with network planning techniques is most broad,but application value of the model in a certain extent.The paper has study on network planning optimization in PERT based on improved GA.They are the most difficult part of the paper that the integrated optimization of.single project plan network and multi-project network plan optimization.Also those are the innovative points of the paper.These innovative points are as follows:1.The paper studies the optimization of resources of single project networks and proposes the optimizing way using the improved GA.The paper establishes comprehensive optimization model to the problem of resources balanced and the problem of shortest time limit for a project when resources limited;First of all resource-constrained optimization of the cost,and then balanced optimization of resources. Resource-constrained optimization method the cost of the cost optimization and limited resources shortest time optimization methods for organic integration in the evolutionary process of the former for the latter to provide the time and resources to the work of the information and choose individual standard information,which provided for the former resource constraints,cost optimization makes in the course of each individual can meet the resource constraints,and ultimately sought to meet the minimum cost of constraint conditions.The second step is mainly for a balanced optimization of resources.From the first step it is expected to cost as well as working hours and other information,using a fixed time limit,balanced optimization of resources optimization method.Examples show that the method can be carried out in coordination between the various goals and achieved better overall optimization results.2.Building a new optimization model to solve the resource-constrained multi-project scheduling problem,put forward a new improved genetic algorithm optimization method.Dynamic through the establishment of cross linked list to store all project work in the interaction between the binding relationship,and then all projects will be mixed together the work of coding.Initialization conducted in two parts,the first of more than 10 kinds of the more common heuristic method,in accordance with heuristic rules to generate part of chromosomes, and then randomly select the applications that are used to generate part of another chromosome. Genetic Operators extensive search operation based on the crossover operator and search based on the neighborhood mutation operator,the evaluation function by weight coefficient of the three expected objectives into a weighted goal on the final results of the evaluation process.Select operator proportional selection and optimal preservation strategy of combining method.This method overcomes the two-tier model of certain deficiencies in the decision-making,and does not require network in the preparation of plans by adding virtual work will be all the network plans for a merger.Experimental results show that this method with other than 15 kinds of heuristic method has achieved positive results of the optimization.3.Give out the resource-constrained multi-project scheduling optimization and resource optimization problem with a balanced combination of dual-objective optimization methods.First on the network plan the allocation of resources has been optimized,the issue is divided into two types,one is a fixed time limit under balanced optimization of resources to address a wide range of resources balanced optimization problems;The other is the shortest construction period of there is existing the certain defect in method owing to upper tradition of perception speculate and logic analysis basis.First,it has the very strong pertinence when resolving network plan each problem in optimizing,can not resolve the many-sided problem at the same time;Second,it's job is numerous in treatment,efficiency is lower time complicated problem of logic;At the same time, many models and method all is a kind of type network plan owing to very concrete certain,can not apply to all construction projects but.Network optimization problem thinking that the job is numerous with regard to,the logic is complicated therefore,the tradition various optimizes method if linear program simple shape algorithm,nonlinearly branch and bound algorithm, dynamic programming algorithm,various heuristic algorithm,fill grain eliminating peak algorithm and so on,have no way to bear it's calculate complicated degree in general,the effect optimizing moreover accepts certain restricting,that's the reason that the paper come to study the network plan optimizes a problem choosing with inheritance algorithm.The thesis makes use of inheritance algorithm to carry out the content studying,mainly on the problem of planning optimization in the program evaluation and review technique as follows:First it expatiates the basic concept and status quo of project scheduling,discusses the class of project scheduling and math model and dissertates the effective and academic gist-Pattern Theorem and Building Block Hypothesis.Second the paper describes the application and study of single project network planning scheduling optimization based on the improved GA in detail.1.The paper studies the optimization of resources of single project networks and establishes genetic algorithm model to the problem of resources balanced and the problem of shortest time limit for a project when resources limited;2.The paper studies the time cost optimization problem.Aiming at two kind of common relational types of the continuous type and the separation type of time and cost,it designs optimized solutions for GA respectively;3.The paper builds up a multi-purpose integrated genetic algorithm optimization models to the time,costs and resources three goals for integrated optimization.In each of those problems, examples of the application of genetic algorithms are pointed out in the paper for the certification.The paper discusses the application and study on multi-project network planning scheduling optimization using improved GA.1.Building a new optimization model to solve the resource-constrained multi-project scheduling problem,put forward a new improved genetic algorithm optimization method,comparative and analysis with other heuristic methods;2.Proposing the GA based on multi-project resource equilibrium optimization;3.Balance time and resources for the establishment of a comprehensive optimization model optimization,combined with application examples,by the results of comparative analysis in this paper proved the correctness of the algorithm design and efficiency.The paper analyses every model using cases,the result of analysis and calculation is not only verify the validity of the model and the efficiency on getting the solution but also prove the limited resources optimization,in reference to previous literature on the basis of effective use of the hybrid genetic algorithm for the problem.Then the network costs in the plan has been optimized,cost optimization for the duration of work and costs between the two types in common -continuous and linear type,are given in the corresponding genetic algorithm opfmization results show that,After optimization of resources not only a more balanced,but also like some type of resources.