In this chapter, we address stochastic scheduling problems with general distributed activity durations. Markov models have been proposed for this class of problems with the drawback of being limited to exponential activity durations. The proposed ap- proach aims at estimating the distribution of the makespan of an activity network with general distributed activity durations by means of a continuous-time markov chain and the associated time to absorption using phase-type approximations for non exponential distributions. © 2014 Nova Science Publishers, Inc.