برنامه ریزی پویا در فضای حالت کشاف محدود: یک برنامه زمان بندی پروژه با منابع محدود تصادفی

The resource-constrained project scheduling problem (RCPSP) is a significant challenge in highly regulated industries, such as pharmaceuticals and agrochemicals, where a large number of candidate new products must undergo a set of tests for certification. We propose a novel way of addressing the uncertainties in the RCPSP including the uncertainties in task durations and costs, as well as uncertainties in the results of tasks (success or failure) by using a discrete time Markov chain, which enables us to model probabilistic correlation of the uncertain parameters. The resulting stochastic optimization problem can be solved by using dynamic programming, but the computational load renders this impractical. Instead, we develop a new way to combine heuristic solutions through dynamic programming in the state space that the heuristics generate. The proposed approach is tested on a simplified version of RCPSP that has a fairly complicated stochastic nature, with 1,214,693,756 possible parameter realizations (scenarios), and involves five projects and 17 tasks. As a result, an on-line policy is obtained, which can use the information states in on-line decision making and improve the heuristics rather than a fixed solution obtained by the previous mathematical programming (MILP) problem formulations.

A challenge in highly regulated industries, such as pharmaceuticals and agrochemicals, is the process of selecting, developing, and efficiently manufacturing new products that emerge from the discovery phase. Candidate products must undergo a set of tests related to safety, efficacy, and environmental impact, to obtain certification. The problem of scheduling these tasks and associated analysis can be considered as a generalization of the well-known job shop scheduling problem. The case in which all the problem data have known values belongs to the NP-hard class of combinatorial problems (Blazewicz, Lenstra, & Kan, 1983). In general, task success or failure is uncertain and the time value of project reward varies, which adds more complexity to the scheduling problem. In a specialized R&D pipeline management problem, the time value of project reward decreases as the time to introduction of the product increases due to incoming competitive products and fixed patent periods. Hence a company has to manage its various resources, manpower, lab space, capital, pilot facilities, etc. to ensure its best return on its new product pipeline, with the added complication that the outcome of tasks is uncertain. Besides the uncertainty about the success of the task, there are several additional uncertain parameters in real problems, such as uncertainties in task duration and resource (cost) requirement. The project scheduling problem with unlimited resource (Schmidt & Grossmann, 1996) was introduced to the process systems engineering area using a mathematical programming (MILP) based solution approach. In the case of unlimited resource, the overall objective function (net present value) of the problem can be separated into the individual objective functions of each project since one project does not influence the others. There has been significant progress in solution methods Blau et al., 2000, Jain and Grossmann, 1999, Maravelias and Grossmann, 2001 and Rogers et al., 2002 for the problem with resource constraints as well as uncertainty in the task outcome. However, previous solution methods for resource-constrained project scheduling problem (RCPSP) have considered only a subset of the potential uncertainties and have been based on mathematical programming techniques. Even though the mathematical programming approach can account for uncertainties of the problem via scenario generation, the approach is limited to a fairly small number of scenarios due to the exponential increase in the computational load. Limitations in the mathematical programming approach lie not only in the computational tractability but also in the awkwardness in capturing richer representations of uncertainty. Notable exceptions are Subramanian et al., 2000, Subramanian et al., 2001 and Subramanian et al., 2003, where a broader set of uncertainties in the problem are addressed within a simulation and optimization (SIMOPT) framework. The SIMOPT framework developed in Subramanian et al., 2000, Subramanian et al., 2001 and Subramanian et al., 2003 achieved substantial improvement in combining stochastic simulation and optimization by taking a discrete-event dynamic system’s view of the RCPSP. However, outer iteration process of the SIMOPT where constraints are added to the MILP to steer it away from decisions that gave poor outcomes in simulation cannot does not fully and rigorously account for the way information and outcomes can influence the decisions. In this study, we address the uncertainties in the RCPSP using a discrete time Markov chain, which enables us to model correlations among the uncertain parameters. For example, the probability of success of a future task may not be independent of the outcomes of current or previous tasks. Furthermore, a novel solution method, dynamic programming in a heuristically confined state space developed and illustrated in Choi et al., 2002b, Choi et al., 2002a and Choi et al., 2003, is tailored to the problem to obtain high quality solutions. The proposed approach is focused on solving the RCPSP as a multi-stage on-line decision making problem. Finally, the proposed approach is demonstrated by effectively solving a fairly complex stochastic RCPSP that can have up to 1.2 billion different outcomes depending on realization of the uncertainty.

A stochastic resource-constrained project scheduling problem (sRCPSP) has been addressed by using Markov chains to model key uncertainties (the duration, cost, and result of a task). To solve the problem, a DP formulation has been developed with the appropriate definitions of state, including the information state variables, state transition rules, and actions. The conventional stochastic DP approach cannot be used as a solution method for the problem due to the enormous state space. A novel algorithmic framework, DP in a heuristically confined state space (Choi et al., 2002a), was tailored for the problem. The algorithmic framework has been tested by solving an illustrative SRCPSP with significant stochastic complexity. By simulating the problem with three heuristic policies, we obtained a set of visited states, which corresponds to only about 0.00016% of the entire state space. We then performed DP over the states with reasonable computation time. The policy obtained by solving the DP showed superior performance to any of three heuristic policies. Indeed, the solution obtained by the policy on average outperformed the best heuristic solution chosen for each different realization. Furthermore, the robustness of the policy was confirmed by solving the problem with a different set of realizations, data of which were not used to create the policy. The proposed algorithmic framework, DP in a heuristically confined state space, is a general solution approach that can handle a much wider class of sRCPSP. For example, including decisions to cancel an on-going project (Rogers et al., 2002) is an important issue in problems in which new projects arrive during the scheduling period. This feature can be incorporated into our methodology by providing a reasonable way to represent project arrivals within the state space framework. Some extensions of the proposed approach needed to handle more realistic RCPSPs were discussed in Section 7. Beyond sRCPSPs, the algorithm approach presented may have applicability in supply chain planning and process design (Cheng, Subrahmanian, & Westerberg, 2003).