On scheduling and resource allocation problems with uncertainty

We analyze scheduling problems in the stochastic online scheduling environment. In this environment, information on the future arrival of a job is unknown until the job arrives at the system; and the processing requirement of a job remains uncertain until the job is finished. Our goal was to identify online algorithms with attractive asymptotic performance ratios. Under some mild probabilistic assumptions, we first showed that any nondelay algorithm is asymptotically optimal for stochastic online single machine problem, uniform parallel machine problem and flow shop problem with the objective of minimizing the total weighted completion time. We then extended these results to a more general realm and illustrated the significance and practical usage by giving examples. Our simulation studies on these problems and the stochastic online job shop and open shop problems show that two generic nondelay algorithms converge very fast. The simulation results also suggest that, compared with the total weighted completion time metric, the total weighted flow time metric and total weighted stretch metric are more sensitive and may be better performance measures in the online scheduling environment.; We also present a new approach to strategic facility location planning. In this approach, decision makers identify a number of future scenarios and estimate the likelihood of each scenario occurring. We then used the model to find a solution that minimizes the expected regret with respect to an endogenously selected subset of worst-case scenarios whose collective probability of occurrence is exactly 1-alpha. Our new model, alpha-reliable meanAccess regret, has a number of advantages over the existing alpha-reliable p-median minimax regret model. First, by definition, alpha-reliable meanAccess regret is an upper bound of the corresponding alpha-reliable p-median minimax regret. Therefore, minimizing alpha-reliable meanAccess regret will also lead to a low alpha-reliable p-median minimax regret. Second, minimization of alpha-reliable meanAccess regret avoids the dangerous increase in the worst-case regret. Third, the alpha-reliable meanAccess model is computationally much easier to solve. All of these advantages have been demonstrated by our numerical experiments.