DOI : http://dx.doi.org/10.7232/iems.2012.11.4.397 |

Buffer Management Method for Multiple Projects in the CCPM-MPL Representation

Thi Ngoc Truc*, |

Department of Information Science and Control Engineering, Nagaoka University of Technology, Nagaoka, Japan Department of Electrical Engineering, Nagaoka University of Technology, Nagaoka, Japan Department of Industrial and Systems Engineering, Hosei University, Koganei, Japan Department of Humanities, Yamanashi Eiwa College, Kofu, Japan |

(Received: August 19, 2012 / Revised: November 23, 2012 / Accepted: November 26, 2012) |

Abstract |

This research proposes a framework of buffer management for multi-project systems in the critical chain project management (CCPM) method, expressed in the form of max-plus linear (MPL) representation. Since time buffers are inserted in the projects for absorbing uncertainties in task durations and protecting the completion times, the proposed method provides a procedure for frequently surveying the rates of consumed buffers and the rate of elapsed times. Their relation expresses the performance of the projects which is plotted on a chart through the completed processes. The chart presents the current performance of the projects and their interaction, which alerts managers to make necessary decisions at the right time for managing each project and the entire multi-project system. The proposed framework can analyze the complex system readily, and it enables managers to make an effective decision on scheduling. The effectiveness of the framework is demonstrated through a numerical example. |

- 1. INTRODUCTION
- 2. THEORETICAL BACKGROUND
- 2.1 Max-Plus Algebra
- 2.2 Max-Plus Linear Representation
- 2.3 CCPM-MPL Framework for Determining Time Buffers in Multiple Projects
- • Project buffer (PB)
- • Feeding buffer (FB)
- • Capacity buffer (CB)
- • Redefined system with the CCPM applied
- 3. BUFFER MANAGEMENT
- 3.1 Concept of the CCPM
- 3.2 Proposed Method
- • Ratio of the PBs’ consumption (buffer used, %):
- • Ratio of the progress time over the critical path duration (time elapsed, %)
- 4. NUMERICAL EXAMPLE
- 4.1 Determination of Time Buffers
- • Project buffer
- • Feeding buffer
- • Capacity buffer
- • The system with the CCPM applied
- 4.2 Buffer Management
- • Ratio of the PB’s consumption
- • Ratio of the corresponding progress time over the expected duration time
- 5. CONCLUSION
- ACKNOWLEDGMENTS

The critical chain project management (CCPM) is a well-known method for planning and managing projects. The concept of the CCPM is an outgrowth of the theory of constrains (TOC), first developed by Goldratt (1990), which has drawn much attention for many researchers (Herroelen et al., 2002; Cohen et al., 2004; Leach, 2005; Tukel et al., 2006). These researches have mainly focused on clarifying the concepts of the CCPM method, discussing several related issues such as resource conflict, buffer’s size, and buffer management. In project management, initial schedule is frequently changed due to unpredictable reasons such as external uncertainties, processing changes, and resource conflicts. Thus, the CCPM provides a method for inserting time buffers which play a role for absorbing uncertainties in the task durations to protect the completion time. Moreover, the CCPM method has achieved successes not only for a single project but for large-scale multi-projects (Cohen et al., 2004; Leach, 2005).

On the other hand, the max-plus linear (MPL) representation is known as an efficient tool for describing a class of discrete event systems (DESs) (Heidergott et al., 2006; Goto, 2010). The typical and significant feature of DESs is that events occur at discrete time instants and the values of the internal states change non-continuously. This kind of systems typically appears in manufacturing systems, transportation systems, project management, and so on. Since unpredictable changes in the execution times may influence the completion time, several researches that consider uncertainties have been carried out (Heidergott, 2006). However, due to the nonlinearity in the states of the system, it is difficult to handle largescale systems.

Furthermore, an application of the CCPM framework to an MPL representation was studied in our previous paper (Takahashi et al., 2009; Truc et al., 2011). Therein, a method for determining and inserting time buffers to absorb uncertainties is considered using an MPL representation. We first identified a critical path, which is the longest path of successive tasks with zero float time. Then, we reduced the processing time and installed project and feeding buffers. A project buffer is inserted between the end of the critical path and its succeeding output. Feeding buffers are inserted wherever a non-critical path joins into a critical path. These buffers were frequently monitored and controlled with a buffer management policy (Kasahara et al., 2009), in which the behavior of a project is featured by the rates of buffer consumption and processing time. However, these works were designed only for a single-project system.

