Managing Time, Cost & Quality

ARTICLE IN PRESS

Applied Mathematics and Computation xxx (2006) xxx–xxx www.elsevier.com/locate/amc

On the discrete time, cost and quality trade-off problem Hamed R. Tareghian, Seyyed Hassan Taheri

*

Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, Iran Department of Mathematics, University of Khayam, Mashhad, Iran

Abstract In this paper a solution procedure is developed to study the tradeoffs among time, cost and quality in the management of a project. This problem assumes the duration and quality of project activities to be discrete, non-increasing functions of a single non-renewable resource. Three inter-related integer programming models are developed such that each model optimizes one of the given entities by assigning desired bounds on the other two. Different forms of quality aggregations and effect of activity mode reductions are also investigated. The computational performance of the models is presented using a numerical example.  2006 Elsevier Inc. All rights reserved. Keywords: Project management; Discrete time; Cost and quality trade-off problem

1. Introduction The discrete time–cost trade-off problem, hereafter referred to as DTCTP, is a well-known problem from the project management literature (see e.g. [1,2]). The instances of this problem are the so-called projects that consist of a finite set A of activities together with a partial order  on A. The DTCTP occurs when the duration of project activities are a discrete non-increasing function of a single non-renewable resource committed to them. Any activity, ij 2 A, may be executed in say, k different modes, where the rth mode (1 6 r 6 k) takes tijr time and costs an amount cijr of money. Without loss of generality, it is assumed that all values of tijr and cijr are non-negative integers. The executions of activities in A depend on their precedence relations. In other words, if ij  jk, then activity ij may not be started unless activity jk has been completed. All activities are available for processing at time zero. A feasible solution ~ s ¼ fr1 ; . . . ; rjAj g of such a DTCTP consists of assigning an execution mode, r, (1 6 r 6 k) to activity ij 2 A. The cost cð~ sÞ of solution ~ s is the total amount of money spent on ~ s. The duration dð~ sÞ of solution ~ s is the finish time of the earliest start schedule that assigns duration tijr to activity ij 2 A. In this schedule considering the precedence relations, each activity starts at the earliest possible time. As such the

*

Corresponding author. E-mail addresses: [email protected] (H.R. Tareghian), [email protected] (S.H. Taheri).

0096-3003/$ - see front matter  2006 Elsevier Inc. All rights reserved. doi:10.1016/j.amc.2006.02.029

ARTICLE IN PRESS 2

H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

duration of solution ~ s equals the length of the longest path in the partial order, where the length of the path is the sum of the durations of the activities in the path. The objectives of the solution procedures to DTCTP can be threefold. The so-called deadline problem aims at minimizing the total cost of the project such that a given deadline is met, while the budget problem involves minimizing the project duration without exceeding a given budget. There is a tradeoff between cost and time. Solutions with shorter durations usually cost more, while solutions with low costs usually take longer. By fixing either cost or duration, two related optimization problems are obtained with the objective of minimizing the other parameter. A third objective is to construct the complete and efficient time/cost profile over the set of feasible project durations. Several procedures have been proposed to optimally solve the DTCTP. Early optimal solution procedures are mainly based on dynamic programming e.g. [2,3], or enumeration algorithms [4]. The current exact algorithms still rely on dynamic programming, but in addition exploit the decomposition structure of the project network (e.g. see [5] for one of the implementations of series-parallel decompositions). A Lagrangian relaxation-based heuristic for activity on arc (AoA) networks is developed in [6]. It follows from [7] that both deadline and budget problems are very difficult to solve; they are, in fact, strongly NP-hard for general project networks. It was recently suggested that the quality of a completed project may be affected by project crashing [8]. As such, in expedition of a project, its quality should also be taken into consideration along with the time and cost tradeoffs. Considering the inter-twined effects of time, cost and quality in project management, it seems reasonable to develop a mathematical model, hereafter referred to as DTCQTP, which considers project’s time, cost and quality simultaneously. In the DTCQTP, like DTCTP, project’s activities are performed in one of several alternatives. For each activity a set of time, cost and quality triplet, referred to as mode, are given. The quality of each activity is specified discretely at a scale of [0.75–0.99]. The overall project quality is a function of quality attained at each activity. The form of this function depends on the nature of the problem and the definition of quality adapted. The purpose of this problem is to complete the project at a given deadline, provided that its total cost is minimized while its overall quality is maximized. The literature on solution methods for the DTCQTP is scant. The authors are not aware of any work in the literature that has studied the DTCQTP. The procedure developed in [8] which considers the tradeoffs among cost, time and quality in continuous mode, was later used to study an actual cement factory construction project in Thailand [9]. In this paper, we develop three inter-related binary integer programming models that assist project managers make trade-off decisions. In the following section we formally describe the problem and present the mathematical models. In Section 3, we discuss the results using an illustrative example. A mechanism is proposed for activity mode reductions and its effect on models performance is discussed. In the last section, a summary is given and some conclusions are drawn. 2. Problem statement Assume that the specifications of a project is given in the form of a directed acyclic graph G = (V, A), in which V is the set of nodes, representing events, and A is the set of arcs, representing activities, in the AoA mode of representation. For each activity, ij 2 A, a set Mij of modes, is given. For each mode, r 2 Mij, let tijr, cijr and qijr denote the duration, the cost and the quality attained by performing activity ij in mode r, respectively. It is assumed that for each activity ij 2 A, tijr > tijr+1 implies cijr < cijr+1, but qijr > qijr+1. The nature of each activity determines the quality level (0 6 qijr 6 1) assigned to it. The objective is to construct the complete and efficient time, cost and quality profile to offer decision support in crashing a project. The following notation is used to represent the relevant data in the DTCQTP problem: V A B Mij tijr cijr

