# A Float-Path Theory and Its Application to the Time-Cost Tradeoff Problem

Authors: Zhi-xiong Su; Jian-xun Qi; Han-ying Wei
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

Activity floats are vital for project scheduling, such as total floats which determine the maximum permissible delays of activities. Moreover, activity paths in activity networks present essences of many project scheduling problems; for example, the time-cost tradeoff is to shorten long paths at lower costs. We discovered relationships between activity floats and paths and established a float-path theory. The theory helps to compute path lengths using activity floats and analyze activity floats using paths, which helps to transmute a problem into the other simpler one. We discussed applications of the float-path theory and applied it to solve the time-cost tradeoff problem (TCTP), especially the nonlinear and discrete versions. We proposed a simplification from an angle of path as a preprocessing technique for the TCTP. The simplification is a difficult path problem, but we transformed it into a simple float problem using the float-path theory. We designed a polynomial algorithm for the simplification, and then the TCTP may be solved more efficiently.


---

## Body

## 1. Introduction

A project is defined by a set of “real” activities and a set of immediate precedence relations. Based on this, DuPont company and Kelley and Walker [1] created activity networks to represent projects, such as CPM networks. The temporal analysis of the activity network resulted in the definition of several parameters, not the least important among which are the earliest and latest start and finish-time of an activity, which gave rise to the concept of activity floats. There are four such floats—total float, free float, safety float, and interference float [2–5]. These floats play an important role in two issues of central concern to managers: resource allocation and activity scheduling, since floats gave a measure of the flexibility in scheduling the activities during the project execution without delaying the project completion time [5].In this paper, we researched the activity floats from the view of length instead of time and discovered their new properties—there are close relationships between floats and paths in activity networks. For example, the total float of an activity is equal to the difference between length of the critical path and length of the longest path passing the activity. The properties cause the activity floats and paths to be represented by each other, and we summarized them as a float-path theory. Paths are vital research subjects in most types of networks, and the activity network is no exception. Activity paths present essences of many project scheduling problems. For example, the essence of the time-cost tradeoff is to compress long paths to a required length at the lowest cost. The classic Fulkerson [6] algorithm is to compress the critical path and the compression in each step is determined by free floats of noncritical activities. Solving different problems needs considering different types of paths, and it may be difficult to find some types of paths. The float-path theory provides a new approach for path problems, that is, replacing finding paths by computing activity floats, even analyzing paths when changing the network’s structure (such as adding, removing, or flipping arcs).In this paper, we considered the application of the float-path theory to a classic project scheduling problem—time-cost tradeoff problem (TCTP), especially the nonlinear continuous and discrete versions. The continuous TCTP was proposed by Kelley [7] and contains linear and nonlinear TCTP. The nonlinear TCTP is more realistic but difficult than the linear one, and the nonlinear time-cost curve is a main research objective. The more general form of the time-cost curve was analyzed by Panagiotakoplos [8] and Moder et al. [9] following the earlier studies of the concave time-cost curve by Falk and Horowitz [10] and convex time-cost curve studies of others [11–15]. Their main ideas for the nonlinear TCTP were to approximate the nonlinear function by using a piecewise linear function and then solve the problem by computing the linear function. Later some other authors further developed the approaches [4, 16] and proposed new ones, for example, decision support model [17]. In addition to researching the time-cost curve, several heuristic algorithms are used to solve the nonlinear TCTP [18–23]. Discrete TCTP (DTCTP), the most difficult of the TCTPs, was proposed by Panagiotakoplos [8] and Harvey and Patterson [24]. De et al. [25] proved that the problem was strong nondeterministic polynomial-time hard (NP-hard). Many scholars designed heuristic algorithms for the problem. Skutella [26] first designed an approximation algorithm for the DTCTP, and some recent heuristic algorithms for the problem have been reported [27–34]. Akkan et al. [27], in particular, proposed a simplification for the problem, and their main approach was to compute path lengths, especially the shorter paths in the network. But the workload of directly computing all path lengths in a network is incredible, and the effect of this simplification may be not perfect. In addition, several exact methodologies are used to solve the problem with small-scale, including mathematical programming [35], dynamic programming [36, 37], branch and bound procedure [38], and robustness measures [23, 39].We considered the large-scale nonlinear continuous TCTP and DTCTP from the idea of equivalent simplification. Simplification has a much larger benefit for the problems. For the nonlinear TCTP, narrowing the duration interval of an activity allows a more detailed approximation of the piecewise linear function to its nonlinear function. The measure can improve the effect and accuracy of solving the problem. The effectiveness of simplification will be more prominent to the DTCTP. The number of schemes of the DTCTP will increase exponentially as the scale of the problem increases, which causes the increase of the computation greatly. Conversely, in case of reducing activities, the number of schemes will decrease exponentially. Hence the simplification may cause a large-scale DTCTP to be solved using exact algorithms.The float-path theory applies to the simplification. For instance, a target of the simplification is to remove paths shorter than the required length. There are numerous paths but fewer activities in a large-scale network. We can use the float-path theory to replace the computing path lengths by computing activity floats and remove numerous redundant paths by removing several activities. This is similar to the effect of the analytic geometry, which substitutes quadratic functions for complex cone curve. Based on the float-path theory, we designed a polynomial algorithm to simplify the TCTPs. The preprocessing technique may help to solve the TCTP and other project scheduling problems.


## 2. Time Parameter in a CPM Network

### 2.1. Time Parameter of Node

In a CPM network (activity-on-arc representation), let nodes(
1
) and (
n
) be the start and terminal nodes of the network, and let d
i
j denote the duration of the activity (
i
,
j
), and E
T
i and L
T
i are the earliest and latest times of the node (
i
); then let j
=
2,3
,
…
,
n,
(1)
E
T
1
=
0
,
E
T
j
=
max
⁡
i
{
E
T
i
+
d
i
j
}
and let j
=
n
-
1, n
-
2
,
…
,
1,
(2)
L
T
n
=
E
T
n
,
L
T
j
=
min
⁡
k
L
T
k
-
d
j
k
.
Length L
(
μ
∇
) of the critical path, μ
∇, in the network is
(3)
L
μ
∇
=
E
T
n
=
L
T
n
.


### 2.2. Activity Float

The activity floats mainly include total, free, safety, and interference floats and are described below in relation to an activity(
i
,
j
).Total Float. The total float (T
F
i
j) is defined as
(4)
T
F
i
j
=
L
T
j
-
E
T
i
-
d
i
j
.
It denotes the maximum permissible delay of the activity (
i
,
j
) without delaying the project duration.Free Float. The free float (F
F
i
j) is computed as
(5)
F
F
i
j
=
E
T
j
-
E
T
i
-
d
i
j
.
It denotes the maximum permissible delay of the activity (
i
,
j
) when all its succeeding activities start as early as possible and all its preceding activities finish as early as possible.Safety Float. The safety float (S
F
i
j) is defined by
(6)
S
F
i
j
=
L
T
j
-
L
T
i
-
d
i
j
.
It denotes the maximum permissible delay of the activity (
i
,
j
) when all its preceding activities start as late as possible and all its succeeding activities finish as late as possible.Interference Float. The interference float (I
F
i
j) is computed as
(7)
T
F
i
j
=
E
T
j
-
L
T
i
-
d
i
j
.
If the interference float is positive, then it describes the maximum permissible delay when all its succeeding activities start as early as possible and all its preceding activities finish as late as possible. In case it is negative, the IF is the minimum required shortening of the duration of the activity to allow all its succeeding activities to finish as early as possible and all its preceding activities to finish as late as possible.


## 2.1. Time Parameter of Node

In a CPM network (activity-on-arc representation), let nodes(
1
) and (
n
) be the start and terminal nodes of the network, and let d
i
j denote the duration of the activity (
i
,
j
), and E
T
i and L
T
i are the earliest and latest times of the node (
i
); then let j
=
2,3
,
…
,
n,
(1)
E
T
1
=
0
,
E
T
j
=
max
⁡
i
{
E
T
i
+
d
i
j
}
and let j
=
n
-
1, n
-
2
,
…
,
1,
(2)
L
T
n
=
E
T
n
,
L
T
j
=
min
⁡
k
L
T
k
-
d
j
k
.
Length L
(
μ
∇
) of the critical path, μ
∇, in the network is
(3)
L
μ
∇
=
E
T
n
=
L
T
n
.


## 2.2. Activity Float

The activity floats mainly include total, free, safety, and interference floats and are described below in relation to an activity(
i
,
j
).Total Float. The total float (T
F
i
j) is defined as
(4)
T
F
i
j
=
L
T
j
-
E
T
i
-
d
i
j
.
It denotes the maximum permissible delay of the activity (
i
,
j
) without delaying the project duration.Free Float. The free float (F
F
i
j) is computed as
(5)
F
F
i
j
=
E
T
j
-
E
T
i
-
d
i
j
.
It denotes the maximum permissible delay of the activity (
i
,
j
) when all its succeeding activities start as early as possible and all its preceding activities finish as early as possible.Safety Float. The safety float (S
F
i
j) is defined by
(6)
S
F
i
j
=
L
T
j
-
L
T
i
-
d
i
j
.
It denotes the maximum permissible delay of the activity (
i
,
j
) when all its preceding activities start as late as possible and all its succeeding activities finish as late as possible.Interference Float. The interference float (I
F
i
j) is computed as
(7)
T
F
i
j
=
E
T
j
-
L
T
i
-
d
i
j
.
If the interference float is positive, then it describes the maximum permissible delay when all its succeeding activities start as early as possible and all its preceding activities finish as late as possible. In case it is negative, the IF is the minimum required shortening of the duration of the activity to allow all its succeeding activities to finish as early as possible and all its preceding activities to finish as late as possible.


