# Productivity Oriented Cooperative Approach to Scheduling IT Project Tasks

Tadeusz Nowicki, Robert Waszkowski

► To cite this version:

Tadeusz Nowicki, Robert Waszkowski. Productivity Oriented Cooperative Approach to Scheduling IT Project Tasks. 16th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Jun 2017, Bialystok, Poland. pp.354-365, 10.1007/978-3-319-59105-6_30 hal-01656216

HAL Id: hal-01656216

https://inria.hal.science/hal-01656216

Submitted on 5 Dec 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Productivity oriented cooperative approach to scheduling IT project tasks

Tadeusz Nowicki and Robert Waszkowski

Military University of Technology, Warsaw, Poland

tadeusz.nowicki@wat.edu.pl, robert.waszkowski@wat.edu.pl

**Abstract.** Task execution duration depends on the employee who performs the task. Specifically in IT projects, an experienced employee can perform assigned tasks several times faster than a novice worker can. Preparing the schedule, project manager should take into account individuals' productivity determined by analyzing historical data of tasks implementation. Consequently, measured productivity is used in preparing the schedule in an optimal manner (minimizing the time needed to complete project tasks by a team of workers with different skills). As an extension of previous studies the authors formulate a linear programming problem including the possible cooperation of employees with tasks execution. The result of the conducted research is a complete package supporting project managers in determining productivity and scheduling.

**Keywords:** IT project management, scheduling, linear programming.

## 1 Introduction

One of the most important task for project managers is to prepare the schedule. To arrange an optimal schedule the manager must have knowledge of tasks structure and their workload. Tasks structure is based on the execution order, determining predecessors and successors of each task. Workload is defined as the standard time needed to complete each task [1, 5, 6, 9, 10, 11, 12, 13, 14]. In many works the authors consider the situation where co-operators are allowed [2, 3, 4]. However, it is not assumed that co-operation is not additive. In addition, co-operation does not reduce the costs, but shorten the execution time of a set of tasks. In this paper is considered exactly such a problem.

In fact, duration of the task execution depends on the employee who performs the task. In many situations, experience and skills of workers can result in significant differences in the execution time of tasks. According to the conducted research, an experienced employee can perform assigned tasks several times faster than a novice worker.

The manager usually has a team composed of both experienced and novice staff. Therefore, it is crucial which worker will perform a given task. The correct assignment of the task performers can result in a significant shortening duration of the overall project.
In practice, the knowledge about the productivity of each team member increases with the development time. If the manager is able to measure productivity, he can reschedule next stages of the project in a way to achieve optimal results. Therefore, the toolkit of a project manager must be equipped with computer-aided tools, allowing him/her to prepare the schedule as a result of a defined optimization problem. Preparing the schedule project manager should take into account individuals' productivity determined by analyzing historical data of tasks implementation. Consequently, measured productivity is used in preparing the schedule in an optimal manner (minimizing the time needed to complete project tasks by a team of workers with different skills).

In the article we assume scheduling of the project on the understanding that employees can cooperate and divide daily working time between tasks. It means that a task can be performed by more than one worker at the same time and a worker can perform more than one task at a time.

# 2 MATHEMATICAL MODEL

## 2.1 The problem formulation

We assume that:

$R = \{1,2,3,...,r,...,R\}$ - is a set of numbers of the project task types

$Z = \{1,2,3,...,z,...,Z\}$ - is a set of numbers of project tasks

The types of project tasks, that have to be performed, can be described by the vector:

$$R^Z = (r_1, r_2, ..., r_z, ..., r_Z)$$

where $r_z$ - is the number of the type of the z-th task, $r_z \in R, z \in Z$

The task performance time is defined as an average time needed to perform the task by a worker without special skills. This time is called the reference time. The reference time is used to determine the task performance time of more qualified worker. The reference times for project tasks can be described by the vector:

$$C^w = (c_1^w, c_2^w, ..., c_z^w, ..., c_Z^w), z \in Z$$

