Resource Constrained Project Scheduling Problems with minimum and maximum time lags (RCPSP/max) provides a general model for resource scheduling in many real-world problems (such as manufacturing and construction engineering). Due to its practical importance and generality, providing effective algorithms and scalable solutions for RCPSP/max is a topic of growing research. Traditional methods have addressed deterministic models with all parameters known with certainty. In this thesis, we are concerned with RCPSP/max problems in an uncertain environment where durations of activities are stochastic and resource availabilities are subject to unforeseen breakdowns.
We propose methods for generating robust execution strategy to protect against uncertainty. Given a level of risk prescribed by the planner, we investigate the problem of computing the minimum probability-guaranteed makespan (i.e. Robust Makespan) and propose methods for generating an execution strategy such that when uncertainty is dynamically realized, any schedule instantiated from the execution strategy will be guaranteed to finish within the robust makespan with the given level of confidence (or risk).
To the end, we first introduce and study the properties of a decision rule used to compute the start times of all activities with respect to execution strategies and dynamic realizations of uncertainty. Based on the decision rule, we derive the expression for robust makespan of an execution strategy as a quantitative and exact measurement of robustness and propose methods for generating execution strategy with the best robust makespan. To improve performance of local search, we provide enhancements that exploit temporal dependencies between activities. Our experimental results illustrate that robust local search is able to provide robust execution strategies efficiently. We then apply our methodology in the MRO industry context and provide the planner candidate execution strategy based on his own attitude to risk.
Next, we deal with the additional consideration of resource uncertainty due to resource breakdown and repair. We propose different chaining procedures and compute robust resource allocations by predicting the effect on robustness of generated strategies. We incorporate such information into robust local search and propose methods for generating execution strategies that can better absorb resource and durational uncertainties. Experiments show that our proposed model is capable of addressing uncertainties of both resources and durations and the most robust execution strategy is generated by the chaining procedure that takes into account of both mean and variance values of the effect of resource breakdown.
Finally, we apply our model to the service industry context and add visibility from a risk management perspective to the service provider by computing the robust cost of business processes.
|Advisor:||Lau, Hoong Chuin|
|Commitee:||Cheng, Shih-Fen, Lim, Yun Fong, Varakantham, Pradeep Reddy|
|School:||Singapore Management University (Singapore)|
|Department:||School of Information Systems|
|School Location:||Republic of Singapore|
|Source:||DAI-B 74/01(E), Dissertation Abstracts International|
|Keywords:||Large scale optimization, Local search, Project scheduling, Risk management, Robustness, Scheduling under uncertainty|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be