The research presented in this dissertation addresses the Multi-Mode Resource-Constrained Project Scheduling Problem (MMRCPSP) in the presence of resource
unavailability. This research is motivated by the scheduling of engineering design tasks in
automotive product development to minimize the project completion time, but addresses a
general scheduling situation that is applicable in many contexts.
The current body of MMRCPSP research typically assumes that, 1) individual resource
units are available at all times when assigning tasks to resources and, 2) before assigning tasks
to resources, there must be enough resource availability over time to complete the task without
interruption. In many situations such as assigning engineering design tasks to designers,
resources are not available over the entire project-planning horizon. In the case of engineering
designers and other human resources, unavailability may be due to several reasons such as
vacation, training, or being scheduled to do other tasks outside the project. In addition, when
tasks are scheduled they are often split to accommodate unavailable resources and are not
completed in one continuous time segment. The objectives of this research are to obtain
insight into the types of project scheduling situations where task splitting may result in
significant makespan improvements, and to develop a fast and effective scheduling heuristic
for such situations.
A designed computational experiment was used to gain insight into when task splitting
may provide significant makespan improvements. Problem instances were randomly
generated using a modification of a standard problem generator, and optimally solved with
and without task splitting using a branch and bound algorithm. In total 3,880 problem
instances were solved with and without task splitting. Statistical analysis of the experimental
data reveals that high resource utilization is the most important factor affecting the
improvements obtained by task splitting. The analysis also shows that splitting is more
helpful when resource unavailability occurs in multiple periods of short duration versus fewer
periods of long duration. Another conclusion from the analysis indicates that the project
precedence structure and the number (not amount) of resources used by tasks do not
significantly affect the improvements due to task splitting.
Using the insights from the computational testing, a new heuristic is developed that can
be applied to large problems. The heuristic is an implementation of a simple priority rule-based
heuristic with a new parameter used to control the number of task splits. It is desirable
to obtain the majority of task splitting benefits with the smallest number of split tasks.
Computational experiments are conducted to evaluate its performance against known optimal
solutions for small sized problems. A deterministic version of the heuristic found optimal
solutions for 33% of the problems and a stochastic version found optimal solutions for over
70%. The average percent increase in makespan compared to optimal was 7.58% for the
deterministic heuristic and less than 2% for the stochastic versions demonstrating acceptable
performance. / Graduation date: 2003
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/31495 |
| Date | 14 March 2003 |
| Creators | Buddhakulsomsiri, Jirachai |
| Contributors | Kim, David S. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0018 seconds