The project tasks can include information about the need to perform other tasks before you started current task. Predecessors can be described by a matrix:

$$D = [d_{ij}]_{Z \times Z}$$

where

$$d_{z_1 z_2} = \begin{cases} 1 & - \text{ if the execution of task } z_2 \text{ have to precede} \\ 0 & - \text{ otherwise} \end{cases}$$
For the description of workers we assume that

$P = \{1,2,3,...,p,...,P\}$ – set of number of employees, to be taken into account in the tasks execution.

The suitability for performance of specific types of tasks can be defined for each employee. Let it be described by following matrix

$$U = [u_{pr}]_{P \times R}$$

where

$$u_{pr} = \begin{cases} 1 & \text{when the } p^{th} \text{ employee is able to accomplish the task of type } r \\ 0 & \text{otherwise} \end{cases} \\ p \in P, r \in R$$

The productivity of individual employees is different during the performance of different types of tasks. The difference in productivity of a given employee at a particular type of task is defined by a coefficient $\beta$, that represents how many standard time units assigned to perform a particular task the worker performs in one unit of his working time. Thus, the effectiveness of workers in the tasks of different types is defined by vector

$$\beta_p = (\beta_{p1}, \beta_{p2}, ..., \beta_{pr}, ..., \beta_{pR}), p \in P$$

Of course, if the p-th employee is not suitable for the task of r-type, which is defined in the matrix $U: u_{pr} = 0$, then there is also equality $\beta_{pr} = 0$.

Taking into account the productivity of the employee, the time for the task by the p-th worker (provided that the employee p suited to this type of task, namely $\beta_{pr} > 0$, $u_{pr} = 1$) is:

$$c_{pz} = \frac{c_z^w}{\beta_{prz}}$$

where

$$p \in P, z \in Z, r_z \in R^z, c_z^w \in C^w$$

## 2.2 Decision variables

The decision relating to the project schedule is described by matrix-vector:

$$(X, T, \dot{X})$$

where:

$$X = [x_{pz}]_{P \times Z}$$

and

$$x_{pz} = \begin{cases} 1 & \text{if the } p-th \text{ worker will perform } z-th \text{ task} \\ 0 & \text{otherwise} \end{cases}$$
$p \in P, z \in Z,$

$T = (\tau_1, \tau_2, \dots, \tau_z, \dots, \tau_Z),$

$\tau_Z$ - start time (number of an hour) of the z-th task,
and

$X' = [x'_{pz}]_{pzZ}$

$$x'_{pz} = \begin{cases} t'_{pz} & - \text{if } x_{pz} = 1 \text{ than } t'_{pz} \in \{1, 2, \dots, l_p\} \text{ means amount of hours during a day,} \\ 0 & - \text{if } x_{pz} = 0 \end{cases}$$

$\acute{x}_{pz}$ can also be represented using binary variables $\acute{x}_{pzl}$, and then becomes:

