Scheduling in the Face of Uncertain Resource Consumption And Utility

Abstract. We discuss the problem of scheduling tasks that consume uncertain amounts of a resource with known capacity and where the tasks have uncertain utility. In these circumstances, we would like to find schedules that exceed a lower bound on the expected utility when executed. We show that the problems are N P-complete, and present some results that characterize the behavior of some simple heuristics over a variety of problem classes.