## 3. Float-Path Theory in a CPM Network

Float-path theory reflects the property of the CPM network structure, and it mainly contains the relationships between activity floats and path lengths. We summarize them in the following theorems.Theorem 1.
Supposeμ
i
→
j is a path from the node (
i
) to node (
j
); then its length, L
(
μ
i
→
j
), is
(8)
L
μ
i
→
j
=
E
T
j
-
E
T
i
-
∑
(
e
,
f
)
∈
μ
i
→
j
‍
F
F
e
f
=
L
T
j
-
L
T
i
-
∑
(
e
,
f
)
∈
μ
i
→
j
‍
S
F
e
f
=
L
T
j
-
E
T
i
-
T
F
u
v
-
∑
e
,
f
∈
μ
i
→
u
‍
F
F
e
f
-
∑
(
r
,
s
)
∈
μ
v
→
j
‍
S
F
r
s
=
L
T
j
-
E
T
i
-
T
F
k
-
∑
(
e
,
f
)
∈
μ
i
→
k
‍
F
F
e
f
-
∑
(
r
,
s
)
∈
μ
k
→
j
‍
S
F
r
s
,
where (
u
,
v
)
∈
μ
i
→
j and (
k
)
∈
μ
i
→
j.Proof.
See AppendixA.Theorem 2.
For any node,(
i
), its earliest time, E
T
i, is equal to length of the longest path, μ
1
→
i
∇, from the start node (1) of the network; that is,
(9)
E
T
i
=
L
μ
1
→
i
∇
,
and its latest time, L
T
i, is equal to the difference between length of the critical path, μ
∇, and length of the longest path, μ
i
→
n
∇, from it to the end node (
n
) of the network; that is,
(10)
L
T
i
=
L
μ
∇
-
L
μ
i
→
n
∇
.Proof.
See AppendixB.Corollary 3.
For any node,(
i
), the free float, F
F
e
f, of any activity (
e
,
f
) on the longest path μ
1
→
i
∇ from the start node (1) of the network to it is equal to 0; that is,
(11)
F
F
e
f
=
0
,
e
,
f
∈
μ
1
→
i
∇
,
and the safety float, S
F
r
s, of any activity (
r
,
s
) on the longest path μ
i
→
n
∇ from it to the end node (
n
) of the network is also equal to 0; that is,
(12)
S
F
r
s
=
0
,
r
,
s
∈
μ
i
→
n
∇
.Proof.
See AppendixC.Theorem 4.
For any activity,(
i
,
j
), its total float, T
F
i
j, is equal to the difference between length of the critical path, μ
∇, and length of the longest path, μ
i
j
∇, passing it; that is,
(13)
T
F
i
j
=
L
μ
∇
-
L
μ
i
j
∇
.Proof.
See AppendixD.Theorem 5.
For any activity,(
i
,
j
), its free float, F
F
i
j, is equal to the difference between length of the longest path, μ
j
∇, passing its end node (
j
) and length of the longest path, μ
i
j
∇, passing it; that is,
(14)
F
F
i
j
=
L
μ
j
∇
-
L
μ
i
j
∇
.Proof.
See AppendixE.Theorem 6.
For any activity,(
i
,
j
), its safety float, S
F
i
j, is equal to the difference between length of the longest path, μ
i
∇, passing its start node (
i
) and length of the longest path, μ
i
j
∇, passing it; that is,
(15)
S
F
i
j
=
L
μ
i
∇
-
L
μ
i
j
∇
.Proof.
It is similar to the proof of Theorem5.Theorem 7.
For any activity,(
i
,
j
), its interference float, I
F
i
j, can be represented as follows: add an arc (
j
,
i
) with length d
j
i
=
d
i
j, and I
F
i
j is equal to the value of that length of the longest path, μ
j
i
∇, passing the arc (
j
,
i
) once minus length of the critical path μ
∇ of the old network, and minus double duration d
i
j of the activity (
i
,
j
); that is,
(16)
I
F
i
j
=
L
μ
j
i
∇
-
L
μ
∇
-
2
d
i
j
.
If F
F
i
j
>
0 and S
F
i
j
>
0, the equation is still correct after flipping the arc (
i
,
j
).Proof.
See AppendixF.The float-path theory helps to solve many path problems by transforming the computations of path lengths into the computations of activity floats. For example, according to Theorem2 and Corollary 3, we can find the longest path from the start node (
1
) to any node and the longest path from any node to the end node (
n
); according to Theorem 4 and Corollary 3, we can find the longest path passing any activity; and according to Theorem 7, we can analyze paths when changing the network’s structure (e.g., adding or flipping arcs).


## 4. Application of the Float-Path Theory to TCTP

### 4.1. The TCTP

Assume in a CPM networkG that d
i
j denotes the duration of each activity (
i
,
j
) and l
i
j
≤
d
i
j
≤
u
i
j, where f
i
j
(
d
i
j
) denotes the cost of duration (d
i
j) and is a monotonic decreasing function, and t
i denotes the time of each node (
i
) and T denotes project duration that T
=
t
n
-
t
1. The continuous TCTP can be formulated as follows (λ denotes the required project duration):
(17)
min
⁡
∑
(
i
,
j
)
∈
G
‍
f
i
j
(
d
i
j
)
s
.
t
.
t
j
-
t
i
≥
d
i
j
h
h
h
h
l
i
j
≤
d
i
j
≤
u
i
j
h
h
h
h
t
n
-
t
1
≤
λ
.And assume thatd
i
j
m and c
i
j
m, respectively, denote the duration and cost of mode m of each activity (
i
,
j
), and if d
i
j
m
1
≥
d
i
j
m
2 then c
i
j
m
1
≤
c
i
j
m
2 for all m
∈
M
i
j. The DTCTP can be formulated as follows:
(18)
min
⁡
∑
(
i
,
j
)
∈
G
‍
∑
m
∈
M
i
j
‍
c
i
j
m
x
i
j
m
s
.
t
.
∑
m
∈
M
i
j
‍
x
i
j
m
=
1
,
(
i
,
j
)
∈
G
h
h
h
h
t
j
-
t
i
-
∑
m
∈
M
i
j
‍
d
i
j
m
x
i
j
m
≥
0
h
h
h
h
t
n
-
t
1
≤
λ
h
h
h
h
t
i
≥
0
,
(
i
)
∈
G
h
h
h
h
x
i
j
m
∈
{
0,1
}
,
(
i
,
j
)
∈
G
,
m
∈
M
i
j
.In an activity network, the project duration is equal to the length of the critical path; therefore in solving the TCTP the solution is to make all the paths no longer than the required lengthλ at a minimum total cost.


### 4.2. Principles of Equivalent Simplification of the TCTP

We first consider reducing the scale of the problem and propose Proposition8 of the equivalent simplification in combination with the CPM network.Proposition 8.
If all activities choose their longest durations and a path is no longer thanλ, then in all cases the path will be no longer than λ so that can be eliminated from our consideration in solving the TCTP. Therefore, the path can be removed. However, because removing a path may cause the removal of other paths, keeping paths longer than λ is essential when removing the shorter ones.However, it is difficult to directly implement the proposition, and we simplify it to Proposition9.Proposition 9.
If all activities choose their longest durations and the longest path passing one activity(
i
,
j
) is no longer than λ, then in all cases all paths passing the activity will be no longer than λ. Thus, the activity (
i
,
j
) is a redundant activity and can be removed, and its optimal duration is the cheapest duration.Furthermore, we consider simplifying parameters of each activity and propose Propositions10~12 of the equivalent simplification.Proposition 10.
If activity(
i
,
j
) chooses a duration d
i
j and the longest path passing the activity is longer than λ, even if all the other activities choose their shortest durations, then it will in all cases make the project duration longer than λ, and d
i
j is not the optimal solution. On this basis, d
i
j is a redundant duration of the activity (
i
,
j
) which is called redundant-long duration and can be removed.Proposition 11.
If one activity chooses a duration, the longest path passing the activity will be no longer thanλ, even if all other activities choose their longest durations; therefore, in all cases the duration is unable to make project duration longer than λ, and one names it as short duration.Proposition 12.
For all the short durations of an activity(
i
,
j
), the total cost will be lower when choosing the cheapest duration d
i
j compared to other choices; therefore, the minimum total cost will not be realized when using the short durations other than d
i
j, and the other durations are not optimal solutions. Thence, these short durations are redundant durations of the activity and can be removed. One names them as redundant-short durations.


### 4.3. Equivalent Simplification of TCTP Using the Float-Path Theory