$$\acute{x}_{pz} = \sum_{l=1}^{l_p} \acute{x}_{pz'l}$$

## 2.3 Problem constraints

CA: each task must be completed by exactly one worker

$$\sum_{p=1}^{P} u_{pr_z} x_{pz} = 1, z \in Z \quad (CA)$$

CB: each worker has to perform at least one task

$$\sum_{z=1}^{Z} u_{pr_z} x_{pz} \geq 1, p \in P \quad (CB)$$

CC: task precedence must be taken into account

The condition that the task $z''$ must precede task $z'$ can be written as follows:

$$\tau_{z'} \geq d_{z'z''} \cdot \left( \tau_{z''} + \sum_{\substack{p=1 \\ u_{pr_{z''}} \neq 0}}^{P} x_{pz''} \cdot \frac{c_{z''}^{w}}{\beta_{pr_{z''}}} \right) \quad (CC)$$

for $z', z'' \in Z, z' \neq z''$

CD: the worker cannot work more than $l_p$ (i.e. 8) hours per day

To check the condition that the employee does not work more than eight hours a day, for each of the individual tasks, check for all tasks occurring at the time of its
initiation, if the amount of time spent per day on their implementation does not exceed eight hours.

To select tasks that are performed at the start time of another task it should be noted that the task z' continues at the start time of the task z'' if each of the following inequalities is true:

$$ \begin{cases} \tau_{z'} \le \tau_{z''}, & z', z'' \in Z \\ \tau_{z'} + c_{z'} \ge \tau_{z''}, & Z \end{cases} \quad \begin{array}{l} (CDA) \\ (CDB) \end{array} $$

Where inequality (CDA) means that the task z' begins earlier than the task z'' and inequality (CDB) means that the task z'' begins at the time the task z' lasts. The way to check if the inequality $\sum_j a_j x_j \le b$ is satisfied in [15]. Inequality $\tau_{z'} \le \tau_{z''}$ is equal to $\tau_{z'} - \tau_{z''} \le 0$, and the inequality (CDA) becomes:

$$ \begin{cases} \tau_{z'} - \tau_{z''} + M \cdot e_{z'z''}^1 \le M + 0 & (CDA1) \\ \tau_{z'} - \tau_{z''} - (m - \varepsilon) \cdot e_{z'z''}^1 \ge 0 + \varepsilon & (CDA2) \end{cases} $$

where m and M are, respectively, the lower and upper bound of the expression $(\tau_{z'} - \tau_{z''})$ and $\varepsilon$ is a small number that causes the failure of inequality.

If the set of all possible occurrences of the expression $(\tau_{z'} - \tau_{z''})$ is defined as:

$$ W = \{(\tau_{z'} - \tau_{z''}): z', z'' \in Z\} $$

then the lower and upper bound should be considered as such values of m and M, that satisfy the inequalities:

$$ \begin{cases} m \le y \\ M \ge y' \end{cases} \quad y \in W $$

After applying these transformations indicator variable $e_{z'z''}^1 = 1$, when the inequality (CDA) is satisfied.

The way to check if the inequality $\sum_j a_j x_j \ge b$ is satisfied in [15].

Inequality $\tau_{z'} + c_{z'} \ge \tau_{z''}$ can also be written as $\tau_{z'} - \tau_{z''} + c_{z'} \ge 0$.

In addition, substituting $c_{z'} = \sum_{p=1}^{P} \frac{c_{z'}^W}{\beta_{pr_{z'}}} \cdot x_{pz'}$ inequality can be written as

$$ \tau_{z'} - \tau_{z''} + \sum_{p=1}^{P} \frac{c_{z'}^W}{\beta_{pr_{z'}}} \cdot x_{pz'} \ge 0 $$

and then we have constraints in the form of:
$$
\left\{
\begin{array}{l}
\tau_{z'} - \tau_{z''} + \sum_{\substack{p=1 \\ \beta_{pr_{z'}} \neq 0}}^{P} \frac{c_{z'}^w}{\beta_{pr_{z'}}} \cdot x_{pz'} + m \cdot e_{z'z''}^2 \geq m + b \quad (\text{CDB1}) \\
\\
\tau_{z'} - \tau_{z''} + \sum_{\substack{p=1 \\ \beta_{pr_{z'}} \neq 0}}^{P} \frac{c_{z'}^w}{\beta_{pr_{z'}}} \cdot x_{pz'} - (M + \varepsilon)e_{z'z''}^2 \leq b - \varepsilon \quad (\text{CDB2})
\end{array}
\right.
, z', z'' \in Z
$$

That means that $e_{z'z''}^2 = 1$, when the inequality (CDB) is satisfied.
If $l_p$ is the number of allowable hours of work per day for a p-th worker, then:

$$
\sum_{z'=1}^{Z} (e_{z'z''}^{1} \cdot e_{z'z''}^{2} \cdot \acute{x}_{pz'}) \leq l_p, p \in P, z'' \in Z
$$

In the further considerations it is necessary to use binary variables. Thus $\acute{x}_{pz}$ can be
written as:

$$
\acute{x}_{pz} = \sum_{l=1}^{l_p} \acute{x}_{pz'l}
$$

and after substitution:

$$
\sum_{z'=1}^{Z} \left( e_{z'z''}^{1} \cdot e_{z'z''}^{2} \cdot \sum_{l=1}^{l_p} \acute{x}_{pz'l} \right) \leq l_p, p \in P, z'' \in Z(*)
$$

It should be noted that the sum is over all z, also for the case where z' = z''.

It is a non-linear inequality. Linearization method for such inequalities is described in
[15]. Let $\acute{y}_{pz'z''l} = e_{z'z''}^1 \cdot e_{z'z''}^2 \cdot \acute{x}_{pz'l}$. We then have:

$$
\sum_{z'=1}^{Z} \sum_{l=1}^{l_p} \acute{y}_{pz'z''l} \leq l_p, p \in P, z'' \in Z \quad (\text{CDC})
$$

With additional constraints defined as:

$$
\begin{cases}
e_{z'z''}^1 + e_{z'z''}^2 + \acute{x}_{pz'l} - \acute{y}_{pz'z''l} \le 2 & (\text{CDD1}) \\
e_{z'z''}^1 + e_{z'z''}^2 + \acute{x}_{pz'l} - 3\acute{y}_{pz'z''l} \ge 0 & (\text{CDD2})
\end{cases}
\ p \in P, z', z'' \in Z, l \in L
$$

After this transformation, we obtain the linear inequalities.
## 2.4 Objective function

We have the objective function:

$$F(X, T, \dot{X}) = \max_{z \in Z} \{\tau_Z + c_Z\}$$

and optimization problem:

$$\min_{X,T,\dot{X}} F(X, T, \dot{X})$$

So we have:

$$\min_{X,T,\dot{X}} \max_{z \in Z} \{\tau_Z + c_Z\}$$

what can be replaced with a linear optimization problem:

$$\min_{X,T,\dot{X}} g$$

- new linear objective function

$$g \ge \tau_Z + c_Z, z \in Z$$

- additional constraint

or, considering that:

$$c_Z = \frac{c_Z^W}{\sum_{\substack{p=1 \\ \beta_{prZ} \neq 0}}^P \beta_{prZ} \cdot x_{pz} \cdot \frac{\bar{x}_{pz}}{l_p}}$$

we have additional constraint as follow:

$$g \ge \tau_Z + \frac{c_Z^W}{\sum_{\substack{p=1 \\ \beta_{prZ} \neq 0}}^P \beta_{prZ} \cdot x_{pz} \cdot \frac{\bar{x}_{pz}}{l_p}}, z \in Z \quad (CX)$$

## 2.5 Optimization problem

Accordingly, the full optimization problem is as follows:

$$\min_{X,T,\dot{X}} g$$

subject to

$$\sum_{p=1}^{P} u_{prZ} x_{pz} = 1, z \in Z \quad (CA)$$

$$\sum_{z=1}^{Z} u_{prZ} x_{pz} \ge 1, p \in P \quad (CB)$$

$$\tau_{z'} \ge d_{z'z''} \cdot \left( \tau_{z''} + \sum_{\substack{p=1 \\ u_{pr_{z''}} \neq 0}}^{P} x_{pz''} \cdot \frac{c_{z''}^W}{\beta_{pr_{z''}}} \right) \quad (CC), z', z'' \in Z, z' \neq z''$$

$$\left\{ \begin{array}{l} \tau_{z'} - \tau_{z''} + M \cdot e_{z'z''}^1 \le M + 0 \quad (CDA1) \\ \tau_{z'} - \tau_{z''} - (m - \varepsilon) \cdot e_{z'z''}^1 \ge 0 + \varepsilon \quad (CDA2) \end{array} \right. \\ , z', z'' \in Z$$
$$
\left\{
\begin{array}{l}
\tau_{z'} - \tau_{z''} + \sum_{\substack{p=1 \\ \beta_{pr_{z'}} \neq 0}}^{P} \frac{c_{z'}^w}{\beta_{pr_{z'}}} \cdot x_{pz'} + m \cdot e_{z'z''}^2 \geq m + b \qquad (\text{CDB1}) \\
\tau_{z'} - \tau_{z''} + \sum_{\substack{p=1 \\ \beta_{pr_{z'}} \neq 0}}^{P} \frac{c_{z'}^w}{\beta_{pr_{z'}}} \cdot x_{pz'} - (M + \varepsilon)e_{z'z''}^2 \leq b - \varepsilon \qquad (\text{CDB2}) \\
\sum_{z'=1}^{Z} \sum_{l=1}^{l_p} \acute{y}_{pz'z''l} \leq l_p, p \in P, z'' \in Z \quad (\text{CDC})
\end{array}
\right.
$$

