Robust Execution Strategy for Scheduling under Uncertainty

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