Theorems13~15 describe how to determine the redundant objectives.Theorem 13.
Let each activity(
i
,
j
) choose the longest duration d
i
j
=
u
i
j; then compute its total float T
F
i
j and the project duration T. If T
F
i
j
≥
T
-
λ, then the activity (
i
,
j
) is a redundant activity.Proof.
See AppendixG.Theorem 14.
Let each activity(
i
,
j
) choose its shortest duration d
i
j
=
l
i
j; then add an assistant activity (
1
,
n
) with duration d
1
n
=
λ, and compute the total float T
F
i
j. If L
T
j
-
E
T
i
<
u
i
j, then each duration d
i
j meeting d
i
j
>
L
T
j
-
E
T
i is a redundant-long duration of the activity (
i
,
j
).Proof.
See AppendixH.Theorem 15.
Let each activity(
i
,
j
) choose its longest duration d
i
j
=
u
i
j, and compute its total float T
F
i
j and project duration T. If T
F
i
j
<
T
-
λ and l
i
j
≤
L
T
j
-
E
T
i
-
T
+
λ, then each duration d
i
j meeting d
i
j
≤
L
T
j
-
E
T
i
-
T
+
λ is a short duration of the activity (
i
,
j
). Except for the cheapest short duration for an activity, the others are redundant-short durations.Proof.
See AppendixI.


### 4.4. Algorithm of Equivalent Simplification of the TCTP

Suppose there aren nodes in a corresponding CPM network for a given project, indicated by G, with the start and terminal nodes marked as (
1
) and (
n
); then we can simplify the TCTP of the project as follows.Step 1.
Add assistant activity(
1
,
n
) with duration d
1
n
=
u
1
n
=
l
1
n
=
λ.Step 2.
Letd
i
j
=
l
i
j of each activity (
i
,
j
), and compute time parameters.Step 3.
Remove duration of activity(
i
,
j
) that is longer than L
T
j
-
E
T
i.Step 4.
Letd
i
j
=
min
⁡
{
L
T
j
-
E
T
i
,
u
i
j
} of each activity (
i
,
j
), and compute time parameters.Step 5.
Remove activity(
i
,
j
) whose T
F
i
j
≥
E
T
n
-
λ.Step 6.
For duration of each remaining activity(
i
,
j
) which is no longer than L
T
j
-
E
T
i
-
E
T
n
+
λ, preserve the longest one and remove the others.Proof.
See AppendixJ.The complexity of the algorithm isO
(
m
), where m indicates quantity of activities (see Appendix K). The effectiveness of the algorithm depends on the comparisons among the length of the critical path, the length of the longest path passing each activity, and the required length λ. For example, when most paths are much shorter than the critical path (e.g., most activities have large total floats), or the difference between λ and the length of the critical path is small, the simplification may be more effective because it may remove more activities.After the equivalent simplification of the networkG, the remaining network is marked as G
*. The optimal solution of the TCTP can be solved using the network G
*: (
1
) the optimal duration of each activity in the network G
* can be obtained by using existing algorithms, such as the algorithms in References; (
2
) for each redundant activity (
i
,
j
) in Steps 5 and 6 of the simplification, its duration is unrelated to λ so that the optimal duration is the current longest (cheapest) one b
i
j
* for the minimum total cost.


## 4.1. The TCTP

Assume in a CPM networkG that d
i
j denotes the duration of each activity (
i
,
j
) and l
i
j
≤
d
i
j
≤
u
i
j, where f
i
j
(
d
i
j
) denotes the cost of duration (d
i
j) and is a monotonic decreasing function, and t
i denotes the time of each node (
i
) and T denotes project duration that T
=
t
n
-
t
1. The continuous TCTP can be formulated as follows (λ denotes the required project duration):
(17)
min
⁡
∑
(
i
,
j
)
∈
G
‍
f
i
j
(
d
i
j
)
s
.
t
.
t
j
-
t
i
≥
d
i
j
h
h
h
h
l
i
j
≤
d
i
j
≤
u
i
j
h
h
h
h
t
n
-
t
1
≤
λ
.And assume thatd
i
j
m and c
i
j
m, respectively, denote the duration and cost of mode m of each activity (
i
,
j
), and if d
i
j
m
1
≥
d
i
j
m
2 then c
i
j
m
1
≤
c
i
j
m
2 for all m
∈
M
i
j. The DTCTP can be formulated as follows:
(18)
min
⁡
∑
(
i
,
j
)
∈
G
‍
∑
m
∈
M
i
j
‍
c
i
j
m
x
i
j
m
s
.
t
.
∑
m
∈
M
i
j
‍
x
i
j
m
=
1
,
(
i
,
j
)
∈
G
h
h
h
h
t
j
-
t
i
-
∑
m
∈
M
i
j
‍
d
i
j
m
x
i
j
m
≥
0
h
h
h
h
t
n
-
t
1
≤
λ
h
h
h
h
t
i
≥
0
,
(
i
)
∈
G
h
h
h
h
x
i
j
m
∈
{
0,1
}
,
(
i
,
j
)
∈
G
,
m
∈
M
i
j
.In an activity network, the project duration is equal to the length of the critical path; therefore in solving the TCTP the solution is to make all the paths no longer than the required lengthλ at a minimum total cost.


## 4.2. Principles of Equivalent Simplification of the TCTP

We first consider reducing the scale of the problem and propose Proposition8 of the equivalent simplification in combination with the CPM network.Proposition 8.
If all activities choose their longest durations and a path is no longer thanλ, then in all cases the path will be no longer than λ so that can be eliminated from our consideration in solving the TCTP. Therefore, the path can be removed. However, because removing a path may cause the removal of other paths, keeping paths longer than λ is essential when removing the shorter ones.However, it is difficult to directly implement the proposition, and we simplify it to Proposition9.Proposition 9.
If all activities choose their longest durations and the longest path passing one activity(
i
,
j
) is no longer than λ, then in all cases all paths passing the activity will be no longer than λ. Thus, the activity (
i
,
j
) is a redundant activity and can be removed, and its optimal duration is the cheapest duration.Furthermore, we consider simplifying parameters of each activity and propose Propositions10~12 of the equivalent simplification.Proposition 10.
If activity(
i
,
j
) chooses a duration d
i
j and the longest path passing the activity is longer than λ, even if all the other activities choose their shortest durations, then it will in all cases make the project duration longer than λ, and d
i
j is not the optimal solution. On this basis, d
i
j is a redundant duration of the activity (
i
,
j
) which is called redundant-long duration and can be removed.Proposition 11.
If one activity chooses a duration, the longest path passing the activity will be no longer thanλ, even if all other activities choose their longest durations; therefore, in all cases the duration is unable to make project duration longer than λ, and one names it as short duration.Proposition 12.
For all the short durations of an activity(
i
,
j
), the total cost will be lower when choosing the cheapest duration d
i
j compared to other choices; therefore, the minimum total cost will not be realized when using the short durations other than d
i
j, and the other durations are not optimal solutions. Thence, these short durations are redundant durations of the activity and can be removed. One names them as redundant-short durations.


## 4.3. Equivalent Simplification of TCTP Using the Float-Path Theory

Theorems13~15 describe how to determine the redundant objectives.Theorem 13.
Let each activity(
i
,
j
) choose the longest duration d
i
j
=
u
i
j; then compute its total float T
F
i
j and the project duration T. If T
F
i
j
≥
T
-
λ, then the activity (
i
,
j
) is a redundant activity.Proof.
See AppendixG.Theorem 14.
Let each activity(
i
,
j
) choose its shortest duration d
i
j
=
l
i
j; then add an assistant activity (
1
,
n
) with duration d
1
n
=
λ, and compute the total float T
F
i
j. If L
T
j
-
E
T
i
<
u
i
j, then each duration d
i
j meeting d
i
j
>
L
T
j
-
E
T
i is a redundant-long duration of the activity (
i
,
j
).Proof.
See AppendixH.Theorem 15.
Let each activity(
i
,
j
) choose its longest duration d
i
j
=
u
i
j, and compute its total float T
F
i
j and project duration T. If T
F
i
j
<
T
-
λ and l
i
j
≤
L
T
j
-
E
T
i
-
T
+
λ, then each duration d
i
j meeting d
i
j
≤
L
T
j
-
E
T
i
-
T
+
λ is a short duration of the activity (
i
,
j
). Except for the cheapest short duration for an activity, the others are redundant-short durations.Proof.
See AppendixI.


## 4.4. Algorithm of Equivalent Simplification of the TCTP

Suppose there aren nodes in a corresponding CPM network for a given project, indicated by G, with the start and terminal nodes marked as (
1
) and (
n
); then we can simplify the TCTP of the project as follows.Step 1.
Add assistant activity(
1
,
n
) with duration d
1
n
=
u
1
n
=
l
1
n
=
λ.Step 2.
Letd
i
j
=
l
i
j of each activity (
i
,
j
), and compute time parameters.Step 3.
Remove duration of activity(
i
,
j
) that is longer than L
T
j
-
E
T
i.Step 4.
Letd
i
j
=
min
⁡
{
L
T
j
-
E
T
i
,
u
i
j
} of each activity (
i
,
j
), and compute time parameters.Step 5.
Remove activity(
i
,
j
) whose T
F
i
j
≥
E
T
n
-
λ.Step 6.
For duration of each remaining activity(
i
,
j
) which is no longer than L
T
j
-
E
T
i
-
E
T
n
+
λ, preserve the longest one and remove the others.Proof.
See AppendixJ.The complexity of the algorithm isO
(
m
), where m indicates quantity of activities (see Appendix K). The effectiveness of the algorithm depends on the comparisons among the length of the critical path, the length of the longest path passing each activity, and the required length λ. For example, when most paths are much shorter than the critical path (e.g., most activities have large total floats), or the difference between λ and the length of the critical path is small, the simplification may be more effective because it may remove more activities.After the equivalent simplification of the networkG, the remaining network is marked as G
*. The optimal solution of the TCTP can be solved using the network G
*: (
1
) the optimal duration of each activity in the network G
* can be obtained by using existing algorithms, such as the algorithms in References; (
2
) for each redundant activity (
i
,
j
) in Steps 5 and 6 of the simplification, its duration is unrelated to λ so that the optimal duration is the current longest (cheapest) one b
i
j
* for the minimum total cost.


