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 multiobjective 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 multiobjective decisionmaking methods are presented, namely, the traditional timecost tradeoff problem, fuzzy linear programming, goal programming and an integer programming problem.
Linear Programming Formulation of the TimeCost Tradeoff 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, nonlinear, and discrete formulations of the timecost tradeoff problem (Liberatore and PollackJohnson, 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 multicriteria project crashing problem with linear timecost tradeoff, and proposed a goal programming formulation. The nonlinear 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 concavetype relationships, a mixed integer programming problem has to be attempted, but a convextype relationship appears to be a more practicable assumption in the context of project crashing. If the convextype 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 nonlinear convextype relationship. The discrete version of the timecost problem required specifying a set of discrete processing times and associated costs for each activity which is a different way to model nonlinearity. The budget version of the discrete problem has been shown to be strongly NPhard (De et al., 1997).
The linear programming formulation for the traditional deadline makespan problem can be expressed by (Liberatore and PollackJohnson, 2006):
where
C: total incremental cost for reducing project makespan;
x_{i}: number of time units to crash (reduce duration of) task i;
t_{i}: 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);
d_{i}: duration in time units of task i;
c_{i}: cost per time unit to crash task i;
u_{i}: 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.
The formulation for this linear programming problem can be expressed as:
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.
Liberatore and PollackJohnson (2006) extend the linear formulation of the deadline timecost 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 timecost tradeoff scenario:
where
b_{ij}: normal cost of activity (i, j);
a_{ij}: marginal cost increase for varying the normal time;
n_{ij}: normal time to complete activity (i, j);
y_{ij}: actual duration of activity (i, j);
x_{i}: 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), y_{ij}, would be limited to be within a range from τ_{ij} to μ_{ij}, where τ_{ij} and μ_{ij} represent the lower and upper bounds on y_{ij} 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 nonnegative time.
A Linear TimeCost Tradeoff 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 x_{ij} 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 x_{ij} must assume binary variables only. The critical path method problem with n nodes is formulated as:
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 x_{ij} = 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:
and the solution is D = 24(days), with x_{1,2} = 1; x_{2,4} = 1; and x_{4,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 decisionmaker’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 nonfuzzy 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:
the adopted fuzzy version is
where z_{0} means an aspiration level of the decisionmaker. We now define membership function$\underset{\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}i}{\propto}$ such that
where i indicates de i_{th} row of B or b′, B is the matrix A augmented by the rows of the objective function, b′ the righthand 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
and the maximizing decision
Using the simplest kind of membership function, i.e., linear function of the type
and substituting${b}_{i}^{"}=\raisebox{1ex}{${b}_{i}^{\text{\'}}$}\!\left/ \!\raisebox{1ex}{${d}_{i}$}\right.$ and${B}_{i}^{\text{'}}=\raisebox{1ex}{${B}_{i}$}\!\left/ \!\raisebox{1ex}{${d}_{i}$}\right.$ componentwise, we arrive at the following problem:
or
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
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.
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:
where X_{i} is the number of time units to crash (reduce duration of) task i and t_{i} 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 function$\underset{\text{\hspace{0.17em}}\text{\hspace{0.17em}}i}{\propto}\left(x\right)$ 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
and for the rest of the tasks:
Including the unfuzzy constraints, we arrive at the following formulation
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 X_{A} = 0, X_{B} = 0, X_{C} = 3, X_{D} = 4, X_{E} = 4, X_{F} = 6, and X_{H} = 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.
Time 
λ 
X_{A} 
X_{B} 
X_{C} 
X_{D} 
X_{E} 
X_{F} 
X_{H} 

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. Decisionmakers 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:
where${d}_{i}^{}$ is the amount by which goal i is underachieved and${d}_{i}^{+}$ is the amount by which goal i is overachieved; P_{oi} is the priority associated with${d}_{i}^{+}$ ; P_{ui} is the priority associated with${d}_{i}^{}$; ${x}_{j}(j=1,2,\mathrm{...},n)$ are the variables in the goal equations; b_{i}(i = 1, 2, …, m) are the targets or goals; and a_{ij} 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.
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:
subject to
Also
Where${d}_{1}^{+}$ and${d}_{2}^{+}$ are the amounts by which goals 1 and 2, are overachieved and P_{01} and P_{02} are the priorities associated with these goals respectively The t_{i} and t_{j} are the times corresponding to nodes i and j, and t_{ij} 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 (${d}_{i}^{}$ and${d}_{i}^{+}$ ). The amount by which each one of the goals is overachieved (${d}_{i}^{+}$ ) is the variable to be minimized in this particular case. Equation (2.32) is the nonnegativity 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
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 integerconstrained 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 let${T}_{i}^{j}$ the duration of activity i{i = 1, 2, …, l} in the critical path, and${C}_{i}^{j}$ 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 ElRayes and Kandil (2005) has considered activities to provide an overall quality at the project level using simple weighted approach.
Where${Q}_{i,k}^{n}$ is the performance of quality indicator k in activity i using resource utilization n; Wt_{i,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 Wt_{i} 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:
where${x}_{i}^{j}$ 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
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
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.
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:
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.
Task 
Time (Weeks) 
Cost (€) 
Wt_{i} 
Wt_{i,k} 
${Q}_{i,k}^{n}$ 
Wt_{i,k} 
${Q}_{i,k}^{n}$ 


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