Title page for ETD etd-03272008-111019

Type of Document

Master's Thesis

Author

Rudolph, Adam J,

URN

etd-03272008-111019

Title

An Algorithm for Determining Optimal Resource Allocation in Stochastic Activity Networks

Degree

Master of Science

Graduate Program

Operations Research

Advisory Committee

Advisor Name	Title
Dr. Salah E. Elmaghraby	Committee Chair
Dr Julie Ivy	Committee Member
Dr. Subhashis Ghosal	Committee Member

Keywords

activity networks
stochastic optimization
project scheduling
resource allocation
phase type distribution

Date of Defense

2008-03-24

Availability

unrestricted

Abstract

The problem we investigate deals with the optimal assignment of resources to the
activities of a stochastic project network. We seek to minimize the expected cost of the
project, which we take as the sum of resource utilization costs and lateness costs, if the
project is completed after a specified due date. These costs are both functions of the resource
allocations to the activities with opposite responses to changes in allocation. We assume that
the work content required by the activities follows an exponential distribution. An
immediate result of this assumption is that the duration of the activities also follows an
exponential distribution based on the degree of resource allocation. We construct a
continuous time Markov chain (CTMC) model for the activity network and use the Phase-
Type (PH-type) distribution to evaluate the project completion time.
Absence of an analytically tractable means of evaluating the sensitivity of the project
cost to variation in the resource allocation to an individual activity led us to develop a
derivative descent algorithm for the optimization of the expected cost of the project. We
approximate the value of the derivative at a particular allocation by evaluating the differential
cost of a slightly modified allocation. These quasi-derivatives led to the selection of an
activity to which we optimize resource allocation. We use Fibonacci search over the interval
of permissible allocations to the activity to seek the minimum expected cost. This iterative
process of activity selection followed by changing the resource allocation is repeated until
the expected cost is not significantly decreased. Finally, through extensive experimentation
with a variety of projects of different structure and size, we show that this algorithm yields
promising results in terms of both computation time and accuracy.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	etd.pdf	632.40 Kb	00:02:55	00:01:30	00:01:19	00:00:39	00:00:03