## 5. Illustration

### 5.1. Equivalent Simplification of the Nonlinear Continuous TCTP

The detailed information for a project with 116 activities is shown in Table1 (the cost unit is dollar and time unit is day). The start-time of any activity is no earlier than the finish-time of its immediate predecessor activity, and the cost function of each activity’s duration is nonlinear and monotonically decreasing. How do we simplify the problem and improve the effect and accuracy of the solution if the demand is to shorten the project duration to 520 (λ
=
520) at a minimum cost?Table 1
The information of each activity.
Activity code
Duration interval
Immediate successor
Cost functionf
(
x
)
a
1
[60, 70]
b
1, b
2
-
x
3
+
60
x
2
+
5000
x
a
2
[55, 60]
b
3, b
4, b
5
x
2
-
140
x
+
5000
a
3
[45, 50]
b
6, b
7, b
8
-
x
3
+
45
x
2
+
8000
a
4
[50, 55]
b
9, b
10, b
11
-
x
2
+
60
x
a
5
[70, 100]
b
12, b
13, b
14
-
x
3
+
70
x
2
+
4400
x
a
6
[80, 120]
b
15, b
16
x
2
-
260
x
+
16900
b
1
[70, 75]
e
1, e
2
x
2
-
180
x
+
8100
b
2
[30, 35]
c
1, c
2
-
x
3
+
30
x
2
+
400
x
b
3
[40, 45]
c
1, c
2
x
2
-
120
x
+
3600
b
4
[70, 75]
e
3, e
4, e
5
-
x
2
+
90
x
b
5
[25, 30]
c
3, c
4
-
x
3
+
25
x
2
+
4500
x
b
6
[30, 33]
c
3, c
4
-
x
3
+
30
x
2
+
400
x
b
7
[65, 70]
e
6, e
7, e
8
x
2
-
160
x
+
6400
b
8
[30, 33]
c
5, c
6
-
x
3
+
25
x
2
+
12250
b
9
[25, 28]
c
5, c
6
-
x
3
+
25
x
2
+
4500
b
10
[55, 60]
e
9, e
10, e
11
x
2
-
160
x
+
6400
b
11
[30, 33]
c
7, c
8
-
x
3
+
30
x
2
+
50000
b
12
[20, 23]
c
7, c
8
-
x
3
+
20
x
2
+
9000
b
13
[80, 95]
e
12, e
13, e
14
x
2
-
200
x
+
10000
b
14
[40, 80]
c
9, c
10
-
x
3
+
40
x
2
+
4500
x
b
15
[30, 60]
c
9, c
10
-
x
3
+
25
x
2
+
2450
x
b
16
[80, 115]
e
15, e
16
-
x
2
+
140
x
-
100
c
1
[35, 40]
e
1, e
2
-
x
3
+
35
x
2
+
750
x
c
2
[25, 30]
e
3, e
4, e
5
-
x
3
+
20
x
2
+
1500
x
c
3
[30, 35]
e
3, e
4, e
5
-
x
3
+
30
x
2
+
16000
c
4
[25, 27]
e
6, e
7, e
8
-
x
3
+
20
x
2
+
9000
c
5
[35, 37]
e
6, e
7, e
8
-
x
3
+
35
x
2
+
200
x
c
6
[30, 32]
e
9, e
10, e
11
-
x
3
+
30
x
2
+
400
x
c
7
[20, 22]
e
9, e
10, e
11
-
x
3
+
15
x
2
+
450
x
c
8
[30, 32]
e
12, e
13, e
14
x
2
-
100
x
+
2500
c
9
[40, 42]
e
12, e
13, e
14
2
x
2
-
480
x
+
7200
c
10
[45, 85]
e
15, e
16
-
x
2
+
100
x
+
1100
e
1
[65, 70]
g
1, g
2
2
x
2
-
320
x
+
12800
e
2
[30, 35]
f
1, f
2
-
x
3
+
30
x
2
+
400
x
e
3
[35, 37]
f
1, f
2
-
3
x
3
+
90
x
2
+
3000
x
e
4
[60, 65]
g
3, g
4, g
5
x
2
-
140
x
+
4900
e
5
[30, 32]
f
3, f
4
x
4
-
80
x
3
+
1600
x
2
e
6
[25, 27]
f
3, f
4
x
4
-
60
x
3
+
900
x
2
e
7
[55, 60]
g
6, g
7, g
8
-
x
3
+
55
x
2
+
1050
x
e
8
[20, 22]
f
5, f
6
-
x
3
+
600
x
+
150
e
9
[25, 27]
f
5, f
6
2
x
4
-
120
x
3
+
900
x
2
e
10
[50, 55]
g
9, g
10, g
11
-
x
3
+
50
x
2
+
600
x
e
11
[20, 22]
f
7, f
8
x
4
-
60
x
3
+
900
x
2
e
12
[25, 27]
f
7, f
8
-
x
3
+
25
x
2
+
600
x
e
13
[20, 25]
g
12, g
13, g
14
x
4
-
56
x
3
+
784
x
2
e
14
[45, 90]
f
9, f
10
2
x
2
-
400
x
+
20000
e
15
[40, 75]
f
9, f
10
3
x
2
-
480
x
+
19200
e
16
[85, 130]
g
15, g
16
2
x
2
-
600
x
+
45000
f
1
[30, 35]
g
1, g
2
-
x
3
+
30
x
2
+
675
x
f
2
[25, 28]
g
3, g
4, g
5
2
x
4
-
120
x
3
+
1800
x
2
f
3
[30, 33]
g
3, g
4, g
5
-
2
x
3
+
60
x
2
+
700
x
f
4
[30, 33]
g
6, g
7, g
8
x
4
-
80
x
3
+
1600
x
2
f
5
[35, 38]
g
6, g
7, g
8
-
3
x
3
+
105
x
2
+
600
x
f
6
[25, 28]
g
9, g
10, g
11
x
4
-
60
x
3
+
900
x
2
f
7
[25, 28]
g
9, g
10, g
11
2
x
4
-
160
x
3
+
4000
x
2
f
8
[30, 33]
g
12, g
13, g
14
2
x
4
-
200
x
3
+
5000
x
2
f
9
[35, 35]
g
12, g
13, g
14
300000
f
10
[40, 75]
g
15, g
16
3
x
2
-
540
x
+
24300
g
1
[70, 75]
p
1, p
2
2
x
2
-
340
x
+
14450
g
2
[35, 40]
h
1, h
2
-
3
x
3
+
105
x
2
+
2250
x
g
3
[30, 43]
h
1, h
2
x
2
-
100
x
+
2500
g
4
[65, 70]
p
3, p
4, p
5
-
x
3
+
65
x
2
+
1200
x
g
5
[25, 28]
h
3, h
4
3
x
4
-
180
x
3
+
2700
x
2
g
6
[25, 28]
h
3, h
4
2
x
4
-
160
x
3
+
3200
x
2
g
7
[60, 65]
p
6, p
7, p
8
x
2
-
140
x
+
4900
g
8
[30, 33]
h
5, h
6
3
x
4
-
210
x
3
+
3675
x
2
g
9
[25, 28]
h
5, h
6
2
x
4
-
200
x
3
+
5000
x
2
g
10
[60, 65]
p
9, p
10, p
11
3
x
2
-
280
x
+
9800
g
11
[15, 18]
h
7, h
8
-
x
5
+
15
x
4
+
2000
x
2
g
12
[30, 30]
h
7, h
8
60000
g
13
[20, 25]
p
12, p
13, p
14
5
x
4
-
3000
x
3
+
4500
x
2
g
14
[30, 35]
h
9, h
10
-
2
x
3
+
60
x
2
+
800
x
g
15
[35, 65]
h
9, h
10
x
2
-
140
x
+
4900
g
16
[80, 125]
p
15, p
16
x
2
-
280
x
+
19600
h
1
[30, 35]
p
1, p
2
-
x
3
+
30
x
2
+
16000
h
2
[25, 27]
p
3, p
4, p
5
4
x
4
-
280
x
3
+
4900
x
2
h
3
[30, 32]
p
3, p
4, p
5
-
2
x
3
+
60
x
2
+
12250
h
4
[30, 32]
p
6, p
7, p
8
-
3
x
3
+
90
x
2
+
525
x
h
5
[25, 27]
p
6, p
7, p
8
3
x
4
-
180
x
3
+
2700
h
6
[35, 37]
p
9, p
10, p
11
-
2
x
3
+
70
x
2
+
16000
h
7
[25, 27]
p
9, p
10, p
11
x
4
-
80
x
3
+
64000
x
h
8
[25, 25]
p
12, p
13, p
14
80000
h
9
[40, 60]
p
12, p
13, p
14
x
2
-
130
x
+
4225
h
10
[40, 80]
p
15, p
16
x
2
-
170
x
+
7225
p
1
[60, 65]
v
1
3
x
2
-
450
x
+
16875
p
2
[30, 35]
r
1, r
2
-
x
3
+
30
x
2
+
16000
p
3
[35, 37]
r
1, r
2
-
2
x
3
+
70
x
2
+
800
x
p
4
[65, 70]
v
2
2
x
2
-
360
x
+
16200
p
5
[30, 32]
r
3, r
4
3
x
4
-
240
x
3
+
4800
x
2
p
6
[25, 27]
r
3, r
4
-
x
5
+
25
x
4
+
300
x
3
p
7
[50, 55]
v
3
-
2
x
3
+
100
x
2
+
72000
p
8
[15, 17]
r
5, r
6
-
x
5
+
225
x
3
+
2000
x
2
p
9
[20, 22]
r
5, r
6
2
x
4
-
100
x
3
+
1250
x
2
p
10
[55, 60]
v
4
-
x
3
+
55
x
2
+
42250
p
11
[15, 17]
r
7, r
8
-
2
x
5
+
450
x
3
+
4000
x
2
p
12
[20, 22]
r
7, r
8
3
x
4
-
150
x
3
+
2250
x
2
p
13
[8, 10]
v
5
3
x
6
-
90
x
5
+
675
x
4
p
14
[30, 35]
r
9, r
10
-
2
x
3
+
60
x
2
+
800
x
p
15
[35, 65]
r
9, r
10
x
2
-
160
x
+
6400
p
16
[95, 140]
v
6
x
2
-
300
x
+
22500
r
1
[25, 30]
v
1
-
x
3
+
25
x
2
+
24000
r
2
[35, 38]
v
2
-
2
x
3
+
70
x
2
+
900
x
r
3
[30, 33]
v
2
-
4
x
3
+
120
x
2
+
1600
x
r
4
[25, 28]
v
3
-
2
x
3
+
50
x
2
+
50000
r
5
[30, 33]
v
3
-
6
x
3
+
180
x
2
+
2400
x
r
6
[25, 28]
v
4
-
3
x
3
+
75
x
2
+
75000
r
7
[30, 33]
v
4
-
4
x
3
+
120
x
2
+
1600
x
r
8
[25, 28]
v
5
-
4
x
3
+
100
x
2
+
2200
x
r
9
[40, 45]
v
5
2
x
4
-
240
x
3
+
432000
x
r
10
[55, 90]
v
6
x
2
-
200
x
+
10000
v
1
[75, 80]
—
2
x
2
-
360
x
+
19200
v
2
[50, 55]
—
-
3
x
3
+
150
x
2
+
108000
v
3
[55, 60]
—
2
x
2
-
400
x
+
20000
v
4
[40, 45]
—
0.5
x
4
-
60
x
3
+
108000
v
5
[85, 90]
—
2
x
2
-
440
x
+
24200
v
6
[90, 150]
—
x
2
-
400
x
+
40000We use our algorithm to simplify the nonlinear time-cost tradeoff problem as follows.Step 1.
Represent the project as a CPM network based on Table1 (let d
i
j
=
l
i
j), and assist activity (
1,52
) with duration d
1,52
=
520.Step 2.
Letd
i
j
=
l
i
j of each activity (
i
,
j
), and compute time parameters, as in Figure 1.Figure 1
Time parameters for all activities with their shortest durations.Step 3.
For activitya
5, remove duration longer than L
T
6
-
E
T
1
=
85; that is, remove duration interval [
85,100
], and let u
a
5
:
=
85; similarly, remove duration interval [
90,120
] of activity a
6, duration interval [
55,80
] of activity b
14, duration interval [
45,60
] of activity b
15, duration interval [
90,115
] of activity b
16, duration interval [
60,85
] of activity c
10, duration interval [
65,90
] of activity e
14, duration interval [
55,75
] of activity e
15, duration interval [
95,130
] of activity e
16, duration interval [
55,75
] of activity f
10, duration interval [
50,65
] of activity g
15, duration interval [
90,125
] of activity g
16, duration interval [
55,80
] of activity h
10, duration interval [
50,65
] of activity p
15, duration interval [
105,140
] of activity p
16, duration interval [
70,90
] of activity r
10, and duration interval [
100,150
] of activity v
6.Step 4.
Letd
i
j
=
u
i
j, and compute time parameters, as in Figure 2.Figure 2
Time parameters for all activities with their remaining longest durations.Step 5.
Remove activities whoseT
F
i
j
≥
E
T
52
-
λ
=
635
-
520
=
115, as in Figure 3.Figure 3
Network with nonredundant activities.Step 6.
There are no durations shorter thanL
T
j
-
E
T
i
-
E
T
52
+
λ of each remaining activity (
i
,
j
) in Figure 3; therefore we could not remove them.After the equivalent simplification, a networkG
* is acquired (Figure 4). Obviously, network G
* is much simpler than the old network (Figure 1), and duration intervals of many remaining activities are significantly narrowed.Figure 4
NetworkG
*.Next we further solved the nonlinear TCTP that computed the optimal durations of activities using the mathematical model in Section4.1 and intelligent algorithm software, such as LINDO. The experiment was performed on a PC (1 CPU, Intel 2.0 GHz, 1 G RAM) using the Windows XP operating system.(i)
We first solved the problem without simplification and obtained the project cost of 749,351,200. The computation time was ~30 min.
(ii)
And then we solved the problem after the simplification and obtained the project cost of 749,106,282, which is 2,449,108 cheaper than the former. The computation time was ~2 sec, which is also much faster than the former.This experiment further tests and verifies that the equivalent simplification could improve the effect and accuracy of the solution of the nonlinear continuous TCTP.


