Naru's Happy Travel
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.
11-4-10_397-405_ Nguyen Thi Ngoc Truc.pdf532.5KB

1. INTRODUCTION

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. 

2. THEORETICAL BACKGROUND

2.1 Max-Plus Algebra

 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 ∈ Dm×n  , [ X ]ij expresses the (i, j)th  element of X, and XT  is the transpose matrix of X. For X, Y ∈ Dm×n ,

 If X ∈ Dm×l ,  Y ∈ Dl 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 Dm×n , and e is a matrix whose diagonal elements are e and off-diagonal elements are ε. For a vector v ∈ Dm, diag(v) ∈ Dm×n represents a matrix whose diagonal elements are [v]i   and offdiagonal elements are ε.

2.2 Max-Plus Linear Representation

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 kth  job in process i (1≤ i ≤ n), let di(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 matricesPk, F0 , B0 and C0 are introduced for representing the structure of the system: 

where F0 , B0 and C0 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 (Pk F0)*en ⊕ Pk F0 ⊕ …⊕(Pk F0)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:

2.3 CCPM-MPL Framework for Determining Time Buffers in Multiple Projects

 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 l1 ,l2, … , ln of m-dimension are introduced with the following properties:

for all i (1≤ i ≤ m) and j (1≤ j ≤ n), and lj  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∈ Dm×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 buffer (PB)

 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 C0  , if [ C0 ]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 buffer (FB)

 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 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 ) ⊗F0 ⊗diag(v ), Fββ represents the transitions from non-critical processes to non-critical ones. 

• Capacity buffer (CB)

 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. FAB = diag( lB ) ⊗F0  diag(lA ),FAB   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 FAA = diag( lA ) ⊗F0  ⊗ diag(lA ). FAA  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.

• Redefined system with the CCPM applied

 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(bf ) :  Fβα  and bf  expresses the position and sizes of the FBs, respectively, and

where n is the number of projects. The subscript ‘c’ expresses the CBs. Fxy  presents the transitions of processes from project x to y, and (bc)xy  expresses the size of the corresponding CBs. Note that  Fc = εmn   if n = 1. Moreover, matrices  Pγ = P ⊗1/ 3   and B0  remain unchanged. 

3. BUFFER MANAGEMENT

3.1 Concept of the CCPM

 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.

3.2 Proposed Method

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 (l1 ,l2, … , ln) which represent the processes belonging to n projects, derived in Eq. (17), we define n vectors l1a ,l2a , … ,lna that satisfy: 

where α is the set of critical processes determined by Eq. (16), and lxα   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  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 z1 ,z2, … , zn, 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:

• Ratio of the PBs’ consumption (buffer used, %):

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

where bp  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 rb  as: 

• Ratio of the progress time over the critical path duration (time elapsed, %)

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

where , u'γL = LTα ⊙ 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 rtx  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. 

4. NUMERICAL EXAMPLE

 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).

4.1 Determination of Time Buffers

 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 yE  = (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  = (e e e ε e ε ε ε)T ,     l  = (ε ε ε e ε e e e)T .
The matrix L given in Eq. (18) is: 

• Project buffer

 Since the critical path is identified as α ={1, 3, 4, 5, 6, 8}, and  [C0 ]15 = e and [C0]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 bp = (7 6)T.

• Feeding buffer

 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 bf = (ε 1 ε ε ε ε 1 ε)T  .

• Capacity buffer

 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 (bc )12 = (ε ε 4 ε ε ε ε ε)T  .

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

• The system with the CCPM applied

 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} . 

4.2 Buffer Management

 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 = [e ε e ε e ε ε ε ]T,
l = [ε ε ε 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:

• Ratio of the PB’s consumption

- Classify the original PB of each project:


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

• Ratio of the corresponding progress time over the expected duration time

 - 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.

5. CONCLUSION

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.

ACKNOWLEDGMENTS

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

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소

SketchBook5,스케치북5

SketchBook5,스케치북5

SketchBook5,스케치북5

SketchBook5,스케치북5