The Study On Critical Path Problem In Stochastic Environment

The critical path problem is the time to complete the longest path from thesource node to the destination node in the activity network. In realistic criticalpath problem, people shorten project completion time by prehiring additional laboror paying additional money, then we consider that how balance the relationshipbetween the completion time and the total costs. However, all the activities com-pletion time of the project is uncertain, so we should employ stochastic theory todeal with randomness in critical path problem.This thesis first presents a new class of two-stage stochastic insuring criticalpath problem based on probability criterion. In the case that all the activitiescompletion time of the project is general stochastic variable, we suggest sampleaverage approximation method to reformulate the original problem as a new0–1mixed-integer programming problem. To solve the proposed model, we designa new hybrid algorithm by combining dynamic programming method (DPM) andgenotype-phenotype-neighborhood based binary particle swarm optimization (GPN-BPSO). Because of the difcult of determining the probability distributions in real-istic critical path problem, we develop a new class of two-stage stochastic insuringcritical path problems with value-at-risk (VaR) criterion. When all the activitiescompletion time of the project is general stochastic variable, we use stochastic sim-ulation method to estimate VaR. In this case, we design a new hybrid algorithm bycombining DPM and binary particle swarm optimization (BPSO) to solve the pro-posed model. Finally, we further illustrate the efectiveness of the proposed solutionmethod by comparing with some numerical experiments of some other algorithm.The major new results of this thesis include the following four aspects:(i) Twonovel classes of two-stage stochastic insuring critical path problems are proposed;(ii) Two kinds of important indexes are defined, and some numerical experimentsare performed to demonstrate the necessary of solving stochastic problem;(iii) Inthe cases that all the activities completion time of the project is general stochasticvariable, the proposed models can be turned into their deterministic equivalent ones; (iv) Two hybrid algorithms are designed to solve the proposed models, and comparedwith some numerical experiments of some other algorithms, they are provided toillustrate the efectiveness of the proposed hybrid algorithms.