Optimal buffer management in project planning under uncertainty

Every single day millions of small, medium and large projects are being executed. The planning of these projects is not a simple endeavor. One often hears about the failure to complete projects in time, within budget and according to specifications (see Flyvbjerg [2005] for a nice overview). Perfect examples thereof are the building of the international airport in Denver (200% overrun of the costs), the building of the Chunnel (80% overrun of the costs) and the organization of the Olympic Games in Athens (a billion Euro above budget). Closer to home the renovation of the Berlaymont building in Brussels also caught the eye: in 1991 asbestos was discovered in the building and this had to be removed for safety reasons. Although the planning specified that the building would be renovated by 1998, Belgium has paid some monthly penalties of 221.000 Euro in 2004 due to a late handing over of the building to the European Community. Moreover, the costs were rocketing sky-high: the renovation was estimated to cost 108 million Euro, while the final figure turned out to amount to 620 million Euro. It might be obvious that project planning didn't live up to its promise in this case (as in many others). Fundamental research in the field of project planning is therefore of utmost importance.

The vast majority of the project scheduling efforts over the last forty years (see Demeulemeester & Herroelen [2002] for an overview) have concentrated on the development of a workable baseline schedule with the goal of obtaining a project duration that is as short as possible. One traditionally makes the assumption that the durations of the activities are known and deterministic and that the resources are fully available. A realistic project, however, will always be subject to disruptions. Many types of disruptions have been studied in the literature (Yu & Qi [2004], Wang [2005] and Zhu et al. [2005]): activities can take longer than primarily expected, resource requirements or availabilities may vary, due dates may change during the execution of the project, new activities may have to be inserted (Artigues & Roubellat [2000]), etc. Research in project scheduling has focused on proactive and reactive procedures to counteract the effects of these disruptions as much as possible: proactive planning attempts to build a stable project plan that takes the possible disruptions as much as possible into account, while the reactive planning procedures are called every time the disruption changes the baseline schedule such that it cannot be executed anymore as planned.