$$
\begin{cases}
e_{z'z''}^1 + e_{z'z''}^2 + \acute{x}_{pz'l} - \acute{y}_{pz'z''l} \le 2 & (\text{CDD1}) \\
e_{z'z''}^1 + e_{z'z''}^2 + \acute{x}_{pz'l} - 3\acute{y}_{pz'z''l} \ge 0 & (\text{CDD2}) \\
\text{, } p \in P, z', z'' \in Z, l \in L
\end{cases}
$$

$$
g \geq \tau_z + \frac{c_z^w}{\sum_{\substack{p=1 \\ \beta_{pr_z} \neq 0}}^{P} \beta_{pr_z} \cdot x_{pz} \cdot \frac{\bar{x}_{pz}}{l_p}}, z \in Z \quad (CX)
$$

3 Comparison of scheduling and without scheduling
cooperation

Below provides results of sample solutions of the task of determining the schedule
for versions with and without the cooperation of employees [1, 5, 6, 9, 10, 11, 12, 13,
14]. The solution of the same problem in two versions gives you the opportunity to
direct comparison of results.

The problem with no cooperation is described in detail in [7]. Let us compare the
scheduling results concerning cooperation possibility described in the current article
with the results based on the scheduling model described in [7].

For evaluation of the method for determining the optimal allocation of workers to
the tasks let us consider the following case.

