(610d) A Continuous Approach to Multi-Mode Resource Project Scheduling

In any enterprise the solution to every decision related problem has the objective of maximizing some measure of profit. Many such problems can be reduced to the so-called Resource Project Scheduling Problem (RCPSP) due to their time dependence and resource constraints. Of the different types of RCPSP the multi mode case displays the most realistic picture of the decision options involved in today's highly flexible business environment. Different levels of renewable resources (i.e. personal, equipment, etc) can be allocated to the same activity depending on the ?state of the world? at each time period. However, the indexing approach used in the literature to handle renewable resources has a major scaling limitation, in terms of the number of decisions and allocation levels that can be considered, due to its combinatorial nature. Also, the use of reduced sets of levels to make some of the problems tractable is an unreliable strategy. It is not really possible to predict which part of the solution space is disregarded when selecting the set. Therefore, the lack of resolution or the inadequate range size of the decision space may generate solutions that are far from optimal. In this work we present a series of mathematical formulation that overcome such issues by using a continuous representation for renewable resources. The idea here is that the number of resources in a real life size problem is in the hundreds and therefore rounding will not significantly degrade the optimality of the solution. The proposed approaches are based on the use of ?balances? that keep track of each resource usage in a way similar to a material balance. Though each of the formulations avoid the use of a mode index, which reduce the combinatorial nature of the problem, they represent in a different manner the time dimension. The first approach uses a discrete time representation, the second one completely disregards time in favor of sequencing constraints, and the third one uses a continuous time representation. Therefore, the reduction in the complexity of the problem and the limitations of the model are different. For example if 3 resources have to be scheduled to complete 4 projects, which 5 different stages each, the mode based approach (considering only 3 different modes and 40 time periods) would require in the worst possible scenario the solution of 2^7200 LPs. The discrete time approach would require de solution of 2^2401 , while the sequence based approach and the continuous time one would require 2^360 and 2^1201 (using 20 time slots) respectively. In any case the complexity is overwhelming; therefore in this work we highlight the advantages and disadvantages of each formulation, and explore their performances with a problem drawn from the product development pipeline management domain.

Related references:

Maravelias, C.T. and I.E. Grossmann, "New general continuous-time state - Task network formulation for short-term scheduling of multipurpose batch plants". Industrial and Engineering Chemistry Research, 2003. 42(13): p. 3056-3074

Mendez, C.A., G.P. Henning, and J. Cerda, "An MILP continuous-time approach to short-term scheduling of resource-constrained multistage flowshop batch facilities". Computers and Chemical Engineering, 2001. 25(4-6): p. 701-711.

Schmidt, C.W. and I.E. Grossmann, "Optimization models for the scheduling of testing tasks in new product development". Industrial & Engineering Chemistry Research, 1996. 35(10): p. 3498-3510.

Vishal A. Varma, G. E. Blau, J. F. Pekny, and G. V. Reklaitis, "Enterprise-wide Modeling & Optimization ? An overview of emerging research challenges and opportunities". Puigjaner, L. & Espuna, A. (eds). Computer-aided chemical engineering, 20 : European Symposium on Computer-aided process engineering-15. Elsevier, Netherlands.

Weglarz, J., Project scheduling : recent models, algorithms, and applications. International series in operations research & management science. 1999, Boston: Kluwer. x, 535.

Juan C. Zapata, Vishal A. Varma, and G. V. Reklaitis, "A Framework for Capturing the Impact of Resource Allocation Policies in the Selection of a New Product Portfolio". Marquardt, W. & Sass R. (eds). Computer-aided chemical engineering, 21 : 16th European symposium on computer aided process engineering and 9th international symposium on process systems engineering. Elsevier, Netherlands