### 5.2. Equivalent Simplification of the DTCTP

The detailed information for a project with 88 activities is shown in Table2 (similarly, the cost unit is dollar and time unit is day). The start-time of any activity is no earlier than the finish-time of its immediate predecessor activity, and each activity has three time-cost modes. If the project must be finished within 385 (λ
=
520) at a minimum cost, then the amount of schemes is 3
88
≈
1
0
42. What is the equivalent simplification to improve scheduling effect?Table 2
Modes of each activity.
Activity code
Immediate successor
m
1
m
2
m
3
d
c
d
c
d
c
a
1
b
1, b
2
30
58
33
53
35
50
a
2
b
3, b
4, b
5
25
46
27
42
30
40
a
3
b
6, b
7, b
8
45
78
49
75
50
70
a
4
b
9, b
10, b
11
38
66
39
63
40
60
a
5
b
12, b
13
24
50
28
47
30
45
b
1
c
1, c
2
41
62
42
55
45
50
b
2
c
3, c
4, c
5
15
78
18
70
20
65
b
3
c
1, c
2
19
32
23
24
25
20
b
4
c
3, c
4, c
5
12
35
14
32
15
30
b
5
c
6, c
7, c
8
23
102
27
95
30
90
b
6
c
3, c
4, c
5
6
50
8
45
10
40
b
7
c
6, c
7, c
8
16
270
18
200
20
150
b
8
c
9, c
10, c
11
42
115
43
100
45
75
b
9
c
6, c
7, c
8
58
65
59
58
60
55
b
10
c
9, c
10, c
11
11
40
14
37
15
35
b
11
c
12, c
13
16
82
19
77
20
75
b
12
c
9, c
10, c
11
26
72
27
68
30
65
b
13
c
12, c
13
35
100
38
90
40
85
c
1
d
1, d
2
28
85
30
76
32
70
c
2
d
3, d
4, d
5
32
55
34
45
35
40
c
3
d
1, d
2
36
155
38
135
40
120
c
4
d
3, d
4, d
5
15
60
18
55
20
50
c
5
d
6, d
7, d
8
27
14
28
11
30
10
c
6
d
3, d
4, d
5
19
15
21
12
22
10
c
7
d
6, d
7, d
8
58
80
59
75
60
60
c
8
d
9, d
10, d
11
11
68
13
60
15
55
c
9
d
6, d
7, d
8
20
145
23
120
25
100
c
10
d
9, d
10, d
11
45
70
47
55
50
50
c
11
d
12, d
13
37
105
38
90
40
80
c
12
d
9, d
10, d
11
31
45
33
38
35
30
c
13
d
12, d
13
30
27
32
22
35
20
d
1
e
1, e
2
41
68
43
65
45
60
d
2
e
3, e
4, e
5
37
100
40
66
42
60
d
3
e
1, e
2
26
52
29
48
30
45
d
4
e
3, e
4, e
5
31
25
32
22
35
20
d
5
e
6, e
7, e
8
22
60
24
50
25
45
d
6
e
3, e
4, e
5
45
75
48
60
50
50
d
7
e
6, e
7, e
8
17
105
18
90
20
80
d
8
e
9, e
10, e
11
33
95
34
80
35
65
d
9
e
6, e
7, e
8
21
50
23
44
25
40
d
10
e
9, e
10, e
11
15
23
17
21
20
20
d
11
e
12, e
13
32
240
34
210
35
200
d
12
e
9, e
10, e
11
25
65
26
55
30
50
d
13
e
12, e
13
75
105
79
90
80
85
e
1
f
1, f
2
25
33
28
31
30
30
e
2
f
3, f
4, f
5
36
130
39
110
40
100
e
3
f
1, f
2
28
58
30
53
32
50
e
4
f
3, f
4, f
5
20
105
23
96
25
90
e
5
f
6, f
7, f
8
40
80
42
66
45
60
e
6
f
3, f
4, f
5
26
85
29
70
30
65
e
7
f
6, f
7, f
8
25
125
28
110
30
90
e
8
f
9, f
10, f
11
30
320
33
290
35
240
e
9
f
6, f
7, f
8
34
90
37
80
40
70
e
10
f
9, f
10, f
11
17
80
19
72
20
65
e
11
f
12, f
13
48
40
49
36
50
30
e
12
f
9, f
10, f
11
31
42
32
38
35
35
e
13
f
12, f
13
41
115
42
100
45
90
f
1
g
1, g
2
16
60
17
48
20
40
f
2
g
3, g
4, g
5
10
85
13
72
15
65
f
3
g
1, g
2
24
78
26
70
30
60
f
4
g
3, g
4, g
5
39
120
43
115
45
100
f
5
g
6, g
7, g
8
18
52
20
48
22
45
f
6
g
3, g
4, g
5
45
85
47
70
50
65
f
7
g
6, g
7, g
8
36
125
38
110
40
90
f
8
g
9, g
10, g
11
25
320
27
290
30
240
f
9
g
6, g
7, g
8
22
90
24
80
25
70
f
10
g
9, g
10, g
11
17
80
20
72
22
65
f
11
g
12, g
13
34
40
36
36
40
30
f
12
g
9, g
10, g
11
41
42
43
38
45
35
f
13
g
12, g
13
65
115
69
100
70
90
g
1
h
1
44
60
47
48
50
40
g
2
h
2
31
85
32
72
35
65
g
3
h
1
35
78
37
70
40
60
g
4
h
2
31
120
33
115
36
100
g
5
h
3
37
52
39
48
42
45
g
6
h
2
17
75
19
65
20
60
g
7
h
3
21
20
23
17
25
15
g
8
h
4
26
58
27
55
30
50
g
9
h
3
40
36
42
33
45
30
g
10
h
4
26
50
28
44
30
40
g
11
h
5
21
13
24
11
25
10
g
12
h
4
34
80
37
75
42
70
g
13
h
5
42
42
43
36
45
30
h
1
—
28
23
29
21
30
20
h
2
—
31
62
33
55
35
50
h
3
—
29
17
30
16
32
15
h
4
—
40
54
41
52
42
50
h
5
—
35
80
39
75
40
65Step 1.
Represent the project as an activity network based on Table2 (let each activity choose mode 1), and assist activity (
1,37
) with duration d
1,37
=
385.Step 2.
Letd
i
j
=
l
i
j of each activity (
i
,
j
), and compute time parameters, as in Figure 5.Figure 5
Time parameters for all activities with their shortest durations.Step 3.
For activitya
3, remove modes 2 and 3 whose durations are longer than L
T
4
-
E
T
1
=
48; similarly, remove modes 2 and 3 of activity d
13, mode 3 of activity e
13, modes 2 and 3 of activity f
13, mode 3 of activity g
12, and modes 2 and 3 of activity h
5.Step 4.
Let each activity in Figure5 choose the mode with the longest duration from its remaining modes, and compute time parameters, as in Figure 6.Figure 6
Time parameters for all activities with their remaining longest durations.Step 5.
Remove activities whoseT
F
i
j
≥
E
T
37
-
λ
=
392
-
385
=
7, as in Figure 7.Figure 7
Network with nonredundant activities.Step 6.
There are no durations shorter thanL
T
j
-
E
T
i
-
E
T
37
+
λ within the remaining modes of each activity in Figure 7; therefore we could not remove them.NetworkG
* is obtained by the above simplification and shown in Figure 8, and brackets around each activity denote its choice of time-cost modes. It is much simpler than Figure 5, and the amount of schemes is only 3
9
×
2
2
=
78732. The optimal scheme is easily determined using any computer and algorithm.Figure 8
NetworkG
*.