Recently, a CCPM-MPL framework for determining time buffers has been proposed for multi-project systems (Truc et al., 2012), an extended and improved version of a single-project case. The project and feeding buffers are determined for each project in large-scale systems; the buffers are used to absorb uncertainties in the internal task durations of each project. Moreover, the constraints between the projects are determined to insert capacity buffers; they play a role for absorbing uncertainties in the preceding project and protect the subsequent projects.

This research considers a framework for managing these buffers in a multi-project system. Particularly, instead of minimizing the duration of each project as the case of a single project, the multi-project scheduling aims to maximize the throughput of the entire system by sharing the same resources. Thus, it is difficult for managers to comprehend the relationship between these projects with mutual dependence by applying the singleproject framework (Kasahara et al., 2009) one by one, making the control of the whole system tough. The proposed framework herein expresses the performance for all projects and their relationship in the complex system with multiple input times, which can alert managers to make extra actions at the proper time to avoid tardiness both for individual project and for the entire system. In this paper, the effect of cost and resource conflicts is not considered for the sake of simplicity. For further discussion of resource conflicts, refer to Yoshida et al. (2011).

The remaining contents are presented in the following four sections. Section 2 provides a brief review of the theoretical background for this paper: max-plus algebra, MPL representation, and CCPM-MPL framework. Section 3 derives a concept of buffer management in the CCPM method, and proposes a framework of buffer management in the form of the MPL representation. The proposed framework is confirmed through a numerical example in Section 4. Finally, conclusions and recommendations are given in Section 5.

Max-plus algebra is known as the schedule algebra for describing a certain class of DESs. For a set D = R {−∞}, where R is the entire real set, operators for addition and multiplication are defined as:

The symbol ⊗ corresponds to multiplication in conventional algebra, and is often omitted when no confusion is likely to arise. For example, we simply write xy for expressing x⊗ y. These operators hold the commutative, associative and distributive laws. The zero and unit elements for these are given by ε(=−∞) and e (= 0), respectively. These hold x⊕ε = ε⊕ x = ε and x ⊗ε = ε⊗ x = ε for an arbitrary ε (=+∞). Moreover, we define ε (=+∞) and assume a property ε⊗ε = ε⊗ε = ε.

Furthermore, the following two operators are defined for subsequent discussions:

An operator for the power of a ∈ R is defined as:

Operators for multiple numbers are as follows. If m≤n,

For a matrix X ∈ D^{m×n} , [ X ]i_{j} expresses the (i, j)^{th} element of X, and X^{T} is the transpose matrix of X. For X, Y ∈ D^{m×n} ,

If X ∈ D^{m×l} , Y ∈ D^{l x p}

The priority of operators ⊗ and ⊙ are higher than that of operators ⊕ and ∧ where ⊙ is well-defined if X has at least one non- ε entry in every row. The zero and unit elements for matrices are; ε_{mn} is a matrix whose all elements are ε in D^{m×n} , and e is a matrix whose diagonal elements are e and off-diagonal elements are ε. For a vector v ∈ D^{m}, diag(v) ∈ D^{m×n} represents a matrix whose diagonal elements are [v]_{i} and offdiagonal elements are ε.

We briefly review the MPL representation for a certain class of discrete event systems developed by Yoshida et al. (2010). We assume the following constraints imposed on the focused system:

• The number of processes, external inputs and external outputs are n, p, and q, respectively.

• All processes are used only once for a single job.

• The subsequent job cannot start processing while the current job is at work.

• Processes that have precedence constraints cannot start processing until they have received all the required parts from the preceding processes.

• Processes with external inputs cannot start until all the required materials have arrived.

• The processing starts as soon as all the conditions above are satisfied.

For the k^{th} job in process i (1≤ i ≤ n), let d_{i}(k) (≥0), [x^{-}(k)]_{i} and [x^{+}(k)]_{i}, x k be the processing time, processing start time, and processing completion time, respectively. We give the initial condition by x(0)= ε_{n1} .Moreover, [ u(k)]_{i} represents the material arrival time from external input i (1≤ i ≤ p), and [y(k)]_{i} represents the output time of the finished product to external output i (1≤ i ≤ q). The following matricesP_{k}, F_{0} , B_{0} and C_{0} are introduced for representing the structure of the system:

where F_{0} , B_{0} and C_{0} are referred to as the adjacency, input and output matrices, respectively.

The earliest completion time is defined as the minimum value with which the corresponding process can complete processing. Specifically, the earliest completion times of all processes are calculated by:

where (P_{k} F_{0})^{*}e_{n} ⊕ P_{k} F_{0 }⊕ …⊕(P_{k} F_{0})^{l-1} , and an instance l (1≤ l ≤ n) depends on the precedence-relationships of the system. The corresponding output times are given by:

The earliest starting times of all processes are given by:

Furthermore, the latest starting times are defined as the maximum value by which the same output time based on the earliest time can be accomplished. Thus, the latest starting times of all processes and the latest feeding times are given by:

A critical path is understood as a series of processes with zero total float. Total float is the maximum time which can be moved backward without changing the completion time. This is defined as the difference between the latest and earliest starting times. Specifically, the total floats ω(k) of all processes are obtained as:

Moreover, the critical path is identified by the set of process numbers α that satisfy:

We briefly review the framework for determining time buffers in a multi-project system (Truc et al., 2012). Considering a general system with m processes (tasks) and n projects, n vectors l_{1} ,l_{2}, … , l_{n }of m-dimension are introduced with the following properties:

for all i (1≤ i ≤ m) and j (1≤ j ≤ n), and l_{j} expresses which processes belong to project j. Note that process i is implicitly designed to belong a certain project based on the priority of the projects and the processes. Then, we define a matrix L∈ D^{m×n} hat represents the layer of projects as follows:

Moreover, we reduce the processing time of tasks to 1/3 of the original time and define the size of time buffers as 1/3 of the corresponding path duration (Takahashi et al., 2009). The position and size of the buffers are determined as below:

Project buffers are inserted between the end of critical paths and their succeeding external outputs, to protect the critical paths. The positions are determined by inspecting the elements of the output matrix C_{0} , if [ C_{0 }]_{ij} _{ }≠ ε and j ∈α, a PB is inserted behind process. The sizes of the PBs are obtained by:

where matrix L_{α} is defined from the set of critical processes ( α ) determined in Eq. (16) as:

Feeding buffers are inserted where a non-critical path joins into a critical path, to protect the critical paths from delay which may occur in the non-critical paths. To define the positions of FBs, we first introduce two vectors v and w with the properties as [v ]_{i} ={e :i ∈ β, ε : i ∉ β}, and [w ]_{i} ={e : i∈α, ε : i∉ α}, where β is the set of non-critical processes, the positions are identified using two vectors v′ and w′ with the following properties:

where γ is the subset of β having a successor classified as α. F_{βα} = _{ }diag(w) _{ }⊗ F_{0 }⊗ diag(v), F_{βα} represents the transitions from non-critical processes to critical ones.

where τ is the subset of α having a predecessor classified as β. Then, FBs are installed at transitions between processes γ and τ. The sizes of the FBs are estimated as:

where F_{ββ} = diag( v ) ⊗F_{0} ⊗diag(v ), F_{ββ} represents the transitions from non-critical processes to non-critical ones.

Capacity buffers are inserted at the transitions between projects, to absorb uncertainties in the preceding project and protect the subsequent projects. We first determine transitions for each pair of the projects. Generally, transitions from project A to project B(A≠ B) are defined through two vectors h and h′ with the following properties as:

where ϑ is the set of processes in project A with a successor belonging to project B. F_{AB} = diag( l_{B} ) ⊗F_{0} diag(l_{A} ),F_{AB} represents the transitions from processes in project A to processes in project B.

where ϕ is the set of processes in project B with a predecessor belonging to project A. Taking these together, CBs are inserted at transitions between processes ϑ and ϕ. The sizes of the CBs from project A to B are calculated by:

where F_{AA} = diag( l_{A} ) ⊗F_{0} ⊗ diag(l_{A} ). F_{AA} represents the transitions between processes in project A.

Similarly, we can find the positions and sizes of CBs from project B to A, or between any pair of the projects.

