An optimal model for construction
time-resource tradeoff problem[(]
Xianjia. Wang1, Zhongping. Wan2
1 Institute of Systems Engineering, Wuhan University, Wuhan 430072 China.
2 School of Mathematics and Statistics, Wuhan University, Wuan 430072 China.
Abstract: So-called the time-resource tradeoff problem, it is a specified project content with a set of activities to determine an efficient project scheduling according to some precedence relationship and the renewable resource constraints, under the objective of minimizing the project duration and the total consumed-resources cost. In this paper we propose a new mathematical model with time-resource trade-off problem, in which objective functions with conflict one another is defined as adaptive and adjustable between the project duration and the total consumed-resources cost in all period. This adjustment is based on the corresponding Lagrange multiplier, which is viewed as price information. It helped us to can control and monitor the resources utilized situation at any time. A satisfied feasible solution can be obtained in our solution procedure by compromising and adjusting relationship between the project duration and the total consumed-resource cost. A numerical example is illustrated. In addition, both the project duration and the total consumed-resources cost in the Lagrangian relaxation form associated with the resource constraints are interpreted as a two-player game: one player offers prices to purchase lots of resource available so as to minimize the project duration; the other sell the redundant resources based on prices to maximize profit (that is the resource available be wasted as small as possible).
Keywords: time-resource tradeoff problem; resource-constrained; scheduling; Lagragian relaxation; solution procedure.
1. Introduction
The major objective of the construction project planning and scheduling is usually to determine the completion times of the project in a way, which minimizes the project completion cost according to some precedence relationship of project activities and the available resource limited. The cost of completing an activity of a project is actually an aggregated cost of usage of several resources required to perform the tasks. Generally, the activity duration can be regarded as a function of resource availability. A time-cost tradeoff problem generates minimum cost project schedules as a function of project realization times, and it is one of the most important aspects of construction planning and control. Many models and solution procedures have been developed for solving time-cost tradeoff problems (Leu et al 2001; Li et al 1999; and so on). Simin and Horn (1996) extended the multiple objective mathematical models with the minimization of project cost and duration (Deckro and Hebert 1990) to the minimization problem of resource cost for each activity and project duration for trade-offs in project scheduling. In these models, it is implicitly assumed that resources are available in infinite amounts. Clearly, it is not actually for this assumption in the engineering practice. Based on this extended framework, we here present a time-resource tradeoff model with the precedence relationship and the resource constraints. Our problem is very different from model presented Simin and Horn, it mainly will show the following several aspects: 1) the activity duration is treated as a decision variable; 2) the resource is limited in the time-resource tradeoff problem; 3) the two-objective time-resource tradeoff scheduling problem in which the total consumed-resources cost is incorporated one. It is evident that the resource-constrained problem must be considered for time-resource tradeoff project scheduling with resource limited, this is almost similar to the resource constrained time-cost tradeoff project scheduling problem (Brucker et al 1999; Icmeli and Erenguc 1996). Reason is that because the minimization of completion duration of project activities (it is actually in a sense of PERT- or CPM-path) is impractical, and the resource conflict situation for which could be taken place at any time in the project scheduling process cannot effectively be monitored. Therefore that the resource-constrained time-resource tradeoff project scheduling problem is considered is necessary and becomes practically more appealing, despite it could become more difficult to solve.
2. Time-resource trade-off model
The time-resource tradeoff for project scheduling problem involves scheduling, resource cost, and determining the duration of project activities, in such a way that resource (some of which are available only in limited amounts) and precedence constraints are met. Preemption is not allowed. Our objective is to minimize several resource costs and completion duration of project activities. Here, we assume a project in which the duration of each activity is unknown, thus its value might fall between the normal and crash duration of the activity. The resource cost and the project duration are assumed to have some decreased function relationship, e.g. linear or other function relationship. The following notations defined will be used in the our model:
= the number of activities in the project;= the number of so-called renewable resource types; = the completion time (duration) of activity ; = the set of pairs of activities indicating finish-start precedence relation, i.e. number of events in the project network; = the set of activities in progress during time interval=, i.e. the set of on-going activities at time ; = the normal duration for activity .= the crash duration (the possible lower bound) for activity .= the duration (or processing time) variable of activity that takes integer values between and .= the total availability of resource type at time .= the cost amount of resource required for activity .= the amount of resource type that required per period by activity corresponding to duration variable .
Without loss of generally, we assume that the activity 1 denotes the start of the project. Let the activity , the dummy activity, denotes the completion of the project. The dummy activity does not require any resource nor does it requires any duration, i.e. and .
Our optimization model for time-resource tradeoff problem for resources can be written as follows:
Min (1)
Min (2)
s.t. (3)
for activity (4)
for , . (5)
Expressions (1) and (2) show that the problem is a two-objective programming one, in which is the minimization of the project completion and the total cost of consuming resources, respectively. Constraint (3) ensures that precedence relationships are satisfied. Constraint (4) indicates that the duration variable of activity be bounded. Constraint (5) is a conceptual statement of the resource constraints, in which the sum of resource requirements does not exceed their respective capacities availability in any period, i.e. the resource constraints cannot be violated.
Remark 2.1 The problem will become a resource-constrained project scheduling with duration variable if we delete the second objective function in our model, i.e.
Min (6)
s.t. (3), (4) and (5).
3. Lagrangian relaxation of resource constraints
This section, the Lagrangian relaxation of the resource constraints (5) will be considered. In terms of the relaxation approach, the resource leveling results would be affected by changing multipliers associated with resource constraints. Therefore the resource utilization will be monitored at any time.
Let be the corresponding to non-negative Lagrange multipliers to the resource constraints (5). We have the following Lagrangian function:
(7)
For convenience, we consider the following single objective problem
Min (8)
s.t.
for activity
for ,
(the absolute due date of project).
It follows that its dual problem corresponding to the programming (8) is
(9)
where
= (10)
and
. (11)
The optimization problem may hight the partial dual problem corresponding to the original two-objective optimization problem. Obviously, the dual function is separable in the contributions to the dual objective of the individual resource type . Each sub-problem can be interpreted as a profit maximization problem (i.e. the resource-wasted as less as possible) for resource type when it sees the price at time .
We may interpret the dual optimization (9) using the following “two-firm” model. Firm P, a minimizing resource cost utility (i.e. minimizes the total consumed-resources cost), facing resource supply at time (for convenience, the subscript is omitted), may sell the firm Q the redundant resource available in the precondition of completing time of the project scheduling is not affected (i.e. it means selection of the duration of activity, ). The firm Q, for its profit (e.g. it minimizes the completion time of the project), offering firm P the price , needs to purchase lots of the resource available. Firm P’s objective is to minimize its total consumed-resource cost. Consequently it may be redundant resources available. Firm Q’s problem is to adjust the prices of so as to achieve its maximum benefit (i.e. completion duration of the project as early as possible). Hence it will purchase more redundant resources from the firm P, considering that the firm P will minimize its resource cost.
4. The solution procedure
To solve our time-resource tradeoff project scheduling problem, in the following solution procedure given, which could be called a compromise Lagrange relaxation procedure. In this method, we can adopt the following three-phase structure strategy based on some effective algorithms and Lagrange relaxation method as well as modification techniques. A satisfied feasible (or near-optimal) solution to the time-resource tradeoff problem is only obtained by the procedure. The solution procedure is in detail described as follows:
Initialization process: Select duration of activity at random in the interval defined by the crash and normal duration of activity, i.e. =; or set all activity duration to normal durations.
Phase 1: Solve the problem (6) to determine completion duration of the project by means of some effective algorithms of the resource-constrained project scheduling, e.g. genetic algorithm. Check to see if the completion duration of the project obtained by Phase 1 algorithm is less than the due date of the project. If the project duration is less than its due date, go to Phase 2; Otherwise, the duration of some activities (e.g. the activity of which is that the number (or cost) of resources required times the duration of the activity is biggish) be decreased such that they are located within the interval , back to Phase 1.
Phase 2: Test to see if there is a resource violation at any time in the current solution. If there is no resource conflict, then go to Phase 3. Otherwise, solve the problem (9) where the duration variable is limited within the interval to determine the total consumed-resources cost of the project by using of some primal-dual optimization algorithms in the nonlinear programming with discrete or continuous variables.
Phase 3: Modify (i.e. reduce) duration of some activities such that there is a proper decreases nonnegative quantity in the .
Verification of the termination condition: One of the following three conditions is met, then computation terminate. Otherwise, Back to Phase 1.
(1) If for all and , where indicates a supply quantity of given resource type at time and , be pre-given allowable upper bound (i.e. the overmuch resources be restricted within the certain limits).
(2) The predetermined number of the Phase iteration is made.
(3) For () and , if there exists a such that of satisfied that and is the minimum.
5. An illustrative example
To illustrate that this paper proposed model and solving method, a simple project with two type resources requirements is planned with the network shown in Fig. 1, the normal and crash duration of all activity in Table 1. For the sake of simplicity, we only discuss that the resource cost and duration of activity is a linear relationship below:
, for ; . (13)
The nonnegative parameters , above generated by random are shown in Table 2. The resource requirements are 10 and 6. The relationship between the resource required per duration and duration for activity are all piecewise linear function, are shown in Table 3. We now can describe our computation process as follows.
Fig. 1 Project network progress direction
1. Initialization. Set all activity duration to normal durations. Initial duration and resources required for activity in Table 4 below.
2. By Phase 1 algorithm, the completion duration of project =20 time units, its scheduling is A-D-B-C//E-F, where the symbol C//E denotes parallelity relations of both activity C and E. Note that the earliest start time of activity B and E are the same.
3. The objective function = 36.63 units passing through simple computation in Phase 2 algorithm.
4. Proceed to Phase 3 algorithm. By computing, we can select that the duration of the activity and corresponding to resources required per duration is shown in Table 5 below. Back to 1. Note that there not exist this in the and .
5. By computing, the completion duration of project =19 time units, its scheduling is the same with result in Step 2 above and, the objective function =38.32.
Such-and-such progressing, a satisfied result, i.e. we can accept, must be obtained.
Remark. In studying of the time-resource tradeoff problem with the resource constraints, we sometimes shall discover that the project duration is not decreased while the duration of activity is reduced. For example, we set the duration of the activity to as follows: A=3, B=3 or 4, C=3, D=6, E=4, F=5. By simple computation, the project duration is 21 or 22 time units, its scheduling is A-D-B-C-E-F or A-D-B-E-C-F. The total resources cost is 44.18 and 40.95 respectively. Obviously, these project durations are all larger than the project duration before computation. This problem indicates that the project duration is not always decreased with the activity reduction (crashing) under the resource constraints.
6. Conclusions
In this paper, we proposed a new mathematical model for time-resource tradeoff problem. This model is different from the other models (e.g. Simin and Horn 1996), it mainly shows the following several aspects: 1) the activity duration is treated as a decision variable; 2) the resource constraints are considered; 3) the two-objective functions with conflict one another, the project duration and the total consumed-resources cost, which is defined as adaptive and adjustable between them in all period. It is no surprise that the time-resource tradeoff problem is a difficult problem to solve. The objective is to determinate duration of each activity so that the project duration and the total consumed-resources cost are as minimized as possible under the some precedence and the resource constraints.