INTRODUCTION
Project Scheduling (PS) is a central field within operations research and management science. A deterministic project consists of activities, subject to precedence relations, that have a predetermined objective. Motivated by realworld situations, a wide variety of objectives for project scheduling have been studied in the literature. One of the most common objectives is related to financial measures of a project. Financial aspects of the problem appear when, generally, a series of cash flows occur over the course of the project. Time value of money is taken into account by discounting the cash flows.
Since the introduction of cash flows in project scheduling by Russell (1986) the maximization of the Net Present Value (NPV) has gained increasing attention throughout the literature. Russell (1970) considers unconstrained project scheduling problem with positive and negative cash flows and presents a nonlinear programming model. Elmaghraby and Herroelen (1990) offer an optimal algorithm that builds tree structures in as AOA network. Etgar et al. (1996) consider a problem with an AOA network, where cash flows are associated with events. Shtub and Etgar (1997) also present a branch and bound approach to it. Etgar and Shtub (1999) again consider special version of this problem, assuming that cash flows are linear functions of the event's realization times. Vanhoucke et al. (2001b) study the unconstrained maxnpv problem with a fixed deadline. Adding resource constraints to the maxnpv problem, results in an NP hard optimization problem. Some recent surveys on ResourceConstrained Project Scheduling Problem (RCPSP) with discounted cash flows (RCPSPDC) are given by Vanhoucke et al. (2001a), Icmeli and Erenguc (1996) and Ulusoy and Ozdamar (1995). Doersch and Patterson (1977) developed an exact zeroone integer programming model for the RCPSPDC. Yang et al. (1992) propose a branch and bound algorithm for this problem. Baroum and Patterson (1999) consider an AON network with nonnegative cash flows associated with the activities and proposed a branch and bound procedure for it. Zhu and Padman (1996) propose a tabu search approach. There are plenty of papers concerning heuristic approaches to the RCPSPDC. The first one was developed by Russell (1970). Some recent surveys on RCPSPDC are given by Padman and SmithDaniels (1993), Padman et al. (1997), SmithDaniels et al. (1996) and Icmeli and Erenguc (1994). Yang et al. (1995) propose nine stochastic scheduling rules. Baroum and Patterson (1996) describe several priority rule heuristics and compare them on the basis of computational experiments. Pinder and Maruchech (1996) develop 10 new scheduling heuristics and compare them with several wellknown rules.
A nonregular performance measure, which is gaining attention in justintime
environments, is the minimization of the weighted earlinesstardiness penalty
costs of the project activities. In this problem setting, activities have an
individual activity due date with associated unit earliness and unit tardiness
penalty costs. This problem involves the scheduling of project activities in
order to minimize the weighted earlinesstardiness costs in the absence of resource
constraints. According to the classification scheme of Herroelen et al.
(1999), problem can be classified as cpmearly/tardy.
This research addresses the Weighted EarlinessTardiness Project Scheduling Problem (WETPSP), for the extended form, which time value of money is taken into account by continuous discounting the cash flows and minimum as well as maximum timelags between different activities may be given. The problem is faced by many firms hiring subcontractors, maintenance crews as well as research team. Costs of earliness include extra storage requirements and idle times and implicitly incur opportunity costs. Tardiness leads to costumer complaints, loss of reputation and profits, monetary penalties or goodwill damages. The literature on solution methods for the WETPSP is scant. The Weighted EarlinessTardiness Project Scheduling Problem (WETPSP) reduces to the problem of finding a minimal cut in a transformed digraph so that the problem can be solved in polynomial time.
Vanhoucke et al. (2000a) and Vanhoucke (2001) have developed an exact recursive search algorithm for the basic form. The algorithm exploits the basic idea that the earlinesstardiness costs of a project can be minimized by first scheduling activities at their due date or at a later time instant if forced so by binding precedence constraints, followed by a recursive search which computes the optimal displacement for those activities for which a shift towards time zero proves to be beneficial. Vanhoucke et al. (2000b) have exploited the logic of the recursive procedure for solving the WETPSP in their branch and bound procedure for maximizing the net present value of a project in which progress payments occur. This is often the case when activities are subcontracted and the subcontractors are paid upon activity completions. Kazaz and Sepil (1996) solve the problem using Benders decomposition, while Sepil and Ortac (1997) developed heuristics for the problem under renewable resource constraints.
PROBLEM DESCRIPTION
The deterministic Weighted EarlinessTardiness Project Scheduling Problem (WETPSP) involves the scheduling of project activities in order to minimize the weighted earlinesstardiness costs of the project in the absence of resource constraints. The project is represented by an AON network where the set of nodes, N, represents activities and the set of arcs, A, represents finishstart precedence constraints with a timelag of zero. The activities are numbered from the dummy start activity 1 to the dummy end activity n and are topologically ordered, i.e., each successor of an activity has a larger activity number than the activity itself. The fixed duration of an activity is denoted by d_{i }(1≤i≤n), while h_{i} denotes its deterministic due date. The completion time of activity i is denoted by the nonnegative integer variable f_{i }(1≤i≤n).
The earliness of activity i can be computed as:
E_{i }= max (0, h_{i} – f_{i}) 
The tardiness of activity i can be computed as:
T_{i} = max (0, f_{i} – h_{i})