Let 3 equally complex design tasks will be performed by 2 employees of equal productivity. Individual tasks do not depend on each other, and so they can be performed at the same time and in any order. The workload for each task is 8 hours, and the productivity of each worker is 1.

3.1 Case #1. Scheduling with no cooperation

Let us consider the case where the cooperation of employees in carrying out the
task is not allowed. The results of the calculations for such case is shown in the follow-
ing table and is described in the Gantt chart and resource load chart.
<table><caption>**Table 1.** Results for case #1 – no cooperation</caption><thead><tr><th>Task</th><th>Workload [h]</th><th>Predecessor</th><th>Employee assigned</th><th>Productivity</th><th>Start time</th><th>Duration [h]</th><th>End time</th></tr></thead><tbody><tr><td>2</td><td>8</td><td></td><td>2</td><td>1</td><td>0</td><td>8</td><td>8</td></tr><tr><td>3</td><td>8</td><td></td><td>1</td><td>1</td><td>8</td><td>8</td><td>16</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 2.** Resource Load Chart for case #1 – no cooperation</figcaption></figure>

<figure><img src="image_3.png" /></figure>
On the resource load chart, it is shown the usage of the two employees labeled with different colors. The upper course of the graph for the selected worker means that the worker is working on a task, the lower - means that an employee at a given time is not used for the implementation of any task.

## 3.2 Case #2. Scheduling with cooperation

Let us consider the case where the cooperation of employees in carrying out the task is allowed.

The results of the calculations for such case is shown in the following table and is described in the Gantt chart and resource load chart.

