GPM First
Chapter 2 of Management Science, Operations Research and Project Management (978-1-4724-2643-7) by José Ramón San Cristóbal Mateo

Multi-Objective Decision-Making Models

Chapter 2

Traditional research on project schedule and management focuses on one objective: either the shortest possible project duration or the minimum possible cost. However, in most situations, the optimization problems are multi-objective where two or more independent objectives must be optimized simultaneously, such as the utilization of resources available and balance of workload. In this chapter, different types of multi-objective decision-making methods are presented, namely, the traditional time-cost trade-off problem, fuzzy linear programming, goal programming and an integer programming problem.

Linear Programming Formulation of the Time-Cost Trade-off Problem

Linear programming is a powerful tool used by managers to obtain optimal solutions to problems that involve restrictions or limitations, such as available resources, budgets, and time. There are a number of different linear programming techniques, some of these techniques are used to fine solutions for specific types of problems, and other are mode general.

The literature contains linear, non-linear, and discrete formulations of the time-cost trade-off problem (Liberatore and Pollack-Johnson, 2006). The linear formulation assumes that each activity’s time can range over a closed interval, and that the cost of completing the activity is linear and decreasing over the interval. This problem can be formulated as a linear programming problem and there are exact solution algorithms that take advantage of the project network’s structure (Fulkerson, 1961; Kelley, 1961). Moore et al., (1978) reported a multi-criteria project crashing problem with linear time-cost trade-off, and proposed a goal programming formulation. The non-linear problem in its simplest form has been modeled using a piecewise linear representation of the common situation in which it becomes proportionately more expensive to reduce duration by each successive time unit. For concave-type relationships, a mixed integer programming problem has to be attempted, but a convex-type relationship appears to be a more practicable assumption in the context of project crashing. If the convex-type relationship is approximated by piecewise linear segments, then the project crashing problem can be converted into equivalent linear programming formulations. Vrat and Kriengkrairut (1986) presented a goal programming model for the project crashing problem with a non-linear convex-type relationship. The discrete version of the time-cost problem required specifying a set of discrete processing times and associated costs for each activity which is a different way to model non-linearity. The budget version of the discrete problem has been shown to be strongly NP-hard (De et al., 1997).

The linear programming formulation for the traditional deadline makespan problem can be expressed by (Liberatore and Pollack-Johnson, 2006):

Min C=i=1ncixi(2.1)

subject totjti+dixi(i,j)iP(j)(2.2)

t1=0(2.3)

tnT(2.4)

0xiui(2.5)

ti0i(2.6)

 

where

C: total incremental cost for reducing project makespan;

xi: number of time units to crash (reduce duration of) task i;

ti: time task i is scheduled to start (in time units from the beginning of the project);

T: the desired makspan (deadline for total project completion time);

di: duration in time units of task i;

ci: cost per time unit to crash task i;

ui: maximum number of time units that task i can be reduced (crashed);

n: number of tasks (1 if is the start task, and n if is the finish task);

P(j): The set of tasks that are immediate predecessors of task j;

The objective is to minimize the total crashing costs such that the earliest start times of each activity must be greater than or equal to the earliest finish times of that activity’s immediate predecessors. We assume that the start task (task 1) is the only task with no predecessors, that the finish task (task n) is the only task that is not a predecessor of any other task, and that there are no cycles in the network.

Next, the above linear programming problem is applied to the project shown in Figure 2.1. Table 2.1 shows the tasks to undertake, their normal cost, crashing cost, normal duration and crashing time.

 
Figure 2.1 Network associated to the time-cost trade-off problem

graphics/fig2_1.jpg

 
Table 2.1 Data of the project

Task

Arc (i,j)

Normal cost (€*103)

Crashing cost (€*103)

Normal time (days)

Crashing time (days)

Xi

Slope

A

(1,2)

8

14

10

7

3

2

B

(1,3)

7

16

9

6

3

3

C

(2,5)

8

9

6

5

1

1

D

(2,4)

10

18

8

6

2

4

E

(3,4)

6

14

8

4

4

2

F

(5,6)

4

4

5

5

0

0

G

(4,6)

9

24

6

3

3

5

The formulation for this linear programming problem can be expressed as:

MinC:2xA+3xB+1xC+4xD+2xE+5xG