set of nodes, V = {1, 2, . . . , n} set of activities set of critical activities set of execution modes for activity, ij, ij 2 A duration of activity ij when executed in mode, r, r = 1, . . . , jMijj cost of performing activity ij in mode, r, r = 1, . . . , jMijj

ARTICLE IN PRESS H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

qijr xi aij Cmax Tmax

3

quality of performing activity ij in mode, r, r = 1, . . . , jMijj occurrence time of node, i, i 2 V lower bound for the quality of activity, ij, ij 2 A, r = 1, . . . , jMijj upper bound for project cost upper bound for project deadline

The three objective functions sought to be optimized in the DTCQTP, namely project’s quality, duration, and cost can be defined as follows: 1 X X f1 ¼ q xijk ; ð1Þ jAj ij2A k2M ij ijk X X X f2 ¼ tijk xijk þ xi ; ð2Þ ij2B k2M ij

f3 ¼

X X

i2V

ð3Þ

cijk xijk .

ij2A k2M ij

In order to assist decisions regarding project crashing, we have developed three mathematical models to optimize the above functions. The first model follows: max f 1 ð4Þ s:t: X xijr ¼ 1; ij 2 A; ð5Þ r2M ij

xj  xi P X X

X

tijr xijr ;

ij 2 A; i; j 2 V ;

ð6Þ

r2M ij

cijr xijr 6 C max ;

ð7Þ

ij2A r2M ij

ð8Þ

xn 6 T max ; x1 ¼ 0; xi P 0;

i 2 V ; integer;

xijr ¼ f0; 1g;

ij 2 A; r 2 M ij :

ð9Þ ð10Þ ð11Þ

The second model which shares constraints (5)–(7), and (9)–(11) from the first model is min f 2 s.t. X qijr xijr P aij ;

ð12Þ ij 2 A.

ð13Þ

r2M ij

And finally, the third model that shares constraints (5), (6), (8)–(11) from the first model is min f 3 s.t. X qijr xijr P aij ;

ð14Þ ij 2 A.

ð15Þ

r2M ij

Objective function (1) maximizes the project’s overall quality, while objective functions (2) and (3) minimize the project’s total duration and costs respectively. Constraint (5) ensures that one and only one execution mode is assigned to each activity. Constraint (6) preserves the precedence relations between project activities. Constraint (7) defines the project’s cost threshold, while constraint (8) defines the project deadline. Constraint (9) forces the project not to start earlier than time zero. Constraint (10) ensures non-negativity of decision variables, while constraint (11) is a binary mode indicator which is 1 when mode k is assigned to activity, ij, and 0, otherwise. Finally, constraint (13) enforces that each activity preserves a certain level of quality.

ARTICLE IN PRESS 4

H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