Basic form of the WETPSP: In the basic form of the problem we suppose
that all precedence relations are finishstart with a timelag of zero and time
value of money is not taken into account.
If we let e_{i }and t_{i }denote the per unit earliness and
tardiness cost of activity i, respectively, the total earlinesstardiness cost
of activity i equals:
e_{i} E_{i} + t_{i} T_{i}

It is assumed that h_{1} = 0, h_{n} = ∞, e_{1}
= t_{1} = ∞ and e_{n }= t_{n} = 0. Problem cpmearly/tardy
can then be formulated as follows (Vanhoucke et al., 2000a):
The objective in Eq. 1 is to minimize the weighted earlinesstardiness
cost of the project. The constraint set given in Eq. 2 imposes
the finishstart precedence relations among activities. Equation
3 and 4 compute the earliness and tardiness of each activity.
Equation 5 forces the dummy start activity to end at time
zero. Equation 6 ensure that the activity finish times, earliness
and tardiness of activities assume nonnegative integer values.
Extended form of WETPSP: When dealing with the NPV criterion, time value
of money is taken into account by discounting the cash flows.

Fig. 1: 
Earlytardy cost curve showing the effect of discount rate
on NPV 
The value of an amount of money is a function of the time of receipt or disbursement
of cash. A dollar received today is more valuable than a dollar to be received
in some time in the future, since the today's dollar can be invested immediately.
In order to calculate the value of NPV, a discount rate α has to be chosen,
which represents the return following from investing in the project rather than
e.g., in securities. Then the continuous discounted factor e^{–αT}
denoted the present value of a dollar to be paid at the end of period T using
a discount rate α. Figure 1 shows that the NPV of the
early/tardy penalty costs associated with an activity changes with respect to
the activity completion times. Graphical representation of the NPV of the cash
flows of the activity i over time t, shows that the discount rate α is
the main parameter that affects the overall shape of the curves and curve is
a nonlinear function of the activity finish time and the discount rate. It is
clear from the curves, which as α is increasing, NPV of tardy cost of activity
tends to zero in infinity. Thus, for high discount rate α activities tend
to finish in infinity. Although, a daily discount rate α greater than 0.02
corresponds to an annual discount rate of 3070% which is very unrealistic value,
but for preserve of generality, we consider a deadline δ_{n} for
the project.
The objective of the extended form of WETPSP is to find a schedule such that the net present value of the project is minimized. The way of calculating the value of NPV depends on the payment model considered. We suppose that the cost due to earliness or tardiness of each activity, will impose in progress model (e.g., at the end of each month, earliness or tardiness of each activity may impose some cost to the client).
We have the following notations for weighted earlinesstardiness project scheduling
with discounted cash flows (The extended form of WETPSP):
n 
= 
Number of activities 
N 
= 
Set of nodes of acyclic digraph representing the project 
A 
= 
Set of arcs of acyclic digraph representing the project 
d_{i} 
= 
Duration of activity i 
h_{i} 
= 
Due date of activity i 
f_{i} 
= 
Finish time of activity i (integer decision variable) 
EFT_{i} 
= 
Earliest finish time of activity i 
LFT_{i} 
= 
Latest finish time of activity i 
e_{i} 
= 
Per unit earliness cost of activity i 
t_{i} 
= 
Per unit tardiness cost of activity i 
α 
= 
Discount rate 
δ_{n} 
= 
Deadline of the project 
SM 
= 
State matrix representing the precedence relations conflict between activities 
CA 
= 
Set of conflicted activities in schedule 
Z 
= 
Objective function 
Z* 
= 
Optimal objective function 
ab 
= 
Denotes that activity b may start as soon as activity a is completed. 
Using the above notation, the resourceunconstrained project scheduling problem
under the minimum discounted earlytardy penalty cost objective (classified
as problem early/tardy following the Herroelen et al. (1999)) can be
mathematically formulated as follows:
Subject to:
The objective in Eq. 7 minimizes the NPV of the project.
The constraint set in Eq. 8 maintains the finishstart precedence
relations among the activities. In order to restrict the project duration, we
add a negotiated project deadline δ_{n}, given in Eq.
9 and 10 forces the dummy start activity to end at time
zero. Equation 11 ensure that the activity finish times assume
nonnegative integer values.
BRANCH AND BOUND ALGORITHM
In this section, we give a description of the branch and bound procedure.
Initial schedule: The process of constructing the tree starts with generating an initial and probably infeasible scheduling. In our proposed algorithm, initial scheduling procedure sets the finish time of each activity i at max (h_{i}, EFT_{i}) and calculates its cost. Let us P denotes the level of the branch and bound tree. Then in the initial schedule, we set P = 0. Although this schedule has minimum cost, but it may be infeasible. Feasibility of a schedule can be evaluated by State Matrix (SM). Each element of this matrix can be calculated as follows:
In this matrix, for example, if activity i be predecessor of activity j and finish time of activity i is equal to start time of activity j then we will have SM(i, j) = 0. If finish time of activity i is greater than (less than) the start time of activity j then we will have SM(i, j) < 0 (SM(i, j) > 0). If all elements of SM are nonnegative, then current schedule is timefeasible that means all precedence relations are preserved.
Branching strategy: In this subsection, we describe how to create new
nodes of the enumeration tree and how to select a node for further branching.
Branching is based on the evaluation of SM which presents feasibility of current
schedule, in order to obtain a feasible schedule. Nodes which represent timeinfeasible
project networks and which are not fathomed by any of the node pruning rules
described below lead to a new branching. In each level of branch and bound tree,
if there is more than one such node, ties are broken in favor of children who
have created with more right shift. The branching process takes place from the
selected child, who has now become the current schedule and its children are
generated. Among these children, the best one is selected again. This branching
process continues until all nodes are pruned, based on pruning rules.
The only difference between any current schedule and its parent is that it
includes one new decision about two activities that have time conflict (SM(i,
j) < 0). Time conflicts are resolved using the concepts of left shift and
right shift. Assume, for example, that in a certain node, two activities i and
j have time conflict (SM(i, j) < 0) and activity i is predecessor of activity
j. Suppose that the duration of time conflict between these activities is l
time unit. We have at most (l + 1) alternatives to resolve this time conflict.
In the first node, activity j is shifted to right l time unit. In the second
node, activity j is shifted to right (l – 1) time unit and activity i is
shifted to left 1 time unit. In the kth node, activity j is shifted to right
(l – k + 1) time unit and activity i is shifted to left (k – 1) time
unit. Finally, in (l + 1)th node, activity i is shifted to left l time unit.
In shifting process we must aware that, for each activity i, activity's finish
time don’t be later than LFT_{i}, or earlier than EFT_{i}.
In order to avoid of creating new conflicts, in shifting process, it is necessary
to device preventive approaches. Therefore it is assumed that, in right (left)
shifting of each activity i, if we faced with new conflicts, the associated
activities must shifted to right (left) too. For example this can be shown graphically
as given in Fig. 2, which we suppose and
activity b is selected for right shift.
Consequently, the following lemma applies:
Lemma: The above shifting strategy, will lead to the complete enumeration of search tree.
Pruning rules: If it can be established that further branching from a node cannot lead to an optimal solution, then the node can be pruned away. In this subsection, we present two rules for pruning the enumeration tree:
Incumbent rule: The first pruning rule, the incumbent rule, is based
on the incumbent solution which is the best solution up to a certain point in
the solution process. In this case, it prunes away any schedule that could potentially
lead to an equal or worse solution compared to an incumbent solution. In order
to apply this pruning rule, a procedure has been used to create a Lower Bound
(LB) for the problem. The corresponding bounding procedure is based on concept
called conflict set.