## 5.1. Equivalent Simplification of the Nonlinear Continuous TCTP

The detailed information for a project with 116 activities is shown in Table1 (the cost unit is dollar and time unit is day). The start-time of any activity is no earlier than the finish-time of its immediate predecessor activity, and the cost function of each activity’s duration is nonlinear and monotonically decreasing. How do we simplify the problem and improve the effect and accuracy of the solution if the demand is to shorten the project duration to 520 (λ
=
520) at a minimum cost?Table 1
The information of each activity.
Activity code
Duration interval
Immediate successor
Cost functionf
(
x
)
a
1
[60, 70]
b
1, b
2
-
x
3
+
60
x
2
+
5000
x
a
2
[55, 60]
b
3, b
4, b
5
x
2
-
140
x
+
5000
a
3
[45, 50]
b
6, b
7, b
8
-
x
3
+
45
x
2
+
8000
a
4
[50, 55]
b
9, b
10, b
11
-
x
2
+
60
x
a
5
[70, 100]
b
12, b
13, b
14
-
x
3
+
70
x
2
+
4400
x
a
6
[80, 120]
b
15, b
16
x
2
-
260
x
+
16900
b
1
[70, 75]
e
1, e
2
x
2
-
180
x
+
8100
b
2
[30, 35]
c
1, c
2
-
x
3
+
30
x
2
+
400
x
b
3
[40, 45]
c
1, c
2
x
2
-
120
x
+
3600
b
4
[70, 75]
e
3, e
4, e
5
-
x
2
+
90
x
b
5
[25, 30]
c
3, c
4
-
x
3
+
25
x
2
+
4500
x
b
6
[30, 33]
c
3, c
4
-
x
3
+
30
x
2
+
400
x
b
7
[65, 70]
e
6, e
7, e
8
x
2
-
160
x
+
6400
b
8
[30, 33]
c
5, c
6
-
x
3
+
25
x
2
+
12250
b
9
[25, 28]
c
5, c
6
-
x
3
+
25
x
2
+
4500
b
10
[55, 60]
e
9, e
10, e
11
x
2
-
160
x
+
6400
b
11
[30, 33]
c
7, c
8
-
x
3
+
30
x
2
+
50000
b
12
[20, 23]
c
7, c
8
-
x
3
+
20
x
2
+
9000
b
13
[80, 95]
e
12, e
13, e
14
x
2
-
200
x
+
10000
b
14
[40, 80]
c
9, c
10
-
x
3
+
40
x
2
+
4500
x
b
15
[30, 60]
c
9, c
10
-
x
3
+
25
x
2
+
2450
x
b
16
[80, 115]
e
15, e
16
-
x
2
+
140
x
-
100
c
1
[35, 40]
e
1, e
2
-
x
3
+
35
x
2
+
750
x
c
2
[25, 30]
e
3, e
4, e
5
-
x
3
+
20
x
2
+
1500
x
c
3
[30, 35]
e
3, e
4, e
5
-
x
3
+
30
x
2
+
16000
c
4
[25, 27]
e
6, e
7, e
8
-
x
3
+
20
x
2
+
9000
c
5
[35, 37]
e
6, e
7, e
8
-
x
3
+
35
x
2
+
200
x
c
6
[30, 32]
e
9, e
10, e
11
-
x
3
+
30
x
2
+
400
x
c
7
[20, 22]
e
9, e
10, e
11
-
x
3
+
15
x
2
+
450
x
c
8
[30, 32]
e
12, e
13, e
14
x
2
-
100
x
+
2500
c
9
[40, 42]
e
12, e
13, e
14
2
x
2
-
480
x
+
7200
c
10
[45, 85]
e
15, e
16
-
x
2
+
100
x
+
1100
e
1
[65, 70]
g
1, g
2
2
x
2
-
320
x
+
12800
e
2
[30, 35]
f
1, f
2
-
x
3
+
30
x
2
+
400
x
e
3
[35, 37]
f
1, f
2
-
3
x
3
+
90
x
2
+
3000
x
e
4
[60, 65]
g
3, g
4, g
5
x
2
-
140
x
+
4900
e
5
[30, 32]
f
3, f
4
x
4
-
80
x
3
+
1600
x
2
e
6
[25, 27]
f
3, f
4
x
4
-
60
x
3
+
900
x
2
e
7
[55, 60]
g
6, g
7, g
8
-
x
3
+
55
x
2
+
1050
x
e
8
[20, 22]
f
5, f
6
-
x
3
+
600
x
+
150
e
9
[25, 27]
f
5, f
6
2
x
4
-
120
x
3
+
900
x
2
e
10
[50, 55]
g
9, g
10, g
11
-
x
3
+
50
x
2
+
600
x
e
11
[20, 22]
f
7, f
8
x
4
-
60
x
3
+
900
x
2
e
12
[25, 27]
f
7, f
8
-
x
3
+
25
x
2
+
600
x
e
13
[20, 25]
g
12, g
13, g
14
x
4
-
56
x
3
+
784
x
2
e
14
[45, 90]
f
9, f
10
2
x
2
-
400
x
+
20000
e
15
[40, 75]
f
9, f
10
3
x
2
-
480
x
+
19200
e
16
[85, 130]
g
15, g
16
2
x
2
-
600
x
+
45000
f
1
[30, 35]
g
1, g
2
-
x
3
+
30
x
2
+
675
x
f
2
[25, 28]
g
3, g
4, g
5
2
x
4
-
120
x
3
+
1800
x
2
f
3
[30, 33]
g
3, g
4, g
5
-
2
x
3
+
60
x
2
+
700
x
f
4
[30, 33]
g
6, g
7, g
8
x
4
-
80
x
3
+
1600
x
2
f
5
[35, 38]
g
6, g
7, g
8
-
3
x
3
+
105
x
2
+
600
x
f
6
[25, 28]
g
9, g
10, g
11
x
4
-
60
x
3
+
900
x
2
f
7
[25, 28]
g
9, g
10, g
11
2
x
4
-
160
x
3
+
4000
x
2
f
8
[30, 33]
g
12, g
13, g
14
2
x
4
-
200
x
3
+
5000
x
2
f
9
[35, 35]
g
12, g
13, g
14
300000
f
10
[40, 75]
g
15, g
16
3
x
2
-
540
x
+
24300
g
1
[70, 75]
p
1, p
2
2
x
2
-
340
x
+
14450
g
2
[35, 40]
h
1, h
2
-
3
x
3
+
105
x
2
+
2250
x
g
3
[30, 43]
h
1, h
2
x
2
-
100
x
+
2500
g
4
[65, 70]
p
3, p
4, p
5
-
x
3
+
65
x
2
+
1200
x
g
5
[25, 28]
h
3, h
4
3
x
4
-
180
x
3
+
2700
x
2
g
6
[25, 28]
h
3, h
4
2
x
4
-
160
x
3
+
3200
x
2
g
7
[60, 65]
p
6, p
7, p
8
x
2
-
140
x
+
4900
g
8
[30, 33]
h
5, h
6
3
x
4
-
210
x
3
+
3675
x
2
g
9
[25, 28]
h
5, h
6
2
x
4
-
200
x
3
+
5000
x
2
g
10
[60, 65]
p
9, p
10, p
11
3
x
2
-
280
x
+
9800
g
11
[15, 18]
h
7, h
8
-
x
5
+
15
x
4
+
2000
x
2
g
12
[30, 30]
h
7, h
8
60000
g
13
[20, 25]
p
12, p
13, p
14
5
x
4
-
3000
x
3
+
4500
x
2
g
14
[30, 35]
h
9, h
10
-
2
x
3
+
60
x
2
+
800
x
g
15
[35, 65]
h
9, h
10
x
2
-
140
x
+
4900
g
16
[80, 125]
p
15, p
16
x
2
-
280
x
+
19600
h
1
[30, 35]
p
1, p
2
-
x
3
+
30
x
2
+
16000
h
2
[25, 27]
p
3, p
4, p
5
4
x
4
-
280
x
3
+
4900
x
2
h
3
[30, 32]
p
3, p
4, p
5
-
2
x
3
+
60
x
2
+
12250
h
4
[30, 32]
p
6, p
7, p
8
-
3
x
3
+
90
x
2
+
525
x
h
5
[25, 27]
p
6, p
7, p
8
3
x
4
-
180
x
3
+
2700
h
6
[35, 37]
p
9, p
10, p
11
-
2
x
3
+
70
x
2
+
16000
h
7
[25, 27]
p
9, p
10, p
11
x
4
-
80
x
3
+
64000
x
h
8
[25, 25]
p
12, p
13, p
14
80000
h
9
[40, 60]
p
12, p
13, p
14
x
2
-
130
x
+
4225
h
10
[40, 80]
p
15, p
16
x
2
-
170
x
+
7225
p
1
[60, 65]
v
1
3
x
2
-
450
x
+
16875
p
2
[30, 35]
r
1, r
2
-
x
3
+
30
x
2
+
16000
p
3
[35, 37]
r
1, r
2
-
2
x
3
+
70
x
2
+
800
x
p
4
[65, 70]
v
2
2
x
2
-
360
x
+
16200
p
5
[30, 32]
r
3, r
4
3
x
4
-
240
x
3
+
4800
x
2
p
6
[25, 27]
r
3, r
4
-
x
5
+
25
x
4
+
300
x
3
p
7
[50, 55]
v
3
-
2
x
3
+
100
x
2
+
72000
p
8
[15, 17]
r
5, r
6
-
x
5
+
225
x
3
+
2000
x
2
p
9
[20, 22]
r
5, r
6
2
x
4
-
100
x
3
+
1250
x
2
p
10
[55, 60]
v
4
-
x
3
+
55
x
2
+
42250
p
11
[15, 17]
r
7, r
8
-
2
x
5
+
450
x
3
+
4000
x
2
p
12
[20, 22]
r
7, r
8
3
x
4
-
150
x
3
+
2250
x
2
p
13
[8, 10]
v
5
3
x
6
-
90
x
5
+
675
x
4
p
14
[30, 35]
r
9, r
10
-
2
x
3
+
60
x
2
+
800
x
p
15
[35, 65]
r
9, r
10
x
2
-
160
x
+
6400
p
16
[95, 140]
v
6
x
2
-
300
x
+
22500
r
1
[25, 30]
v
1
-
x
3
+
25
x
2
+
24000
r
2
[35, 38]
v
2
-
2
x
3
+
70
x
2
+
900
x
r
3
[30, 33]
v
2
-
4
x
3
+
120
x
2
+
1600
x
r
4
[25, 28]
v
3
-
2
x
3
+
50
x
2
+
50000
r
5
[30, 33]
v
3
-
6
x
3
+
180
x
2
+
2400
x
r
6
[25, 28]
v
4
-
3
x
3
+
75
x
2
+
75000
r
7
[30, 33]
v
4
-
4
x
3
+
120
x
2
+
1600
x
r
8
[25, 28]
v
5
-
4
x
3
+
100
x
2
+
2200
x
r
9
[40, 45]
v
5
2
x
4
-
240
x
3
+
432000
x
r
10
[55, 90]
v
6
x
2
-
200
x
+
10000
v
1
[75, 80]
—
2
x
2
-
360
x
+
19200
v
2
[50, 55]
—
-
3
x
3
+
150
x
2
+
108000
v
3
[55, 60]
—
2
x
2
-
400
x
+
20000
v
4
[40, 45]
—
0.5
x
4
-
60
x
3
+
108000
v
5
[85, 90]
—
2
x
2
-
440
x
+
24200
v
6
[90, 150]
—
x
2
-
400
x
+
40000We use our algorithm to simplify the nonlinear time-cost tradeoff problem as follows.Step 1.
Represent the project as a CPM network based on Table1 (let d
i
j
=
l
i
j), and assist activity (
1,52
) with duration d
1,52
=
520.Step 2.
Letd
i
j
=
l
i
j of each activity (
i
,
j
), and compute time parameters, as in Figure 1.Figure 1
Time parameters for all activities with their shortest durations.Step 3.
For activitya
5, remove duration longer than L
T
6
-
E
T
1
=
85; that is, remove duration interval [
85,100
], and let u
a
5
:
=
85; similarly, remove duration interval [
90,120
] of activity a
6, duration interval [
55,80
] of activity b
14, duration interval [
45,60
] of activity b
15, duration interval [
90,115
] of activity b
16, duration interval [
60,85
] of activity c
10, duration interval [
65,90
] of activity e
14, duration interval [
55,75
] of activity e
15, duration interval [
95,130
] of activity e
16, duration interval [
55,75
] of activity f
10, duration interval [
50,65
] of activity g
15, duration interval [
90,125
] of activity g
16, duration interval [
55,80
] of activity h
10, duration interval [
50,65
] of activity p
15, duration interval [
105,140
] of activity p
16, duration interval [
70,90
] of activity r
10, and duration interval [
100,150
] of activity v
6.Step 4.
Letd
i
j
=
u
i
j, and compute time parameters, as in Figure 2.Figure 2
Time parameters for all activities with their remaining longest durations.Step 5.
Remove activities whoseT
F
i
j
≥
E
T
52
-
λ
=
635
-
520
=
115, as in Figure 3.Figure 3
Network with nonredundant activities.Step 6.
There are no durations shorter thanL
T
j
-
E
T
i
-
E
T
52
+
λ of each remaining activity (
i
,
j
) in Figure 3; therefore we could not remove them.After the equivalent simplification, a networkG
* is acquired (Figure 4). Obviously, network G
* is much simpler than the old network (Figure 1), and duration intervals of many remaining activities are significantly narrowed.Figure 4
NetworkG
*.Next we further solved the nonlinear TCTP that computed the optimal durations of activities using the mathematical model in Section4.1 and intelligent algorithm software, such as LINDO. The experiment was performed on a PC (1 CPU, Intel 2.0 GHz, 1 G RAM) using the Windows XP operating system.(i)
We first solved the problem without simplification and obtained the project cost of 749,351,200. The computation time was ~30 min.
(ii)
And then we solved the problem after the simplification and obtained the project cost of 749,106,282, which is 2,449,108 cheaper than the former. The computation time was ~2 sec, which is also much faster than the former.This experiment further tests and verifies that the equivalent simplification could improve the effect and accuracy of the solution of the nonlinear continuous TCTP.