3. Computational study In order to illustrate our proposed method, we used DAGEN [10] to generate an instance of a project network. The project so generated consists of 45 activities whose coefficient of complexity equals 4.5 and its complexity index equals 9 (see Fig. 1). In this network, there are 256 paths that link source (node 1) to sink (node 10). The number of modes per activity is randomly chosen from jMijj 2 [2, 10]. For each activity, the execution mode is generated as follows: first the number of modes for activity ij is generated, i.e. jMijj  DU (2, 10). Then the duration of each mode is randomly sampled from DU (1, 100). After durations for all the execution modes are generated, they are sorted in ascending order, i.e. tosij = {t1, t2, . . . , tjMijj; ti 6 ti+1 "i = 1, . . . , jMijj  1}. The corresponding cost for t1 which is incidentally the maximum cost mode is sampled randomly from DU(500, 800). The costs for other modes are determined as follows: ci ¼ ci1  si ðti  ti1 Þ;

i ¼ 2; . . . ; jM ij j;

where si is u(1, 3), s1 = 1, and ci, ti are the cost and the duration for mode i respectively. The quality attained by each activity under normal circumstances is assumed 99%. The quality for the other modes of execution is generated as follows. As it is assumed that the activity duration compressions do not adversely affect activity qualities by the same magnitude, we have classified activities into five different categories. The quality attained by activities in categories 1 to 5 is allowed to vary between 0.95–0.99, 0.90–0.99, 0.85–0.99, 0.80–0.99 and finally 0.75–0.99 respectively. The project as described above was used to study the performance of the models described in (1)–(15). The results obtained by solving the given models are shown in Tables 1–3 respectively. Version 3 of the optimizer called LINGO was available and hence was used to solve the models. The shortest possible time for completing the project is 189. Table 1 shows the cost of the project as its deadline and quality varies. For model 3, T 2 {189, 220, 270, 320, 350, 410, 490, 585, 650, 700, 745, 750}, and project quality varies between 0.75 and 0.99 in increments of 0.05. It is evident that high quality and short deadlines can not be achieved simultaneously. As

Fig. 1. Project network.

ARTICLE IN PRESS H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

5

Table 1 Project costs when its quality and deadline is varied Deadline

0.75

0.80

0.85

0.90

0.95

0.99

189 220 270 320 350 410 490 585 650 700 745 750

26,239 25,643 24,940 24,617 24,488 24,184 23,993 23,839 23,766 23,706 23,651 23,651

NF NF 25,060 24,664 24,488 24,184 23,993 23,839 23,766 23,706 23,651 23,651

NF NF NF 25,009 24,681 24,368 24,061 23,853 23,766 23,706 23,651 23,651

NF NF NF NF NF 24,634 24,103 23,874 23,766 23,706 23,651 23,651

NF NF NF NF NF NF NF NF 23,823 23,746 23,651 23,651

NF NF NF NF NF NF NF NF NF NF 23,651 23,651

NF: not feasible.

Table 2 Project deadline when its quality and budget is varied Budget

0.75

0.80

0.85

0.90

0.95

0.99

23,651 23,670 23,750 23,850 24,000 24,200 25,200 25,700 26,000 26,200 26,239 26,300

745 735 664 583 483 403 242 212 198 195 189 189

745 735 664 583 483 403 263 256 256 256 256 256

745 735 667 593 505 445 305 305 305 305 305 305

745 735 670 594 519 471 409 409 409 409 409 409

745 745 700 639 591 588 508 588 588 588 588 588

745 745 745 745 745 745 745 745 745 745 745 745

Table 3 Project quality when its deadline and budget is varied Budget

189

220

270

320

350

410

490

585

650

700

745

750

23,651 23,670 23,750 23,850 24,000 24,200 25,200 25,700 26,000 26,200 26,239 26,300

NF NF NF NF NF NF NF NF NF NF 0.933 0.933

NF NF NF NF NF NF NF 0.947 0.948 0.948 0.948 0.948

NF NF NF NF NF NF 0.964 0.964 0.964 0.964 0.964 0.964

NF NF NF NF NF NF 0.973 0.973 0.973 0.973 0.973 0.973

NF NF NF NF NF NF 0.976 0.976 0.976 0.976 0.976 0.976

NF NF NF NF NF 0.975 0.982 0.982 0.982 0.982 0.982 0.982

NF NF NF NF 0.979 0.986 0.986 0.986 0.986 0.986 0.986 0.986

NF NF NF 0.984 0.987 0.987 0.987 0.987 0.987 0.987 0.987 0.987

NF NF NF 0.988 0.988 0.988 0.988 0.988 0.988 0.988 0.988 0.988

NF NF 0.989 0.989 0.989 0.989 0.989 0.989 0.989 0.989 0.989 0.989

0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990

0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990

NF: not feasible.

project deadlines extend, the project cost is reduced irrespective of its quality. However, the extension of project deadline beyond a certain limit does not affect the project costs for any level of quality. Table 2 depicts how project deadline is affected by quality and level of budget. For model 2, project budget varies from 23,651 to 26,300, while its quality varies between 0.75 and 0.99 in increments of 0.05.

ARTICLE IN PRESS 6

H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

Table 4 Project quality when its deadline and budget is varied Budget

189

220

270

320

350

410

490

585

650

700

745

750

23,651 23,670 23,750 23,850 24,000 24,200 25,200 25,700 26,000 26,200 26,239 26,300

NF NF NF NF NF NF NF NF NF NF 0.931 0.931

NF NF NF NF NF NF NF 0.941 0.946 0.946 0.946 0.946

NF NF NF NF NF NF 0.963 0.963 0.963 0.963 0.963 0.963

NF NF NF NF NF NF 0.969 0.972 0.972 0.972 0.972 0.972

NF NF NF NF NF NF 0.975 0.975 0.975 0.975 0.975 0.975

NF NF NF NF NF 0.974 0.981 0.981 0.981 0.981 0.981 0.981

NF NF NF NF 0.979 0.986 0.986 0.986 0.986 0.986 0.986 0.986

NF NF NF 0.982 0.987 0.987 0.987 0.987 0.987 0.987 0.987 0.987

NF NF NF 0.988 0.988 0.988 0.988 0.988 0.988 0.988 0.988 0.988

NF NF 0.989 0.989 0.989 0.989 0.989 0.989 0.989 0.989 0.989 0.989

0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990

0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990 0.990

NF: not feasible.

When the budget is low, quality level does not affect the deadline. However, by increasing the budget shorter deadlines are possible at all levels of quality. The effect of quality on project deadline is more evident at higher budgets. For instance, when the budget is 23,651 irrespective of quality level, the deadline can not be reduced from 745. However, if the budget is increased by say 11% to 26,239, then the project deadline can be shortened by at least 74% to 189. Table 3 displays how project quality is affected by project deadlines and level of budget. For model 1, T 2 {189, 220, 270, 320, 350, 410, 490, 585, 650, 700, 745, 750}, while project budget varies from 23,651 to 26,300. Allocating higher budgets make it possible to obtain higher level of quality and also shorter deadlines. At low levels of budget, and with project deadlines less than 745, no solution is feasible. However, if one increases the budget level by only 10% to 26,239, feasible solutions at different levels of quality are obtained. In the above models, we have utilized the arithmetic mean for quality aggregation. In Table 4, we give results when other aggregation method such as geometric mean is used. In Table 4 the effect of project budget and project deadline on project quality is depicted, when the project quality is the geometric mean of individual activities quality. As expected, since the quality of activities are not very dispersed, the effect of using geometric mean as the aggregation method, are not significantly different from Table 3, where arithmetic mean has been used as the aggregation method. 3.1. Activity mode reductions In this section we describe a mechanism that enables us to simplify the problem by eliminating some of the activities execution modes. As most of the models variables are binary, one can reduce the number of variables by eliminating some of the execution modes from consideration, and hence, simplify the solution process for an instance of the problem. Let tosij ¼ ft1 ; t2 ; . . . ; tjM ij j ; ti > tiþ1 ; 8i ¼ 1; . . . ; jM ij j  1g be the duration modes for activity ij sorted in ascending order. For each path, v, linking source to sink, we compute its longest duration X lv2P ¼ tij1 ; ij2v

where P is the set of all source to sink paths, v = 1, . . . , jPj. From the above paths, we create a set, x, that holds those paths whose length exceed Tmax, i.e. x ¼ fv 2 P jlv > T max g. We now define, w, a set holding activities that lie in at least one of the paths, say g 2 v, (v 2 x). For all the activities in

ARTICLE IN PRESS H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

7

Table 5 Effect of activity mode reductions on the models performance Deadline

II

0.75

0.80

0.85

0.90

0.95

0.99

189 220 270 320 350 410 490 585 650 700 745 750

247 245 221 200 173 138 78 24 7 1 0 0

+6.3 5.0 7.0 4.8 +9.1 +10.3 +19.7 +38.8 +36.7 +63.1 +99.5 +99.5

NF NF 13.0 +11.2 +16.1 +1.6 +16.2 +34.3 +46.8 +63.5 +99.5 +99.5

NF NF NF +6.6 10.1 +10.9 15.2 +34.5 +53.2 +61.8 +99.4 +99.4

NF NF NF NF NF 26.7 +15.7 +22.6 +52.6 +65.1 +99.5 +99.5

NF NF NF NF NF NF NF NF +35.5 +50.8 +99.5 +99.5

NF NF NF NF NF NF NF NF NF NF +99.5 +99.5

NF: not feasible. II: no. of paths whose lengths exceed the given deadline (remember that there are 256 paths in the network).

f¼Aw only one single execution mode is considered, namely their longest duration mode. Mode reductions may also be possible for those activities that lie in paths which jointly belong to P  x and x. Obviously, the mode reductions for these activities should not affect the feasibility of the solution. The solution remains feasible if by utilizing the remaining duration modes of activities, the given deadline can be met. However, if there is more than one such activity for mode reductions, some considerations should be given to their relative costs. For this, we sort activities of each path in ascending order according to the value of s calculated as tijk  tijkþ1 s¼ ; ij 2 v; k ¼ 1; . . . ; jM ij j  1. cijkþ1  cijk As such, in each path, activities on top of the list are better candidates costwise for mode reductions. We have applied this mechanism to our solution procedure. Table 5 presents the effect of using this mechanism on the number of iterations used to solve the given problem. It shows the percentage of increase () or decrease (+) in the number of iterations used to solve the problem. As it can be seen, the use of the mode reduction mechanism can reduce the number of iterations up to 99.5%. However, some increase in the number of iterations can also be observed. This may be attributed to the nature of the algorithm that the optimizer, namely LINGO uses to solve the problem. 4. Summary and conclusions In this paper we developed three binary integer programming models to assist decisions regarding the tradeoffs among cost, duration and quality of a project, where cost and quality are discrete non-increasing functions of project duration. The inter-twined effect of time, cost and quality in DTCQTP was shown. In addition, some quantitative results were also presented. Different methods of quality aggregation methods were studied. A mechanism for activity mode reduction was developed, and its effect on the performance of the models was investigated. The authors are presently working on a hybrid metaheuristic combining scatter search and electromagnetism ideas to solve large scale DTCQTP. References [1] P. De, E.J. Dunne, J.B. Gosh, C.E. Wells, The discrete time–cost tradeoff problem revisited, European Journal of Operational Research 81 (1995) 225–238. [2] D.R. Robinson, A dynamic programming solution to cost–time tradeoff for CPM, Management Science 22 (1975) 158–166. [3] T.J. Hindelang, J.F. Muth, A dynamic programming algorithm for decision CPM networks, Operations Research 27 (1979) 225–241. [4] J.H. Patterson, R.T. Harvey, An implicit enumeration algorithm for the time/cost tradeoff problem in project network analysis, Foundations of Control Engineering 4 (1979) 107–117.

ARTICLE IN PRESS 8

H.R. Tareghian, S.H. Taheri / Applied Mathematics and Computation xxx (2006) xxx–xxx

[5] E. Demeulemeester, W. Herroelen, S.E. Elmaghraby, Optimal procedures for the discrete time/cost trade-off problem in project networks, European Journal of Operational Research 88 (1996) 50–68. [6] C. Akkan, A Lagrangian heuristic for the discrete time–cost tradeoff problem for activity-on-arc project networks, Working Paper, Koc University, Istanbul, 1998. [7] V.G. Deineko, G.J. Woeginger, Hardness of approximation of the discrete time–cost tradeoff problem, Operations Research Letters 29 (2001) 207–210. [8] A.J.G. Babu, N. Suresh, Project management with time, cost and quality considerations, European Journal of Operational Research 88 (1996) 320–327. [9] D.B. Khang, Y.M. Myint, Time, cost and quality trade-off in project management: a case study, International Journal of Project Management 17 (4) (1999) 249–256. [10] M.K. Agrawal, S.E. Elmaghraby, W. Herroelen, DAGEN: a generator of test sets for project activity nets, European Journal of Operational Research 90 (1996) 376–382.