Fig. 3: 
Types of conflict set 
To describe the conflict set which calculates the lower bound associated with
the schedule scheme, we introduce some notations.
A subset X of activities compose a conflict set if a) activity i is predecessor
of activity j and these activities have time conflict (SM(i, j) < 0), b)
activity i is predecessor of some activities k_{1}, k_{2}, k_{3},…,
k_{r} and their generalized precedence relations are ignored, or c)
activity j is successor of some activities k_{1}, k_{2}, k_{3},…,
k_{r} and their generalized precedence relations are ignored. These
three types of conflict sets are given in Fig. 3, graphically.
In order to calculate a lower bound for each timeinfeasible schedule, we follow a twostage procedure. In the first stage, for a timeinfeasible schedule, we identify maximum such conflict sets, so that they didn’t have common activity. In the other hand, each activity i, may be member of one conflict set. In this stage, other generalized precedence constraints that didn’t consider in none of conflict sets are relaxed. In the second stage, LB is calculated based of the following propositions:
Proposition 1: Associated with each type I conflict set, that a precedence
relation between activities i and j is ignored, let C(i, j) be the minimum cost
incurred for resolving timeconflict between activities i and j. If we suppose
that the relative time conflict is l(i, j) time unit, then C(i, j) can be computed
as follows:
Let be the minimum cost incurred for resolving τth conflict set in current
schedule. Thus, about type I conflict set, it may be stated as:
Proposition 2: Associated with each type II conflict set, which activity
i is predecessor of some activities k_{1}, k_{2}, k_{3},…,
k_{r} and their precedence relations are ignored, we can compute as
follows:
Proposition 3: Associated with each type III conflict set, which activity
j is successor of some activities k_{1}, k_{2}, k_{3},…,
k_{r} and their precedence relations are ignored, we may derive:
Proposition 4: Associated with each schedule, a Lower Bound (LB) may
be written as follows:
Dominance rule: The second pruning rule, the dominance rule, is based on fact that some nodes may repeat. Each node in the search tree represents the initial scheduling extended with a set of activity shifts to resolve time conflicts. Therefore, it is possible that a certain node represents a project network which has been examined earlier at another node in the search tree. One way of checking whether two nodes represent the same project network is to check the State Matrix (SM). Identical sets of activity shifts lead to identical project networks. This rule applies when a node is compared to a previously examined node in another path of the search tree. This can be enforced by saving the information required during backtracking.
Algorithm: Having discussed all the necessary concepts of the algorithm, we present it with the pseudocode below:
Initialization: Set P = 0, Z* = ∞, optimal schedule = φ;
Step 1: 
Generate the initial schedule, set it as current schedule; 
Step 2: 
Create CA and SM and calculate Z and LB, for current schedule; 
Step 3: 
If CA is empty and if Z < Z*, go to step 11; 
Step 4: 
Find the first negative element in SM, called SM(i,j), representing the
first time conflict, between activities i and j; 
Step 5: 
Expand current schedule (generate all schedules directly reachable
from current schedule, by all possible shifting activities i and j. For
resulting schedules, set P = P+1 and create their CA and SM and calculate
their Z and LB); 
Step 6: 
Find the branching schedule, the schedule in level P, which not fathomed.
(Ties are broken in favor of children who have created with more right shifting.).
Set it as current schedule and go to step 8; 
Step 7: 
If no result found in step 6, set P = P1. If P = 0, go to step 13,
else go to step 6; 
Step 8: 
Incumbent rule; 
Step 9: 
If the result of incumbent rule is negative, try the dominance rule; 
Step 10: 
If the result of any above two rules is positive,fathom current node and
go to step 6, else go to step 3; 
Step 11: 
Set current schedule as optimal schedule and set Z* = Z; 
Step 12: 
If P = 0, go to step 13, else go to step 6; 
Step 13: 
if Z* = ∞, print 'no possible solution', else print optimal schedule; 
Step 14: 
End; 
A NUMERICAL EXAMPLE
In this section, we determine an optimal schedule for a numerical example by
means of the branch and bound procedure presented. Consider an example of the
WETPSP with 14 activities borrowed from Vanhoucke et al. (2000b). Figure
4 shows the precedence relations among the activities and Table
1 shows the duration, due date and the unit penalty cost of the activities.
For ease of representation, we assume the unit earliness costs to equal the
unit tardiness costs. The project deadline δ_{n} amounts to 21
and the monthly discount rate α equals 0.01 (1%).
At the initial level P = 0 of the tree, we determine the initial scheduling
with setting finish times of each activity i at max (hi, EFTi). An extended
Gantt chart associated with the root of the enumeration tree, node 1, is displayed
in Fig. 5. Such a Gantt chart shows this schedule is not feasible
and there are three conflict set. State Matrix (SM) for initial scheduling is
shown in Fig. 6. This matrix has some negative elements which
is another representation of infeasibility. Then, the set of conflicted activities
are CA = {3, 5, 6, 7, 8, 10, 11 and 12}. In the root of the enumeration tree,
the algorithm computes the objective function (Z) and Lower Bound (LB), 0.87
and 15.31, respectively. Table 2 shows the detailed computation
of lower bound in node 1.
First negative element in SM corresponds to activities 3 and 5, which conflict
1 time unit. Consequently, the algorithm continues with step 5. The level of
the branch and bound tree is increased, i.e., P = 1 and two descendant nodes
will be generated. Node 2, which is due to right shift of activity 5 and node
3, which is due to left shift of activity 3.
Table 1: 
Project's data for numerical example 