subject tot1=0t2t1+10xAt3t1+9xBt4t2+8xDt4t3+8xEt5t2+6xCt6t5+5xFt6t4+6xGt624,,17xA3;xB3;xC1;xD2;xE4;xF=0;xG3xi0i;ti0;i

 

The problem can be solved using Lingo (Lindo systems, 2002) and different solutions to this problem are given in Table 2.2. As can be appreciated, the reduction in time implies an increase in the crashing cost.

 
Table 2.2 Different solutions to the linear programming problem

Time (days)

Crashing cost (€*103)

Task reduced

24

0

22

6

xA = 2; xE = 1

21

10

xA = 3; xE = 1

20

15

xA = 3; xE = 2; xG = 1

19

20

xA = 3; xE = 2; xG = 2

18

25

xA = 3; xE = 2; xG = 3

17

32

xA = 3; xC = 1; xD = 1 xE = 3; xG = 3

Liberatore and Pollack-Johnson (2006) extend the linear formulation of the deadline time-cost problem and propose a quadratic mixed integer programming approach for reducing project completion time that considers crashing as well as the removal and modification of precedence relationships. Deckro et al. (1995) develop the following quadrating programming model for the traditional time-cost trade-off scenario:

Minz(i,j)A[bij+aij(nijyij)2](2.7)

subject toxi+xjyij0forall(i,j)A(2.8)

τijyijμijforall(i,j)A(2.9)

XTD(2.10)

xi0foralli(2.11)

 

where

bij: normal cost of activity (i, j);

aij: marginal cost increase for varying the normal time;

nij: normal time to complete activity (i, j);

yij: actual duration of activity (i, j);

xi: realization time of event i;

A: set of all activities in the project;

T: index of the terminal node of the project;

D: target completion date for the project;

The actual duration of activity (i, j), yij, would be limited to be within a range from τij to μij, where τij and μij represent the lower and upper bounds on yij respectively. Constraint (2.8) ensures that node j cannot be realized until after node i has been realized, and at least the duration of activity (i, j) has elapsed. Constraint (2.9) creates the upper and lower bounds on the duration of each activity. Constraint (2.10) required that the terminal node, T, be realized on or before the project due date, D. Constraint (2.11) requires that each node be realized at some non-negative time.

A Linear Time-Cost Trade-off Model to Find the Critical Path

An alternative way to find the critical path is by using linear programming (Hillier and Lieberman, 2001; Taha, 2003). The idea is based on the concept that a critical path method problem can be thought of as the opposite of the shortest path problem. In order to determine the critical path in the project network it is sufficient to find the longest path start to finish. Then, the length of this path is the total duration time of the project network. The linear programming formulation assumed that a unit flow enters the project network at the start node and leaves at the finish node.

Let xij be the decision variable denoting the amount of flow in activity (i, j) ∈ A. Since only one unit of flow could be in any arc at any time, the variable xij must assume binary variables only. The critical path method problem with n nodes is formulated as:

MaxDi=1nj=1ntijxij(2.12)

subject toj=1nxij=1(2.13)

j=1nxij=k=1nxki,i=2,,n1(2.14)

k=1nxkn=1(2.15)

xij=0or1i,j(2.16)

 

The objective is to maximize the total duration time of the project network form node 1 to node n. The critical path of this project network consists of a set of activities (i, j) ∈ A from the start to the finish in which each activity in the path corresponds to the optimal decision variable xij = 1 in the optimal solution to the linear programming model.

The following example is used to illustrate the proposed model. The problem is to find the critical path between node 1 and node 6 in Figure 2.1. The formulation for this particular linear programming problem can be expressed as:

MaxD10x1,2+9x1,3+6x2,5+8x2,4+8x3,4+6x4,6+5x5,6

subjecttox1,2+x1,3=1x1,2x2,4x2,5=0x1,3+x3,4=0x2,4+x3,4x4,6=0x2,5x5,6=0x4,6+x5,6=1xij=0or1i,j

 

and the solution is D = 24(days), with x1,2 = 1; x2,4 = 1; and x4,6 = 1.

Fuzzy Linear Programming