<table><caption>Table 2. Results for case #2 – cooperation</caption><thead><tr><th>Task</th><th>Workload [h]</th><th>Predecessor</th><th>Employee assigned</th><th>Productivity</th><th>Start time</th><th>Duration [h]</th><th>End time</th></tr></thead><tbody><tr><td>1</td><td>8</td><td></td><td>1</td><td>1</td><td>0</td><td>8</td><td>8</td></tr><tr><td>2</td><td>8</td><td></td><td>2</td><td>1</td><td>0</td><td>8</td><td>8</td></tr><tr><td>3</td><td>8</td><td></td><td>1, 2</td><td>1, 1</td><td>8</td><td>4</td><td>12</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 4. Resource Load Chart for case #2 – cooperation</figcaption></figure>
<figure><img src="image_5.png" /></figure>

Just like before, on the resource load chart, it is shown the usage of the two employees labeled with different colors. The upper course of the graph for the selected worker means that the worker is working on a task, the lower - means that an employee at a given time is not used for the implementation of any task.

Assuming the cooperation opportunities of workers in the implementation of the design tasks, significant reduction of the overall duration time and a better use of resources is achieved. Employees are equally loaded throughout the duration of the project.

## 4 Conclusion

The mathematical model followed by formulation of optimization problems has been developed for the purpose of a schedule creation. Productivity of project team members is taken into account in the model. The authors designed and built software that formulates a linear programming problem based on a mathematical model. The problem is then solved using numerical methods. The result of the conducted research is a complete IT solution package supporting project managers in determining productivity and scheduling.

As for the further research it is worth to examine the possibility to prepare models for other variants of the problem, as far as to rebuild the model in a way that could use the estimation of the future productivity. Furthermore, the impact of differentiation of the software development processes on the productivity is also worth researching.

## 5 References

1. Brucker P. (2007) Scheduling algorithms. Springer, Berlin, Heidelberg.

2. Chen Z.L., Hall N.G. (2007) Supply Chain Scheduling: Conflict and Cooperation in Assembly Systems. Operations Research, vol. 55, No 6, pp. 1072-1089.

3. Calleja P., Estévez-Fernández A., Borm P., Hamers H. (2006) Job scheduling, cooperation, and control. Operations Research Letters, Volume 34, Issue 1, pp. 22-28.
4. Chryssis G., Russell A., Shvartsman A.A. (2005) Work-Competitive Scheduling for Coop-erative Computing with Dynamic Groups. SIAM J. Comput., 34(4), pp. 848–862.

5. El-Rewini H., Lewis T.G., Ali H.H. (1994) Task Scheduling in Parallel and Distributed Systems. Prentice Hall Series in Innovative Technology.

6. Janiak A. (2006) Scheduling in computer and manufacturing systems. WKŁ Publisher, Warsaw.

7. Nowicki T., Waszkowski R. (2013) The method for solving productivity oriented schedul-ing problem. Research in Logistics and Production, Poznan University of Technology.

8. Nowicki T. (1994) – Linear Mixed Equivalent of a Stochastic Scheduling Problem with Different Processors. Biul. WAT/4/1994.

9. Nowicki T. (1996) – Stochastic bi-objective Scheduling Problem in a Multiprocessor Computer System. The 5'th International workshop on Project Management and Schedul-ing. April 11-13.1996, Poznań.

10. Pinedo M., L. (2008) Scheduling. Theory, algorithms and Systems. Springer, New York, London, Heidelberg.

11. Pinedo M., L. (2005) Scheduling. Planning and scheduling In manufacturing and services. Springer, New York.

12. Pochet Y., Wolsey L., A., (2005) Production planning by mixed integer programming. Springer, New York, London, Heidelberg.

13. Simchi-Levi D., Chen X., Bramel J., (1997), The Logic of Logistics, Springer, New York.

14. Sinnen O. (2006) Task scheduling for parallel systems. J. Willey & Sons, Inc., Hoboken, New Jersey.

15. Waszkowski R. (2012) Methods and tools for productivity evaluation in IT projects, doc-toral disertation, WAT, Warszawa.