## 5.2. Equivalent Simplification of the DTCTP

The detailed information for a project with 88 activities is shown in Table2 (similarly, the cost unit is dollar and time unit is day). The start-time of any activity is no earlier than the finish-time of its immediate predecessor activity, and each activity has three time-cost modes. If the project must be finished within 385 (λ
=
520) at a minimum cost, then the amount of schemes is 3
88
≈
1
0
42. What is the equivalent simplification to improve scheduling effect?Table 2
Modes of each activity.
Activity code
Immediate successor
m
1
m
2
m
3
d
c
d
c
d
c
a
1
b
1, b
2
30
58
33
53
35
50
a
2
b
3, b
4, b
5
25
46
27
42
30
40
a
3
b
6, b
7, b
8
45
78
49
75
50
70
a
4
b
9, b
10, b
11
38
66
39
63
40
60
a
5
b
12, b
13
24
50
28
47
30
45
b
1
c
1, c
2
41
62
42
55
45
50
b
2
c
3, c
4, c
5
15
78
18
70
20
65
b
3
c
1, c
2
19
32
23
24
25
20
b
4
c
3, c
4, c
5
12
35
14
32
15
30
b
5
c
6, c
7, c
8
23
102
27
95
30
90
b
6
c
3, c
4, c
5
6
50
8
45
10
40
b
7
c
6, c
7, c
8
16
270
18
200
20
150
b
8
c
9, c
10, c
11
42
115
43
100
45
75
b
9
c
6, c
7, c
8
58
65
59
58
60
55
b
10
c
9, c
10, c
11
11
40
14
37
15
35
b
11
c
12, c
13
16
82
19
77
20
75
b
12
c
9, c
10, c
11
26
72
27
68
30
65
b
13
c
12, c
13
35
100
38
90
40
85
c
1
d
1, d
2
28
85
30
76
32
70
c
2
d
3, d
4, d
5
32
55
34
45
35
40
c
3
d
1, d
2
36
155
38
135
40
120
c
4
d
3, d
4, d
5
15
60
18
55
20
50
c
5
d
6, d
7, d
8
27
14
28
11
30
10
c
6
d
3, d
4, d
5
19
15
21
12
22
10
c
7
d
6, d
7, d
8
58
80
59
75
60
60
c
8
d
9, d
10, d
11
11
68
13
60
15
55
c
9
d
6, d
7, d
8
20
145
23
120
25
100
c
10
d
9, d
10, d
11
45
70
47
55
50
50
c
11
d
12, d
13
37
105
38
90
40
80
c
12
d
9, d
10, d
11
31
45
33
38
35
30
c
13
d
12, d
13
30
27
32
22
35
20
d
1
e
1, e
2
41
68
43
65
45
60
d
2
e
3, e
4, e
5
37
100
40
66
42
60
d
3
e
1, e
2
26
52
29
48
30
45
d
4
e
3, e
4, e
5
31
25
32
22
35
20
d
5
e
6, e
7, e
8
22
60
24
50
25
45
d
6
e
3, e
4, e
5
45
75
48
60
50
50
d
7
e
6, e
7, e
8
17
105
18
90
20
80
d
8
e
9, e
10, e
11
33
95
34
80
35
65
d
9
e
6, e
7, e
8
21
50
23
44
25
40
d
10
e
9, e
10, e
11
15
23
17
21
20
20
d
11
e
12, e
13
32
240
34
210
35
200
d
12
e
9, e
10, e
11
25
65
26
55
30
50
d
13
e
12, e
13
75
105
79
90
80
85
e
1
f
1, f
2
25
33
28
31
30
30
e
2
f
3, f
4, f
5
36
130
39
110
40
100
e
3
f
1, f
2
28
58
30
53
32
50
e
4
f
3, f
4, f
5
20
105
23
96
25
90
e
5
f
6, f
7, f
8
40
80
42
66
45
60
e
6
f
3, f
4, f
5
26
85
29
70
30
65
e
7
f
6, f
7, f
8
25
125
28
110
30
90
e
8
f
9, f
10, f
11
30
320
33
290
35
240
e
9
f
6, f
7, f
8
34
90
37
80
40
70
e
10
f
9, f
10, f
11
17
80
19
72
20
65
e
11
f
12, f
13
48
40
49
36
50
30
e
12
f
9, f
10, f
11
31
42
32
38
35
35
e
13
f
12, f
13
41
115
42
100
45
90
f
1
g
1, g
2
16
60
17
48
20
40
f
2
g
3, g
4, g
5
10
85
13
72
15
65
f
3
g
1, g
2
24
78
26
70
30
60
f
4
g
3, g
4, g
5
39
120
43
115
45
100
f
5
g
6, g
7, g
8
18
52
20
48
22
45
f
6
g
3, g
4, g
5
45
85
47
70
50
65
f
7
g
6, g
7, g
8
36
125
38
110
40
90
f
8
g
9, g
10, g
11
25
320
27
290
30
240
f
9
g
6, g
7, g
8
22
90
24
80
25
70
f
10
g
9, g
10, g
11
17
80
20
72
22
65
f
11
g
12, g
13
34
40
36
36
40
30
f
12
g
9, g
10, g
11
41
42
43
38
45
35
f
13
g
12, g
13
65
115
69
100
70
90
g
1
h
1
44
60
47
48
50
40
g
2
h
2
31
85
32
72
35
65
g
3
h
1
35
78
37
70
40
60
g
4
h
2
31
120
33
115
36
100
g
5
h
3
37
52
39
48
42
45
g
6
h
2
17
75
19
65
20
60
g
7
h
3
21
20
23
17
25
15
g
8
h
4
26
58
27
55
30
50
g
9
h
3
40
36
42
33
45
30
g
10
h
4
26
50
28
44
30
40
g
11
h
5
21
13
24
11
25
10
g
12
h
4
34
80
37
75
42
70
g
13
h
5
42
42
43
36
45
30
h
1
—
28
23
29
21
30
20
h
2
—
31
62
33
55
35
50
h
3
—
29
17
30
16
32
15
h
4
—
40
54
41
52
42
50
h
5
—
35
80
39
75
40
65Step 1.
Represent the project as an activity network based on Table2 (let each activity choose mode 1), and assist activity (
1,37
) with duration d
1,37
=
385.Step 2.
Letd
i
j
=
l
i
j of each activity (
i
,
j
), and compute time parameters, as in Figure 5.Figure 5
Time parameters for all activities with their shortest durations.Step 3.
For activitya
3, remove modes 2 and 3 whose durations are longer than L
T
4
-
E
T
1
=
48; similarly, remove modes 2 and 3 of activity d
13, mode 3 of activity e
13, modes 2 and 3 of activity f
13, mode 3 of activity g
12, and modes 2 and 3 of activity h
5.Step 4.
Let each activity in Figure5 choose the mode with the longest duration from its remaining modes, and compute time parameters, as in Figure 6.Figure 6
Time parameters for all activities with their remaining longest durations.Step 5.
Remove activities whoseT
F
i
j
≥
E
T
37
-
λ
=
392
-
385
=
7, as in Figure 7.Figure 7
Network with nonredundant activities.Step 6.
There are no durations shorter thanL
T
j
-
E
T
i
-
E
T
37
+
λ within the remaining modes of each activity in Figure 7; therefore we could not remove them.NetworkG
* is obtained by the above simplification and shown in Figure 8, and brackets around each activity denote its choice of time-cost modes. It is much simpler than Figure 5, and the amount of schemes is only 3
9
×
2
2
=
78732. The optimal scheme is easily determined using any computer and algorithm.Figure 8
NetworkG
*.


