The LESS method

Adam Kucharski

2024-01-06

Time-cost analysis

Some activities may be performed for a shorter time than originally assumed provided that certain additional costs are incurred. However, this reduction has a time limit below which it is not possible to perform activities, regardless of costs incurred to accelerate them. Let’s make the following assumptions:

The decision problem we deal with concerns the minimization of the total cost of the project (TC) and we will use the LESS method to solve it. The total cost consists of two components:

The purpose of the time-cost analysis is to determine the end term of the project at which the expression \(TC = DC + IC\) reaches its minimum.

In the LESS model, we distinguish the following components:

The duration of the activity (i,j) meets the condition: \(t_{ij}^{c}\leqslant t_{ij}\leqslant t_{ij}^{n}\). For each activity, we calculate the unit cost of acceleration \(s_{ij}\) according to the formula:

\[ s_{ij}=\frac{C_{ij}^{b}-C_{ij}^{n}}{t_{ij}^{n}-t_{ij}^{b}} \]

The time-cost analysis runs in iterations and can be described with the following steps:

  1. Carry out the analysis assuming normal duration of activities.
  2. In this and each subsequent step, accelerate the selected critical activity by 1 unit and recalculate the total cost.
  3. Choose the critical activity with the lowest unit acceleration cost.
  4. If there are parallel critical activities, speed up one critical activity for each of the parallel branches. The selection of the activities to be accelerated is determined by the sum of the unit acceleration costs of each of the parallel critical branches.

LESS method in package critpath

Notice!

The critpath package requires the DiagrammeR, ggplot2, reshape2 and strigr packages to be installed additionally.

Let us assume that the activities are described on arcs (AoA model). Consider a small example where 5 nodes are connected by 7 actions as shown in the graph below.

plot_graphAOA(lessexample1)

Fig. 1. Graph for the lessexample1 dataset

The lessexample1 data set contains the data frame shown in the table below. This is a variant in which a start and end node are given for each activity. It is also possible to provide a list of predecessors. See the Introduction vignette for more information.

Tab. 1. Data for the LESS model
Start. node End. node Name Normal duration Crash duration Normal cost Crash cost
1 2 A 4 2 50 70
1 3 B 6 3 40 55
2 3 C 2 1 20 24
2 4 D 6 4 100 130
3 4 E 3 2 50 60
3 5 F 3 3 25 25
4 5 G 5 3 60 75

As with other critpath functions, the column names can be anything, but the order they are in is significant. The first two columns describe the structure of the graph, the third contains activities labels, the others contain data on the project. The number of rows corresponds to the number of activities that make up the project.

First, we present the function solve_lessAOA(data, ICconst, ICslope), which is the most important function for the LESS method. It iterates through the procedure and returns the graph and information about the solution.

The function takes three arguments: data frame, intercept and slope of the linear indirect cost function. The indirect cost function in our example takes the form: \(IC = 50 + 15t_{5}\), where \(t_{5}\) denotes the completion time in the last, fifth node of the graph.

z <- solve_lessAOA(lessexample1, 50, 15)
#> Reduced completion time:  11

The results are as follows:

# Data frame with some data and partial results
z[2]
#> $summary_less
#>      id from to name time crash.time TF accel.cost
#> 1->2  1    1  2    A    2          2  0       10.0
#> 1->3  2    1  3    B    5          3  0        5.0
#> 2->3  3    2  3    C    2          1  1        4.0
#> 2->4  4    2  4    D    6          4  0       15.0
#> 3->4  5    3  4    E    3          2  0       10.0
#> 3->5  6    3  5    F    3          3  3        NaN
#> 4->5  7    4  5    G    3          3  0        7.5
# List of critical activities
z[3]
#> $critical
#> [1] "A" "B" "D" "E" "G"
# The total cost vector of all iterations
z[4]
#> $TC_iter
#> [1] 620.0 612.5 605.0 600.0 600.0 605.0
# Minimum total cost
z[5]
#> $min_cost
#> [1] 600
# Completion time for normal time
z[6]
#> $normal_DD
#> [1] 15
# The shortest completion time
z[7]
#> $min_time
#> [1] 11

Using the plot_crit_pathAOA() function we will obtain a graph with marked critical activities.

plot_graphAOA(solved = z)

Fig. 2. Critical activities for the lessexample1 dataset

It is also possible to make a graph of the evolution of total costs thanks to the function plot_TC().

plot_TC(z)
Fig. 3. Total cost chart for the lessexample1 dataset

Fig. 3. Total cost chart for the lessexample1 dataset