A stochastic project scheduling problem with resource constraints

A stochastic project scheduling problem subject to an incompatibility constraint and multiple renewable resource constraints is described by a discrete-time discrete-event dynamic system and modeled as a Markov decision process. The discrete-event dynamic system is observed only at transitions rather than at every time point. The incompatibility constraint prohibits two incompatible jobs from being active at the same time. The jobs are preemptive only when there are completions of other jobs, and may have multiple operating modes. Each mode is associated with a set of resource requirements and a discrete-time job duration distribution. The objective is to minimize the expected project duration. The optimal solution can be obtained by solving a stochastic dynamic program. Some heuristic methods based on reducing the number of feasible actions at the decision epochs are proposed. These heuristics can be applied simultaneously and are shown to decrease the execution times significantly while increasing the expected project duration only slightly.