دانلود رایگان ترجمه مقاله مدل احتمال جدید برای ضمانت کردن مشکل مسیر بحرانی با الگوریتم اکتشافی (نشریه الزویر 2015)

مدل احتمال جدید برای ضمانت کردن مشکل مسیر بحرانی با الگوریتم اکتشافی

A new probability model for insuring critical path problem with heuristic algorithm

Abstract

In order to obtain an adequate description of risk aversion for insuring critical path problem, this paper develops a new class of two-stage minimum risk problems. The first-stage objective function is to minimize the probability of total costs exceeding a predetermined threshold value, while the second-stage objective function is to maximize the insured task durations. For general task duration distributions, we adapt sample average approximation (SAA) method to probability objective function. The resulting SAA problem is a two-stage integer programming model, in which the analytical expression of second-stage value function is unavailable, we cannot solve it by conventional optimization algorithms. To avoid this difficulty, we design a new hybrid algorithm by combining dynamic programming method (DPM) and genotype-phenotype-neighborhood based binary particle swarm optimization (GPN-BPSO), where the DPM is employed to find the critical path in the second-stage programming problem. We conduct some numerical experiments via a critical path problem with 30 nodes and 42 arcs, and discuss the proposed risk averse model and the experimental results obtained by hybrid GPN-BPSO, hybrid genetic algorithm (GA) and hybrid BPSO. The computational results show that hybrid GPN-BPSO achieves the better performance than hybrid GA and hybrid BPSO, and the proposed critical path model is important for risk averse decision makers.

1 Introduction

In a complex project management problem, we often use a directed network graph to describe various tasks and the relationships among the tasks. In this framework, the arcs represent dependent tasks and the arc weights serve as associated task durations. Also, there exists a node 0 representing the start of the project and a node n representing its termination. A project can be considered completed if all its activities have been finished. An important theoretical result is that the minimum time to complete all the activities in the activity network equals to the length of the longest path from the source node to the destination node [1]. Thus, this path, called critical path, represents the sequence of activities, which will take the longest time to complete. Chen et al. [2] developed a polynomial time algorithm to find the critical path and analyzed the float of each arc in a time-constrained activity network. Guerriero and Talarico [3] proposed a general method to find the critical path in a deterministic activity-on-the-arc network, considering three different types of time constraints. Another area of research dealt with the stochastic nature of activity time. For example, Kelley [4,5] and Moehring [6] estimated the probability that a project would be completed by a given deadline if the duration for each activity is not known with certainty; Burt and Garman [7], Bowman [8] and Mitchell and Klastorin [9] treated mass uncertain information by heuristicbased and Monte Carlo simulation-based techniques, and Shen et al. [10] proposed expectation and chance-constrained models for insuring critical path problems and designed decomposition strategies to solve these models