The representing matrices introduced in Section 2.2 are redefined for easily comprehending the structure of the system after the CCPM applied. After the insertion of the PB, the output matrix C_{γ} is reformulated in the following manner:

where the subscript ‘ γ ’ expresses that the matrix was redefined. After the insertion of the FBs and CBs, the adjacency matrix F_{γ } is reformulated as:

where F_{βα} = F_{βα }⊗_{ }diag(b_{f} ) : F_{βα} and b_{f} expresses the position and sizes of the FBs, respectively, and

where n is the number of projects. The subscript ‘c’ expresses the CBs. F_{xy} presents the transitions of processes from project x to y, and (b_{c})_{xy} expresses the size of the corresponding CBs. Note that F_{c} = ε_{mn } if n = 1. Moreover, matrices P_{γ }= P_{k } ^{⊗1/ 3} and B_{0} remain unchanged.

In the CCPM, for managing and observing the projects’ performance, the buffers are frequently monitored to protect the critical path as well as the project’s completion time. This mechanism is called “Buffer Management”, which can detect a potential problem and raise a warning signal to managers. As the projects proceed, if a task elapses a longer time than expected, the task consumes the buffer on the corresponding path. Thus, the buffer management frequently compares two parameters: the consumption rate of the PB and the progress rate of the corresponding critical path, for expressing the current performance of the project. In the multi-project system, these parameters are frequently checked for all projects and plotted on a fever chart, as shown in Figure 1. This chart shows the relationship between buffer used (%) versus time used (%) through the completed processes. The chart is divided into three zones: green, yellow, and red, which are determined empirically by thresholds settings. Typically, we base on the thresholds settings proposed by Leach (2005) as listed in Table 1. Figure 1. An example of a fever chart. Table 1.

**Figure. 1.** An example of a fever chart.

**Table 1.** Buffer thresholds

Using the fever chart, the projects’ status is alerted to project managers and the decision level for an extra action is suggested. Specifically, if the current status is in the green zone, the project is going well and the managers need not take an action. If the status is in the yellow zone, the project assesses a problem and needs a recovery plan to avoid further buffer erosion. If the status is in the red zone, the project will possibly be late and the managers should initiate the action.

We develop a framework of buffer management for a multi-project system, which focuses on the system after the insertion of the time buffers. The overall procedure for buffer management is summarized as the flowchart in Figure 2. A sequencing description for the procedure is expressed by using the MPL representation as follows:

**Figure. 2.** Flowchart of buffer management.

We again consider the multi-project system with n projects and m processes mentioned in Section 2.3. Using n vectors (l_{1} ,l_{2}, … , l_{n}) which represent the processes belonging to n projects, derived in Eq. (17), we define n vectors l_{1a} ,l_{2a} , … ,l_{na} that satisfy:

where α is the set of critical processes determined by Eq. (16), and l_{xα } expresses which critical processes belong to project x(1≤ x ≤n). Thus, the managers can monitor each project in only one procedure for the entire system instead of considering them independently. Next, we introduce a vector z which represents the actual completion times of the completed processes at the monitoring stage. Thus, the managers can survey the value of this vector frequently whenever monitoring the project’s execution. Vector z has the following property:

where t_{i } is defined as actual completion time of process i and η represents the set of completed process numbers at the monitoring stage, and (=+∞) is mentioned in Section 2.1. In order to manage the buffers for each project, we decompose vector z to n vectors z_{1} ,z_{2}, … , z_{n}, which represent n projects by:

where x ∈{1,…, n} , and z has the following properties:

In order to know the projects’ performance at the monitoring stage, we calculate the rates of the PBs’ consumption and the elapsed times. These values are determined for each project as the following procedure:

First, we classify the original PB for each project (x):

where b_{p} is the size of the PBs obtained from Eq. (19). Then, we define the PB consumed by the completed processes for project (x) using the following vector:

where presents the earliest completion times of the system after the CCPM application, derived in Section 2.3. Finally, the consumption rate of the PB at the monitoring stage is calculated through vector r_{b} as:

First, we calculate the duration time of the critical path for each project (x):

where , u'_{γL} = L^{T}_{α} ⊙ x^{-}_{γL},^{ }u'_{γL} expresses the latest feeding times on the critical paths, and x^{-}_{γL} ^{ }and y_{γE} are the latest starting times and the output times of the system after the CCPM application, derived in Section 2.3. Then, we define the completion time of processes at the monitoring stage without considering the effect of input times as:

where u_{γL} ^{ } expresses the latest feeding times which is derived in Section 2.3. Finally, the ratio of the progress time over the estimated completion time is obtained through vector r_{tx} as:

The ratio of buffer consumption (%) versus the corresponding progress time (%) is plotted, respectively for all projects through the completed processes on the same fever chart (Figure 1). The chart expresses the current status of all projects and their interaction. Thus, managers can make a proper decision for protecting each project and the entire system.

A numerical example for a simple system is presented to facilitate better understanding of the proposed framework.

Figure 3 shows a simple system with two projects consisting of three inputs, two outputs and eight processes. Note that the dashed arrow from process (3) to (6) is considered as the precedence constraint between the two projects.

· Project 1 consists of processes (1), (2), (3), and (5).

· Project 2 consists of processes (4), (6), (7), and (8).

**Figure. 3.** A simple system with two projects (1 and 2).

Using the MPL representation introduced in Section 2.2, the representation matrices for the entire system are given as follows:

Assuming that the initial condition is x(0)=ε_{81} and the input times u=[−3 4 5]^{T} , the output times and the critical path are identified as y_{E} = (18 22)^{T} and α ={1, 3, 4, 5, 6, 8}. respectively.

Moreover, we apply the MPL representation presented in Section 2.3 to the system. First, the processing times are given by (3, 3, 9, 6, 9, 9, 3, 3)^{⊗1/ 3} .

From Eq. (17), we define two vectors as:

l_{1 } = (e e e ε e ε ε ε)^{T} , l_{2 } = (ε ε ε e ε e e e)^{T} .

The matrix L given in Eq. (18) is:

Since the critical path is identified as α ={1, 3, 4, 5, 6, 8}, and [C_{0} ]_{15} = e and [C_{0}]_{28} = e the positions of the PBs are behind processes (5) and (8). From Eqs. (19) and (20), we obtain the sizes of the PBs as b_{p} = (7 6)^{T}.

From Eqs. (21)–(23), we obtain the positions of the FBs inserted at the transitions of process (2) → (5) and process (7) → (8). The sizes of the FBs are determined as b_{f} = (ε 1 ε ε ε ε 1 ε)^{T} .

From Eqs. (24)–(26), a CB is inserted at the transition of process (3) → (6). Moreover, the size of the CB at the transition from project 1 to 2 is (b_{c} )_{12} = (ε ε 4 ε ε ε ε ε)^{T} .

Figure 4 shows the system with the time buffers inserted for the multi-project system in Figure 3.

The matrices for representing the structure of the latter system are redefined as follows. Using Eqs. (27)– (29), we obtain the adjacency and output matrices as:

Using Eqs. (10)-(16), the earliest completion times and the corresponding output times are calculated as = ( −2 −11 6 4 9 7 10)^{T} and y_{γE}= (11 16) respectively. The latest feeding times are obtained as u_{γL }= (−3 4 7)^{T} . Moreover, the critical path is identified as α ={1, 3, 4, 5, 6, 8} .

After the insertion of the time buffers, the multiproject system is monitored and controlled through the buffer management proposed in Section 3.2. From Eq. (30), we obtain two vectors as:

l_{1α} = [e ε e ε e ε ε ε ]^{T},

l_{2α} = [ε ε ε e ε e ε e]^{T}.

**Figure. 4.** The multi-project system after the application of critical chain project management method.

We assume here that the set of the completed processes η and the vector of the actual completion times z have been collected at the motoring stage as:

- Classify the original PB of each project:

- Define the PBs consumed by the completed processes on each project (buffer used):

- Calculate the duration time of the critical path for each project:

- Define the progress time at the monitoring stage without considering the effect of the input time(time used):

- Obtain the ratio of the progress time over the duration time of the critical path (time used, %):

The ratio of buffer consumption versus the corresponding progress time is plotted on a fever chart as shown in Figure 5. The plotted points express the statuses of the completed processes along the critical paths. The chart implies the following:

• The performance of project 1 is expressed by processes (1) and (3). In particular, process (3) shows the latest status which belongs to the red zone. It means that project 1 will possibly be late and managers should initiate the extra action to avoid further buffer consumption.

