Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network

摘要：

　　In this paper, we propose a randomized approximation scheme for computing expectation of the critical path length in a stochastic directed acyclic network. Our algorithm is based on the Markov chain Monte Carlo method, and our scheme returns an approximate solution, for which the size of error satisfies a given error rate. We propose a Markov chain and a perfect sampling algorithm based on coupling from the past method.

关键词： PERT critical path Markov chain Monte Carlo perfect sampling coupling from the past randomized approximation scheme

作者: Daisuke YAMAGUCHI Tomomi MATSUI

作者单位: Department of Information and System Engineering,Faculty of Science and Engineering, Chuo University,Kasuga, Bunkyo-ku, Tokyo 112-8551, Japan

会议类型: 国际会议

会议名称: 第8届国际最优化方法及应用大会

会议地点: 上海

会议语种:英文

页码: 309-310

在线出版日期: 2010-12-10（万方平台首次上网日期，不代表论文的发表时间）