## 6. Conclusion

A project can be represented by using an activity network, and the activity floats and activity paths in the network are important to solve many project scheduling problems. For example, for resource leveling, the range of adjusting each activity is determined by its float; and for time-cost tradeoff, a key step is to compress long paths to required lengths. In conventional thinking, activity floats and paths are separate, and all floats are easy to compute but many paths are difficult to find. However, we discovered that there are close relationships between activity floats and paths, and paths and their lengths can be represented by floats. For instance, the total float can be used to compute length of the longest path passing an activity; the free float and safety float can be used to find required paths between two nodes; and the interference float can be used to compute path lengths when changing the network’s structure (adding or flipping arcs). Based on these, we established the float-path theory, which helps to simplify path problems.We use the float-path theory to solve a classic project scheduling problem—the time-cost tradeoff problem, especially the nonlinear continuous and discrete (strong NP-hard) versions. Due to the difficulty, we first simplify the problem rather than designing algorithms to solve it directly. The simplification is to remove redundant activities and redundant durations (time-cost mode) of nonredundant activities, which need to compute enormous path lengths. We used the float-path theory to transform the simplification into computations of some activity floats and designed a polynomial algorithm. Complexity of the algorithm isO
(
m
) and m indicates the amount of activities. After the simplification, the old problem may be solved more effectively using current algorithms.



---

*Source: 539374-2015-02-26.xml*