When the activity times in the project are deterministic and known, the critical path method has been demonstrated to be a useful tool in managing projects in an efficient manner and a useful tool in the planning and control of complicated projects in a wide range of engineering and management applications (Chen and Hsueh, 2008). However, there are many cases where the activity times may not be presented in a precise manner and have to be estimated subjectively. To deal quantitatively with imprecise data, the Program Evaluation and Review Technique (PERT) was employed. However, in PERT, durations are considered independent and identically distributed. The use of the beta distribution or its variants may not be able to provide an appropriate distribution when the activity time is highly skewed. To construct the probability distribution of activity times requires a prior predictable regularity or a posterior frequency distribution. Variability is neglected in the definition of the critical path, which is determined considering only the average duration of the tasks, etc. (Chen, 2007; Zammori et al., 2007).

An alternative way to deal with imprecise data in determining activity times is to employ the concept of fuzziness (Zadeh, 1978). In recent years many researchers have combined fuzzy set theory with PERT to handle time estimates in project planning and control problems. The result is an approach called Fuzzy PERT, whereby the vague activity times can be represented by fuzzy sets. The main advantages of methodologies based on fuzzy theory are that they do not require prior predictable regularities or posterior frequency distributions, and they can deal with imprecise input information containing feelings and emotions quantified based on decision-maker’s subjective judgment (Chen, 2007).

Several studies have investigated the case where activity durations times in a project are approximately known and are more suitable represented by fuzzy sets rather than crisp numbers (Rommelfanger, 1994; Mons et al., 1995; Kutcha, 2001; Chanas and Zielinski, 2003; Chanas et al., 2002; Dubois et al., 2003; Slyeptsov and Tsyhchuk, 2003; Zielinski, 2005). They employed the concept of fuzziness (Kaufmann, 1975; Zimmermann, 2001) to these cases, and developed analysis approaches. Most of them are straightforward extensions of deterministic CPM mainly based on the formulas for the forward and the backward recursions, in which the deterministic activity times are replaced with the fuzzy activity times (Chen and Hsueh, 2008). These studies focus on the identification of the critical path and on the relatively degrees of criticality of activities and paths in project networks. In this section the traditional deadline makespan problem is formulated as a fuzzy decision model.

A fuzzy objective function is characterized by its membership functions and so are the constraints. A decision in a fuzzy environment is defined in analogy to non-fuzzy environments as the selection of activities which simultaneously satisfy (optimize) objective function(s) and constraints. In fuzzy set theory the intersection of sets normally corresponds to the logical ‘and’. The decision in a fuzzy environment can therefore be viewed as the intersection of fuzzy constraints and fuzzy objective function(s). The relationship between constraints and objective functions in a fuzzy environment is therefore fully symmetric, i.e., there is no longer a difference between the former and the latter. Applied to linear programming the fuzzy decision can therefore be defined as the intersection of the fuzzy sets describing the constraints and the objective functions. If one defines the solution with the highest degree of membership to the fuzzy ‘decision set’ as the maximizing decision, then the following approach can be used (Zimmermann, 1984). Starting from the problem:

Minz=cx

SubjecttoAxb(2.17)x0

 

the adopted fuzzy version is

cxz0Axb(2.18)x0

 

where z0 means an aspiration level of the decision-maker. We now define membership functioni such that