Fig. 4: 
Precedence relations 

Fig. 5: 
Extended Gantt chart 

Fig. 6: 
SM for initial scheduling 
Table 2: 
Detailed computation of lower bound in node 1 


Fig. 7: 
Branching process in initial schedule 

Fig. 8: 
Branch and bound tree 
We create a new node of the enumeration tree for each alternative of this decision
and select the best alternative (node 2) for further branching. The State Matrix
(SM) and set of Conflicted Activities (CA) is updated for each node and a lower
bound on the NPV is computed. Resulting tree is given in Fig.
7.
We have coded the branch and bound procedure in MATLAB version 6.5 under windows
XP. The complete branch and bound tree for the example is given in Fig.
8.
In node 4 a first feasible schedule is found with a NPV of 23.29, corresponding with feasible finish times (0, 7, 5, 5, 7, 13, 7, 8, 11, 12, 9, 16, 21 and 21). Search in all tree shows that this schedule is optimal, too. This optimal schedule is repeated in node (16). A feasible schedule is found in node 8, with a NPV of 23.78. Other nodes are fathomed because of the two pruning rules that were described previously.
COMPUTATIONAL RESULTS
In order to validate the proposed branch and bound method for the WETPSPDC,
a problem set consisting of 120 problem instances was generated. This problem
set consisting of equally 40 instances with 10, 30 and 50 activities. The problem
set was extended with unit earlinesstardiness penalty costs for each activity
which are randomly generated between 1 and 10. The due dates were generated
in the same way as described by Vanhoucke et al. (2000b). First, a maximum
due date was obtained for each project by multiplying the critical path length
by 1.5. Subsequently, we generate random numbers between 1 and maximum due date.
Table 3: 
The average CPUtime needed to solve the WETPSPDC 

The numbers are sorted and assigned to the activities in increasing order.
Activity durations are randomly selected between 1 and 10. Maximum number of
predecessors and successors supposed 3.
We have coded the branch and bound procedure in MATLAB version 6.5. The problem
set has solved under windows XP on a personal computer with Pentium IV, 1.7
GHz processor. Table 3 represents the average CPUtime in
second for a different number of activities. As can be seen from
Table 3, the result shows that computational requirements are small.
CONCLUSION
This research reports on an exact branch and bound procedure for extended form of problem cpmearly/tardy, i.e., the unconstrained project scheduling problem with continuous discounted negative cash flows. Negative cash flows occur when an activity is completed at prior or later than its due date. The objective is to schedule the activities in order to minimize the NPV subject to the precedence constraints and a fixed deadline on project. Branching is done by right and left shifting process on two activities which have time conflict, so that predecessor activity has smallest number. Two rules are used for node fathoming, incumbent rule and dominance rule. First pruning procedure computes lower bound by making disjunctive subset of activities so called conflict set. Second pruning procedure fathomed previously examined node in another path of the search tree. Finally, the new branch and bound procedure used for solving a numerical example.