A Study On Project Scheduling Problem And Its Simulation Based On Multi-objective Genetic Algorithm

Managing projects dates back at least4500years. From building the pyramids inEgypt and the Maya temples in South America with the simplest tools, CPM first usedby America DuPont Company and PRET in Polaris Missile Project by America navy,till now, a large number of project management problems on models, algorithms andsystems including some software have been studied to help managers plan, schedule,supervise and control projects.Project scheduling problems, as one of the most important research areas inproject management, dating back to the1960s, have received wide attention from allkinds of specialists and scholars. With the application of modern technology,automation production system makes production more convenient and efficient butmakes project scheduling more difficult almost beyond the wisdom of human.Most project scheduling problems belong to a kind of combinational optimization.The computational complexity theory indicates that many combinatorial optimizationsare NP-hard. Traditional optimization methods in operations research are difficult tosolve these NP-hard with the polynomial computing time needed. Thus theapproximate algorithms, also called heuristic methods, are required.At present, solving the most complex project scheduling problems mainly focuson the study of the meta-heuristic methods, that is, intelligence optimization algorithm,including simulated annealing, tabu search, particle swarm optimization, ant colonyoptimization and evolutionary computation etc.. Intelligence optimization algorithmmimics nature’s phenomenon or procedure to drive its search towards an optimalsolution, appropriate to much more complex nonlinear problems with thecharacteristics of parallel, self-organization, self-learning and self-adaption.Anyway, the researched theories and algorithms serve for their application.Construction industry, as one of the main application area in project management, demands more aiming to itself. In order to help construction enterprises better controlconstructing and improve forecasting so as to avoid unnecessary loss, constructionvirtual prototype technology comes into being.In view of the above mentioned factors, this dissertation tries its best to takemulti-mode resource-constrained project scheduling and its application as researchobjects, and multi-objective genetic algorithm as instrument. The main problems in theresearch are as follows.(1) Though intelligence optimization algorithm can deal with a population ofsolutions, and better approach non-convex or discontinuous Pareto-optimal front, thedynamic adjustment and self-adaptive modification of the designed parameters are stillunder discussion.(2) Solution quality and solving efficiency should be improved further. Based onPareto theory the multi-objective genetic algorithm must construct Pareto optimal setin every run, thus it is necessary to find the least time complexity to design the Paretooptimal set.(3) Time, cost and quality are the important factors in managing projects and canbring the success or failure of the projects. More literatures focus on time-cost tradeoff,and few quality of a project is considered. Though in some studies project schedulingwith time, cost and quality considerations has been mentioned, researchers did not givean all-around design among the three but bounding one or two variables as constant. Itis urgent to build a suitable time-cost-quality tradeoff model and resolve it.(4) Quite a number of uncertain factors exist in the project scheduling problems,which makes them form a dynamic procedure. The research on uncertain is morepractical. It is worth of our thinking to build stochastic or fuzzy network modelsaccording to uncertain state and resolve it.So, with the problems above considered, the main research work and contributionof this dissertation includes:(1) Based on the research on combinatorial optimization and computational complexity, the dissertation compares the positive and negative outcomes from allkinds of different optimization methods, and concludes that the intelligenceoptimization methods are becoming the research tend at present. In resolvingcombinatorial optimization which is quite hard to deal with, the intelligenceoptimization methods improve the ability to find high quality of solutions in thesuitable range of time. Especially, the intelligence optimization methods take muchmore effects on large-scale problems and problems seldom unknown by people.(2) Integrating the theory of combinatorial optimization, the dissertationintroduces a general model of resource-constrained project scheduling problems andtheir classification, gives literatures review based on different methods. It alsoindicates that researching the multi-mode resource-constrained project schedulingproblem is feasible.(3) The dissertation discusses the multi-objective genetic algorithm, including theconstruction of non-dominated sorting, the mechanics of crowding distance assignmentand genetic operations etc.. At the same time, we give a suggestion of self-adaptiveprocedure of multi-objective genetic algorithm by modifying the distribution index andthe population size.(4) Based on analysis of minimizing time, minimizing cost and maximizingquality individually, the interrelation among them and the research scheme are pointedout before the multi-objective models on time-cost-quality tradeoff are formed. Thenthe multi-objective genetic algorithm is applied to the kind of models. Finally theresults gained by simulation show the validity of the applied method. Meanwhile, adecision-making scheme is given based on preference of time, cost and qualityindividually for scheduling a construction project.(5) The dissertation gives a description on models and algorithms of projectscheduling problems under stochastic state, including distribution function and numbercharacteristics of the random variables. It also shows that PERT often undervalues theproject duration which will necessarily bring the risk for managing project. Then, the stochastic multi-objective problems and its mathematics models, resolving methods arestudied. Finally, simulations and conclusions on multi-objective multi-moderesource-constrained scheduling problems are made from the study.(6) Based on the analysis of construction mechanism, the dissertation gives aconsideration on how to integrate the relative scheduling theory into constructionvirtual prototype system from the aspects of integrated platform, developmentenvironment, design steps, and a practical case is made and analyzed in the last.The main innovative researches are included as follows:(1) This dissertation modifies the fixed crossover distribution index, whichmakes the index be capable of self-adaptive adjustment. At the same time also provesthe lower limit of the population size.(2) This dissertation applies multi-objective genetic algorithm to time-cost-qualitytradeoff problems which belong to the type of multi-mode resource-constrained projectscheduling problems, analyzes the optimization mechanism, and proves the validity ofthe improved algorithm from the convergence and distribution.(3) Based on the dynamic change of activity cost and quality with the stochasticactivity duration, the dissertation designs a mechanism of probability conversion andsimulation of random number with integrating the chance-constrained programming,so as to improve the ability of resolving the multi-objective multi-moderesource-constrained stochastic project scheduling problems.As a whole, in case of algorithms, the dissertation starts from the mathematicalmodel of multi-objective genetic algorithms, puts forward two kinds of modificationstrategy. As far as project scheduling is concerned, the dissertation considered thefactor of quality and stochastic environment. The experiments testify theireffectiveness and practicality. The contribution of the dissertation enhances thetheoretical basement of multi-objective optimization theory, enriches the time-costmodels and uncertain network models.