• The performance of project 2 is expressed by processes (4) and (6). Process (6) shows the latest status which belongs to the green zone. It means that project 2 is going well and need not take an action.

• Since a capacity buffer was inserted between projects 1 and 2 at the transition of process (3) → (6), though process (3) takes a longer time to complete which leads project 1 to be at risk, project 2 is still all right. Thus, it signifies that managers need to take the actions which should focus on project 1 only.

**Figure. 5.** Fever chart for the multi-project system in Figure 4.

We have proposed an MPL representation for describing a buffer management in the CCPM method focusing on multi-project systems. By introducing an inspected vector which represents the actual completion time of the completed processes at the monitoring stage, the managers can survey the performance of all projects frequently. Moreover, the proposed method can analyze the complex system to estimate the rates of the consumed project buffers and the elapsed progress times readily for expressing the current status of all projects and their interaction, which support managers to easily monitor each project, effectively managing the entire system.

Since we have developed a deterministic model for inserting and controlling the time buffers, for practical cases, a stochastic model, which takes into account the analysis of the external uncertainties, will be an important future work.

Yoshinori Takei has been supported in part by a research grant from JSPS Grants-in-Aid for Scientific Research No. 23650005. Hiroyuki Goto has been supported in part by a research grant from JSPS Grants-in-Aid for Scientific Research No. 23510163. Hirotaka Takahashi has used the facilities of Earthquake Research Institute (ERI), The University of Tokyo. He has also been supported in part by the JSPS Grant-in-Aid for Scientific Research No. 23740207.

Reference |

1.Cohen, I., Mandelbaum, A., and Shtub, A. (2004), Multiproject Scheduling and Control: A process-based comparative study of the Critical Chain Methodology and Some Alternatives, Project Management Journal, 35(2), 39-50.
2.Goldratt, E. M. (1990), Theory of Constraints, North River Corp., Great Barington, MA. 3.Goto, H. (2010), Modelling methods based on discrete algebraic systems. In: Goti, A. (ed.), Discrete Event Simulations, Sciyo, Rijeka, Croatia, 35-62. 4.Heidergott, B. (2006), Max-Plus Linear Stochastic Systems and Perturbation Analysis, Springer, New York, NY. 5.Heidergott, B., Jan Olsder, G., and van der Woude, J. W. (2006), Max Plus at Work: Modeling and Analysis of Synchronized Systems, Princeton University Press, Princeton, NJ. 6.Herroelen, W., Leus, R., and Demeulemeester, E. (2002), Critical chain project scheduling: do not oversimplify, Project Management Journal, 33, 46-60. 7.Kasahara, M., Takahashi, H., and Goto, H. (2009), On a buffer management policy for CCPM-MPL representation, International Journal of Computational Science, 3(6), 593-606. 8.Leach, L. P. (2005), Critical Chain Project Management, Artech House, Boston, MA. 9.Takahashi, H., Goto, H., and Kasahara, M. (2009), Toward the application of a critical-chain-projectmanagement- based framework on max-plus linear systems, Industrial Engineering and Management Systems, 8(3), 155-161. 10.Truc, N. T. N., Goto, H., Takahashi, H., and Yoshida, S. (2011), Enhanced framework for determining time buffers in the MPL-CCPM representation, International Journal of Information Science and Computer Mathematics, 4(1), 1-18. 11.Truc, N. T. N., Goto, H., Takahashi, H., Yoshida, S., and Takei, Y. (2012), Critical chain project management based on a max-plus linear representation for determining time buffers in multiple projects, Journal of Advanced Mechanical Design, Systems, and Manufacturing, 6(5), 715-727. 12.Tukel, O. I., Rom, W. O., and Eksioglu, S. D. (2006), An investigation of buffer sizing techniques in critical chain scheduling, European Journal of Operational Research, 172(2), 401-416. 13.Yoshida, S., Takahashi, H., and Goto, H. (2010), Modified max-plus linear representation for inserting time buffers, Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management, Macau, China, 1631-1635. 14.Yoshida, S., Takahashi, H., and Goto, H. (2011), Resolution of time and worker conflicts for a single project in a max-plus linear representation, Industrial Engineering and Management Systems, 10(4), 279- 287. |

Designed by hikaru100