Agent-based heuristics for large, multiple-mode, resource-constrained project scheduling problems

Persistent Link:
http://hdl.handle.net/10150/282833
Title:
Agent-based heuristics for large, multiple-mode, resource-constrained project scheduling problems
Author:
Knotts, Gary Wayne, 1962-
Issue Date:
1998
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
In this dissertation we address large, multiple-mode, resource-constrained project scheduling problems with the objective of minimizing makespan. After noting that projects often fail and new research is needed, we provide the formal definition of the resource-constrained project scheduling problem and review the existing literature. We then introduce a new model based on digital electronics. We conceptualize our model using agent technology and discuss it as extension of existing models with more representational power. We also describe how our model supports distributed planning. After implementing our model, we conduct two computational studies. In the first, we develop two agent types: basic and enhanced where the enhanced agent is more sophisticated in selecting an activity execution mode. We apply these agents to the scheduling of 500 instances of a small project originally published by Maroto and Tormos (1994). We evaluate the performance of the agents in conjunction with their use of eight heuristic prioritization rules: shortest and longest processing time, fewest and most immediate successors, smallest and greatest resource demand, earliest start time, and earliest due date. Our results show that enhanced agents consistently outperform basic agents while the results regarding priority rules were mixed. In the second computational study, we further develop our enhanced agents by providing still more sophisticated mode selection. We also evaluate static versus dynamic prioritization and two more priority rules: shortest and longest duration critical path. For this study we generated 2500, 5000, 7500, and 10000 activity projects. For each of these, we generated networks with complexities of 1.5, 1.8, and 2.1. For these twelve networks, we generated 20 problem instances for every possible combination of resource factor = 0.25, 0.50, 0.75, 1.0 and resource strength = 0.2, 0.5, 0.8. We graphically evaluated scheduling performance, computation times, and failure rates and conducted an extensive statistical analysis. We found that enhanced agents using shortest processing time priority consistently produced the shortest schedules. However, these agents fail more often than basic agents. We found that dynamic prioritization requires more computation time, but provides little improvement in scheduling performance. We conclude this work with suggestions for future research.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Operations Research.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Industrial Management
Degree Grantor:
University of Arizona
Advisor:
Dror, Moshe

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleAgent-based heuristics for large, multiple-mode, resource-constrained project scheduling problemsen_US
dc.creatorKnotts, Gary Wayne, 1962-en_US
dc.contributor.authorKnotts, Gary Wayne, 1962-en_US
dc.date.issued1998en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractIn this dissertation we address large, multiple-mode, resource-constrained project scheduling problems with the objective of minimizing makespan. After noting that projects often fail and new research is needed, we provide the formal definition of the resource-constrained project scheduling problem and review the existing literature. We then introduce a new model based on digital electronics. We conceptualize our model using agent technology and discuss it as extension of existing models with more representational power. We also describe how our model supports distributed planning. After implementing our model, we conduct two computational studies. In the first, we develop two agent types: basic and enhanced where the enhanced agent is more sophisticated in selecting an activity execution mode. We apply these agents to the scheduling of 500 instances of a small project originally published by Maroto and Tormos (1994). We evaluate the performance of the agents in conjunction with their use of eight heuristic prioritization rules: shortest and longest processing time, fewest and most immediate successors, smallest and greatest resource demand, earliest start time, and earliest due date. Our results show that enhanced agents consistently outperform basic agents while the results regarding priority rules were mixed. In the second computational study, we further develop our enhanced agents by providing still more sophisticated mode selection. We also evaluate static versus dynamic prioritization and two more priority rules: shortest and longest duration critical path. For this study we generated 2500, 5000, 7500, and 10000 activity projects. For each of these, we generated networks with complexities of 1.5, 1.8, and 2.1. For these twelve networks, we generated 20 problem instances for every possible combination of resource factor = 0.25, 0.50, 0.75, 1.0 and resource strength = 0.2, 0.5, 0.8. We graphically evaluated scheduling performance, computation times, and failure rates and conducted an extensive statistical analysis. We found that enhanced agents using shortest processing time priority consistently produced the shortest schedules. However, these agents fail more often than basic agents. We found that dynamic prioritization requires more computation time, but provides little improvement in scheduling performance. We conclude this work with suggestions for future research.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectOperations Research.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineIndustrial Managementen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorDror, Mosheen_US
dc.identifier.proquest9912140en_US
dc.identifier.bibrecord.b39124514en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.