Scheduling with Contingent Resources and Tasks

Abstract

Finding optimal schedules for the most commonly considered classes of scheduling problems is NP-complete. Best algorithms scale up to very large scheduling problems when optimality is not required and good solution quality suffices. These problems have perfect information in the sense that the resource availability, set of tasks, task duration, and other important facts, are fully known at the time of constructing a schedule. However, the assumption of perfect information is rarely satisfied, and real-world scheduling faces several forms of uncertainty, most notably with respect to durations and availability of resources. The effective handling of uncertainty is a major issue in applying scheduling in new areas. In this work, we investigate the properties of a number of classes of problems of contingent scheduling, in which assignments of resources to tasks depend on resource availability and other facts that are only known fully during execution, and hence the off-line construction of one fixed schedule is insufficient. We show that contingent scheduling in most general cases is most likely outside the complexity class NP, and resides, depending on the assumptions, in PSPACE, Sigma-p-2 or Pi-p-2. The results prove that standard constraint-satisfaction and SAT frameworks are in general not straightforwardly applicable to contingent scheduling.