{i((Ax),cx)=1if(Bx)ibi'0<i((Ax),cx)<1ifbi'<(Bx)ibi'+dii((Ax),cx)=0if(Bx)i>bi'+di(2.19)

 

where i indicates de ith row of B or b′, B is the matrix A augmented by the rows of the objective function, b′ the right-hand side augmented by the upper bounds for the values of the objective functions and d, the subjectively chosen constant of admissible violations. The membership function of the solution is then

(Bx)=minii(Bx)0(2.20)

 

and the maximizing decision

maxx0mini(Bx)(2.21)

 

Using the simplest kind of membership function, i.e., linear function of the type

i(Bx)={1if(Bx)ibi'1(Bx)ibi'diifbi'<(Bx)ibi'+di0if(Bx)i>bi'+di(2.22)

 

and substitutingbi"=bi'di andBi'=Bidi componentwise, we arrive at the following problem:

maxx0min(bi"(B'x)i)(2.23)

 

or

maxx0D(x)(2.24)

 

where D (x) is the membership function of the decision solution set. The problem (2.24) is equivalent to solving the following linear programming problem

Maxλ

Subject toλbi"(B'x)i,i=0(1)m(2.25)x0

 

To explain the proposed approach, an application is presented as a numerical example which deals with the realization of the project shown in Figure 2.2. Table 2.3 shows the data of the project.

 
Table 2.3 Durations (weeks) and costs (€*106) of the project

Arc (i,j)

Task

Normal cost

Crashing cost

Normal time

Crashing time

Slope

(1,2)

A

4.060

6.200

27

20

0.306

(1,5)

B

3.740

4.205

36

31

0.093

(2,4)

C

5.670

7.090

29

26

0.473

(2,3)

D

0.350

0.379

20

16

0.007

(5,6)

E

0.350

0.435

25

21

0.021

(4,7)

F

4.790

6.400

39

33

0.268

(7,8)

G

0.130

0.130

3

3

-

(7,9)

H

0.010

0.025

4.5

3.5

0.015

(5,9)

I

0.590

0.590

29

29

-

 
Figure 2.2 Network associated to the fuzzy linear programming problem

graphics/fig2_2.jpg

The linear programming formulation for the traditional deadline makespan problem which sets up the appropriate execution option for each activity so that the project is completed by a desired deadline T with the minimum cost C can be expressed as follows:

MinC=0.306XA+0.093XB+0.473XC+0.007XD+0.021XE+0.268XF+0.015XH

 

subject tot1=0;t2t1+27XAt2t1+27XAt4t3+0Xf1t4t2+29XCt5t1+36XBt6t5+25XEt7t4+39XFt7t6+0Xf2t8t7+3XGt9t8+0Xf3t9t7+4.5XHt9t5+29XIx0;t9TXA7;XB5;XC3;XD4;XE4;XF6;XH1;

where Xi is the number of time units to crash (reduce duration of) task i and ti the time (in time units from the beginning of the project) task i is scheduled to start. Next, we shall apply the fuzzy approach and make the following assumption: the membership functioni(x) of the fuzzy sets characterizing the objective function rises linearly from 0 to 1 at the higher achievable values corresponding to the minimum time to carry out any task. This means that the level of satisfaction with respect to the improvement in the time to undertake, say task A, rises from 0 if is undertaken in 27 weeks or more (normal time), to 1 if it is undertaken in 20 weeks or less (crashing time). Thus, we have for task A

A(Bx)={1if(Bx)A201(Bx)A207if20<(Bx)A270if(Bx)A>27

 

and for the rest of the tasks:

B(Bx)={1if(Bx)B311(Bx)B315if31<(Bx)A360if(Bx)A>36C(Bx)={1if(Bx)C261(Bx)C263if26<(Bx)C290if(Bx)C>29D(Bx)={1if(Bx)D161(Bx)D164if16<(Bx)D200if(Bx)D>20E(Bx)={1if(Bx)E211(Bx)E214if21<(Bx)E250if(Bx)E>25F(Bx)={1if(Bx)A331(Bx)F336if33<(Bx)A390if(Bx)A>39H(Bx)={1if(Bx)A3.51(Bx)H3.5if3.5<(Bx)A4.50if(Bx)A>4.5

 

Including the unfuzzy constraints, we arrive at the following formulation

MaxλSubject toλ2070.3067XAt4t2+29XCλ3150.0935XBt5t1+36XBλ2630.4733XCt6t5+25XEλ1640.0074XDt7t4+39XFλ2140.0214XEt7t6+0Xf2λ3360.2686XFt8t7+3XGλ3.50.015XHt9t8+0Xf3t1=0t9t7+4.5XHt2t1+27XAt9t5+29XIt2t1+27XAx0;t9Tt4t3+0Xf1XA7;XB5;XC3;XD4;XE4;XF6;XH1;

 

The solution to the above problem corresponding to three different deadlines is shown in Table 2.4. For a deadline equal to 90 weeks, the maximum degree of ‘overall satisfaction’, λ = 2.860, is achieved for the solution XA = 0, XB = 0, XC = 3, XD = 4, XE = 4, XF = 6, and XH = 1. This is the ‘maximizing solution’, which means that the maximum level of satisfaction with respect to the improvement in the time to undertake the project, is obtained by reducing tasks C, D, E, F, and H in 3, 4, 4, 6, and 1 week respectively. If the deadline to undertake the project is reduced to 88 or 86 weeks, the maximum degree of ‘overall satisfaction’ is λ = 2.791 and λ = 2.704 respectively. For these deadlines, in addition to the above reductions, to obtain the maximum level of satisfaction with respect to the improvement in the time to undertake the project, task A must be reduced in 1.50 and 3.50 weeks.

 
Table 2.4 Solution

Time

λ

XA

XB

XC

XD

XE

XF

XH

90

2.860

0

0

3

4

4

6

1

88

2.791

1.50

0

3

4

4

6

1

86

2.704

3.50

0

3

4

4

6

1

Goal Programming

Although goal programming is itself a development of the 1950s, it has only been since the mid 1970s that goal programming received truly substantial attention. Much of the reason for such interest is due to goal programming's demonstrated ability to serve as an efficient and effective tool for the modelling, solution and analysis of mathematical models that involve conflicting goals and objectives.

In linear programming only one objective is permitted. Thus, even though multiple goals must be measured on a common scale, often profit or cost. Linear programming requires unidimensionality in the objective function, i.e., all goals must be expressed in common units and combined to give an overall single measure of effectiveness. Thus is the largest drawback of linear programming. Decision-makers need a methodology to attack problems in which a multitude of conflicting goals and subgoals exist. Goal programming can be used to help satisfying project managers. The requirements are that the project manager must be able to establish the goals and then to express the relationship between the decision variables and goals with linear functions. Once the project manager has provided and ordinal ranking of his/her goals, the goal programming model minimizes the deviation from the goals are satisfied to the fullest extent before lower order goals are considered (Hunnan, 1978).

In the area of Project Management, goal programming models have been used by quite a few authors. In particular, in the project crashing environment, Hanna (1978) incorporates considerations other than the project completion time and project cost into the typical critical path method. Factors such as share of the market, completion time of individual jobs, contractual agreements, and scarcity of resources such as men, materials, and machines are taken into consideration. Vrat and Kriengkrairut (1986) set four types of project goals: (i) to meet a new specified project completion period, (ii) to ensure that certain activities are not crashed for quality reasons, (iii) to maintain a specific budget target, and (iv) to minimize the total direct cost of crashing.

The general form of a goal programming problem may be expressed as:

Minimizei=1m(Poidi++Puidi)(2.26)

subject toj=1m(aijxj)+didi+=bi(2.27)

xj,di,di+0(2.28)

 

wheredi is the amount by which goal i is underachieved anddi+ is the amount by which goal i is overachieved; Poi is the priority associated withdi+ ; Pui is the priority associated withdi; xj(j=1,2,...,n) are the variables in the goal equations; bi(i = 1, 2, …, m) are the targets or goals; and aij are the coefficients of the variables.

Next, the above goal programming problem is applied to the project shown in Figure 2.3. Table 2.5 shows the normal time, crashing time, normal cost, crashing cost, and the slope.

 
Figure 2.3 Network associated to the goal programming problem

graphics/fig2_3.jpg

 
Table 2.5 Normal time, crash time, normal cost, crash cost and cost of crashing per day

Task

Arc (i,j)

ti,j

Normal cost (€)

Cost of crashing (€)

Normal time

Crash time

A

(1,2)

0.50

0.50

3,200

B

(2,8)

3.20

2.30

56,726

7,000

C

(2,3)

0.25

0.25

2,104

D

(3,4)

0.20

0.20

1,803

E

(4,8)

0.30

0.30

2,705

F

(2,5)

0.50

0.25

2,404

500

G

(5,6)

0.75

0.50

5,409

2,500

H

(6,7)

8.50

6.25

42,404

7,700

I

(7,8)

5.25

3.75

28,269

5,500

J

(5,8)

0.15

0.15

2,104

Solving the network through the critical path method algorithm (Kelley and Walker, 1999; Kelley, 1961), the normal time to undertake the project is 15.5 days, begin the activities A, F, G, H, and I critical activities. The normal cost undertaking the project in 15.5 days is €147,128.

Five activities (B, F, G, H, I) can be reduced which will permit reducing the time to complete the project. However, this reduction in time implies an increase in cost. As can be shown in Table 2.5 (last column), e.g., activity B may be reduced form 3.20 days to 2.30 days at a cost of $7,000 per unit time. The project manager must set up his/her goals in function of its interests in order to achieve a balance between time and cost.

Suppose that the project manager sets the following goals: (i) to reduce the time to undertake the project to no more than 12 days (goal 1); (ii) as this reduction in time will imply an increase in cost the project manager wants to limit the crashing costs to €100,000 (goal 2). To achieve these goals the projects manager must manage the project in such a way that the goals may be achieved. The formulation for this particular goal programming problem can be expressed as follows:

MinimizePo1d1++Po2d2+(2.29)

 

subject to

Goal 1t8+d1d1+=12(2.30)

Goal 2  7,000(3.2t2,8)+500(0.5t2,5)+2,500(0.75t5,6)+7,700(8.5t6,7)+5,500(5.25t7,8)+d2d2+=100,000(2.31)

ti,di,di+0(2.32)

 

Also

Crash Timeti,jNormal Timetjtiti,j0.50t1,20.50t2t1t1,22.30t2,83.20t3t2t2,30.25t2,30.25t4t3t3,40.20t3,40.20t8t4t4,80.30t4,80.30(2.33)t8t2t2,8(2.34)0.25t2,50.50t5t2t2,50.50t5,60.75t6t5t5,66.25t6,78.5t7t6t6,73.75t7,85.25t8t7t7,80.15t5,80.15t8t5t5,8

 

Whered1+ andd2+ are the amounts by which goals 1 and 2, are overachieved and P01 and P02 are the priorities associated with these goals respectively The ti and tj are the times corresponding to nodes i and j, and tij is the time to complete the activity (i, j). Equation (2.30) and (2.31) show how the goals have been converted into equations through the addition of deviation variables (di anddi+ ). The amount by which each one of the goals is overachieved (di+ ) is the variable to be minimized in this particular case. Equation (2.32) is the non-negativity constraint. The set of Equation in (2.33) indicates that the time to complete the activity (i, j) is between the normal time and the crash time and Equations in (2.34) are introduced to comply with the temporal sequence between the solution is given in Table 2.6

 
Table 2.6 Deviation variables

d1+ = 0

d1 = 0.75

d2+ = 0

d2 = 73,675

As can be appreciated in Table 2.6, goals 1 and 2 are achieved. The project is carried out in 11.25 (12 − 0.75) days and the total costs do not exceed €100,000.

An integer Programming Problem

Integer programming models are these optimization models in which some or all of the variables must be integer. The main difference between linear programming and integer programming models is that linear programming models allow fraction values for the decision variables, whereas integer programming models allow only integer values for integer-constrained decision variables. Many complex problems can be modelled using 0–1 variables and other variables that are forced to assume integer values. A 0–1 variable (often called a binary variable) is a decision variable that must be equal to 0 or 1, i.e., an activity that either is or is not undertaken. If the variable is 1, the activity is undertaken; if it is equal 0, the activity is not undertaken. In this section, an integer programming model which enables us to minimize the time to undertake a project meeting quality output standards and the corresponding costs is developed.

To form the model for this problem letTij the duration of activity i{i = 1, 2, …, l} in the critical path, andCij the cost of activity i using resource allocation n, with j = 1, 2, …, n. To estimate the overall quality performance at the project level the quality function suggested by El-Rayes and Kandil (2005) has considered activities to provide an overall quality at the project level using simple weighted approach.

 

i=1lWtik=1kWti,k*Qi,kn(2.35)

 

WhereQi,kn is the performance of quality indicator k in activity i using resource utilization n; Wti,k is the weight of quality indicator k compared to other indicators in activity i indicating the relative importance of this indicator to others being used to measure the quality of the activity; and Wti is the weight of activity i compared to other activities in the project representing the importance and contribution of the quality of this activity to the overall quality of the project.

Therefore, we may rewrite the final model as:

Minimizei=1lj=1nTijxij(2.36)

subjecttoi=1lj=1nCijxijC(2.37)

i=1lWtik=1kj=1nWti,kQi,knxijQ(2.38)

xij={1ifactivityiisundertaken0otherwise(2.39)

j=1nxij=1(2.40)

 

wherexij is the 0–1 variable and C and Q are the Cost and Quality target values respectively. Equation (2.39) implies that decision variables are integer and Equation (2.40) implies that each activity is undertaken once. The rest of the variables as above.

Two additional versions of the model can be proposed (San Cristóbal, 2009).The first one enables the project manager to minimize cost meeting quality and time objectives, whiles the second one enables to maximize quality meeting time and costs objectives respectively.

A) To Minimize Cost Meeting Quality and Time

i=1lj=1nCijxij(2.41)

subject to 1=1lj=1nTijxijT(2.42)

i=1lWtik=1kWti,kQi,knxijQ(2.43)

xij={1ifactivityiisundertaken0otherwise(2.44)

j=1nxij=1(2.45)

where T and Q are the Time and Quality target values respectively and the rest of variables as above.

B) To Maximize Quality Meeting Cost and Time Objectives

Minimize i=1lWtik=1kWti,kQi,knxij(2.46)

subject to 1=1lj=1nTijxijT(2.47)

i=1lj=1nCijxijC(2.48)

xij={1ifactivityiisundertaken0otherwise(2.49)

j=1nxij=1(2.50)

where T and C are the Time and Cost target values respectively and the rest of variables as above.

Next the integer programming problem is applied to the project shown in Table 2.7. Solving the network through the critical path method algorithm, the time to undertake the project is 22 weeks, being the activities A, D, and G critical activities.

 
Table 2.7 Tasks to undertake, predecessors, normal and crash duration

Tasks

Predecessors

Normal time (weeks)

Crash time (weeks)

A

9

6

B

8

4

C

5

1

D

A

8

2

E

B

7

4

F

C

5

3

G

D

5

4

Now suppose that the project manager, in the execution of the project, wants to meet the following objectives: to minimize time so that total costs do not exceed €8,000. In addition, two quality output objectives are established: that the overall quality achieved in the overall project exceeds an output, Q, of 98, and the quality achieved by the tasks D and E must be equal to or to exceed a quality output, Q, of 99. The formulation for this particular problem can be expressed as follows:

Minimizei=A,B,C,D,E,F,Gj=1,2Tijxij

 

subject to i=1lj=1nCijxij8,000

i=1lWtik=1kj=1nWti,kQi,knxij98

i=DWtik=1kj=1nWti,kQi,knxij99

i=EWtik=1kj=1nWti,kQi,knxij99

xij={1ifactivityiisundertaken0otherwise

i=1lj=1nxij=1

Table 2.8 shows the time and cost with two resources utilizations (n = 1 and n = 2) and the quality indicators (on a 0–100 scale) and the weights considered.

 
Table 2.8 Time, cost, quality indicators and weights considered

Task

Time (Weeks)

Cost (€)

Wti

Wti,k

Qi,kn

Wti,k

Qi,kn

n = 1

n = 2

n = 1

n = 2

 

k = 1

n = 1

n = 2

k = 2

n = 1

n = 2

A*

9

6

1,000

1,600

0.10

0.8

100

98

0,2

98

96

B

8

4

900

1,800

0.10

0.7

100

96

0,3

98

97

C

5

1

700

800

0.15

0.6

100

98

0,4

98

96

D*

8

2

900

1,900

0.10

0.7

100

98

0,3

98

96

E

7

4

700

1,500

0.15

0.5

100

98

0,5

98

96

F

5

3

500

500

0.20

0.7

100

98

0,3

98

96

G *

5

4

800

2,300

0.20

0.8

100

98

0,2

98

96

* * Critical activity.

This problem was solved using Solver de Microsoft (Microsoft, 2007), and the optimal solution is given in Table 2.9. The minimum time to undertake the project is 18 weeks with a total cost of €7,600, an amount lower than the objective of €8,000. As regard as quality, the two objectives established are achieved. The quality for the overall project is 98.77 (upper than 98) and the corresponding to the activities D and E, 99.4 and 99 respectively.

 
Table 2.9 Optimal solution

Time (T) (Weeks)

18

Cost (C) (€)

7,600

Quality (Q) (Overall Project)

98,77

Quality (Q) (Activity D)

99,4

Quality (Q) (Activity E)

99

Table 2.10 shows the activities that must be undertaken with resources utilization n = 1 and n = 2. Activities B, C, D, E, and F, are undertaken with resources utilization n = 1, while activities A, and G are undertaken with resources utilization n = 2.

 
Table 2.10 Activities to undertake with resources n = 1 and n = 2

Activity

A

B

C

D

E

F

G

n =1

0

1

1

1

1

1

0

n =2

1

0

0

0

0

0

1

Submit your own content for publication

Submit content