A typical objective function for the proactive project planning phase is the weighted sum of the deviations between the planned and the realized starting times of the different activities in the project. Quite some research in our research group (Leus [2003], Leus & Herroelen [2004], Van de Vonder [2006], Van de Vonder et al. [2005, 2006, 2007a, 2007b, 2008], Deblaere et al. [2007], Lambrechts [2007], Lambrechts et al. [2008a, 2008b]) focused itself on the construction of stable project plans and this mainly under the assumption of uncertain durations and uncertain resources. Typically, the solution procedure consisted of two phases. In the first phase, a baseline plan is built that is feasible with respect to the precedence relations as well as to the resource constraints and that is based on previously determined durations and resource requirements for every activity. In a second phase, this plan is made more stable through the introduction of time buffers before the activities (even if their predecessors take longer than expected, this doesn't automatically lead to a postponement of the corresponding activity) and through the determination of how the resources are passed along from activity to activity. A disadvantage of such a two-step procedure obviously results from the fact that the ultimate results depend heavily upon the plan that was chosen in the first step (typically an optimal plan for the deterministic version of the corresponding project scheduling problem).

In this research project we want to search first for a monolithic one-step procedure to build a stable baseline schedule. The basic idea is that we start from a reactive project planning procedure that is called every time a disruption during the execution of the project leads to change in the planning of the project. Such a procedure can for instance consist of an activity list (this list specifies the priority for the different activities) combined with a scheduling scheme (this scheme determines when the activities are planned as a function of their priorities). When we simulate the resulting planning a number of times (for instance a thousand times), we obtain a distribution of the starting times for each activity. Based upon this information, the procedure would then choose those starting times for each of the activities such that a feasible (with respect to the precedence relations and the resource availabilities) project schedule is the result and such that the weighted sum of the deviations between the planned and the realized starting times of the different activities in the project is minimized. Procedures that are based on linear programming should be able to solve the resulting problem optimally. The choice of the reactive project planning procedure is of course of utmost importance and should be tested extensively.

In the field of production planning, Goldratt's Theory of Constraints has had a huge impact. In 1997, Goldratt wrote a new book (Goldratt [1997]), in which he applied the Theory of Constraints on the field of project planning. This application is since then known under the name of Critical Chain Scheduling and Buffer Management (CC/BM) and since then quite some books (Newbold [1998], Leach [2000], among others) and articles (Leach [1999], Maylor [2000], Umble and Umble [2000], among others) have been written on this topic. There were some critics to be heard on CC/BM (Wilkens [2000] and Herroelen & Leus [2001]), but many practitioners became very favourable of CC/BM. The basic philosophy of CC/BM consists of the addition of a project buffer (typically half the length of the critical chain) to the end of the project and of feeding buffers every time a non-critical chain joins the critical chain (typically such a buffer also amounts to half the length of the non-critical chain). During the application of CC/BM the implicit assumption is made that one considers only one execution mode (one duration with the corresponding resource requirements) for each activity.

In this research proposal, the second part wants to extend CC/BM to multiple execution modes: indeed, at the start of the project, a project manager has the possibility to make a choice concerning which execution mode has to be chosen for an activity (an activity with a total work content of 24 person days can for instance be executed in either 6 days using 4 persons or 4 days using 6 persons or ...). These choices for every activity of course result in different project networks and thus in different results when CC/BM is applied. In this second part of the research proposal, we want to research which guidelines can be given with respect to the choices of the execution modes that have to be made when planning projects according to CC/BM. In a first step we want to apply CC/BM for all combinations of the execution modes of the activities and to simulate the resulting planning a number of times (for instance a thousand times). For each combination, we want to choose the best assignment of the execution modes based on the resulting average project duration, the variance of the project duration and the signal-to-noise ratio of the project duration (this is a measure that was proposed by Genichi Taguchi in the field of design of experiments and that has as a goal to select that combination that is best when the average and the variance are considered simultaneously (see Demeulemeester [2008], page 177 for a more involved explanation).

A logical third part of the research proposal consists in the application of the methodology of the second part (the selection of the optimal execution modes) to the problem of the first part (the determination in one step of the optimal starting times of the activities (and thus implicitly the buffers between the different activities)).

I am convinced that a good PhD that researches these three research topics will result in at least three publications in international journals with a good impact factor.

References

Artigues, C. & Roubellat, F. (2000). A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes. European journal of operational research, 127(2), 297-316.

Deblaere, F., Demeulemeester, E., Herroelen, W. & Van de Vonder, S. (2007). Robust resource allocation decisions in resource-constrained projects. Decision sciences, 38(1), 5-37.

Demeulemeester, E. (2008). Integrale kwaliteitsbeheersing. Alta Uitgeverij, Leuven.

Demeulemeester, E. & Herroelen, W. (2002). Project scheduling - A research handbook. Kluwer's International Series, Kluwer Academic Publishers.

Flyvbjerg, B. (2005). Design by deception - The politics of megaproject approval. Harvard design magazine, Spring/summer, 50-59.

Goldratt, E.M. (1997). Critical chain. The North River Press, Great Barrington, USA.

Herroelen, W.S. & Leus, R. (2000). On the merits and pitfalls of critical chain scheduling. Journal of operations management, 19(5), 559-577.

Lambrechts, O. (2007]. Robust project scheduling subject to resource breakdowns. PhD thesis, Faculty of Business and Economics, Katholieke Universiteit Leuven, Belgium.

Lambrechts, O., Demeulemeester, E. & Herroelen, W. (2008a). Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. Journal of scheduling, 11(2), 121-136.

Lambrechts, O., Demeulemeester, E. & Herroelen, W. (2008b). A tabu search procedure for developing robust predictive project schedules. International journal of production economics, 111(2), 493-508.

Leach, L.P. (1999). Critical chain project management improves project performance. Project management journal, June, 39-51.

Leach, L.P. (2000). Critical chain project management. Artech House Professional Development Library.

Leus, R. (2003). The generation of stable project plans - Complexity and exact algorithms. PhD thesis, Faculty of Business and Economics, Katholieke Universiteit Leuven, Belgium.

Leus, R. & Herroelen, W. (2004). Stability and resource allocation in project planning. IIE Transaction, 36(7), 1-16.

Maylor, H. (2000). Another silver bullet? A review of the TOC approach to project management. Paper presented at the 7th International EurOMA Conference, Ghent, Belgium.

Newbold, R.C. (1998). Project management in the fast lane - Applying the theory of constraints. The St. Lucie Press, Boca Raton.

Umble, M. & Umble, E. (2000). Manage your projects for success: An application of the theory of constraints. Production and inventory management journal, Second quarter, 27-32.

Van de Vonder, S. (2006). Proactive-reactive procedures for robust project scheduling. PhD thesis, Faculty of Business and Economics, Katholieke Universiteit Leuven, Belgium.

Van de Vonder, S., Demeulemeester, E., Herroelen, W. & Leus, R. (2005). The use of buffers in project management: The trade-off between stability and makespan. International journal of production economics, 97(2), 227-240.

Van de Vonder, S., Demeulemeester, E., Herroelen, W. & Leus, R. (2006). The trade-off between stability and makespan in resource-constrained project scheduling. International journal of production research, 44(2), 215-236.

Van de Vonder, S., Ballestin, F., Demeulemeester, E. & Herroelen, W. (2007a). Heuristic procedures for reactive project scheduling. Computers & industrial engineering, 52(1), 11-28.

Van de Vonder, S., Demeulemeester, E. & Herroelen, W. (2007b). A classification of predictive-reactive project scheduling procedures. Journal of scheduling, 10(3), 195-207.

Van de Vonder, S., Demeulemeester, E. & Herroelen, W. (2008). Proactive heuristic procedures for robust project scheduling: An experimental analysis. European journal of operational research, 189(3), 723-733.

Wang, J. (2005). Constraint-based schedule repair for product development projects with time-limited constraints. International journal of production economics, 95, 399-414.

Wilkens, T.T. (2000). Critical path, or chain or both? PM Network, 14(7), 68-74.

Yu, G. & Qi, X. (2004). Disruption management - Framework, models and applications. World Scientific, New Jersey.

Zhu, G., Bard, J. & Yu, G. (2005). Disruption management for resource-constrained project scheduling. Journal of the operational research society, 56, 365-381.