=Paper=
{{Paper
|id=Vol-1985/BPM17industry03
|storemode=property
|title=Improving Operational Performance in Service Delivery Organizations by Using a Metaheuristic Task Allocation Algorithm
|pdfUrl=https://ceur-ws.org/Vol-1985/BPM17industry03.pdf
|volume=Vol-1985
|authors=Rahul Paul,R. P. Jagadeesh Chandra Bose,Stephan K. Chalup,Raravi Gurulingesh
|dblpUrl=https://dblp.org/rec/conf/bpm/PaulBCR17
}}
==Improving Operational Performance in Service Delivery Organizations by Using a Metaheuristic Task Allocation Algorithm==
https://ceur-ws.org/Vol-1985/BPM17industry03.pdf
Improving Operational Performance in Service Delivery
Organizations by Using a Metaheuristic Task Allocation
Algorithm
Rahul Paul1? , R. P. Jagadeesh Chandra Bose2 , Stephan K. Chalup1 , and Gurulingesh
Raravi2
1
The University of Newcastle, Callaghan, Australia
2
Conduent Labs, India
Rahul.Paul@uon.edu.au, Jagadeesh.Prabhakara@conduent.com,
Stephan.Chalup@newcastle.edu.au, gurulingesh@gmail.com
Abstract. Efficient allocation of tasks to employees is crucial in service delivery
organizations. It facilitates meeting the service level agreements (SLAs), utilizes
the employees well and improves the operational performance. Task allocation is
a challenging problem that addresses the inter-dynamics of tasks and employees,
considering factors such as diversity, utilization, skills and fairness. The combina-
tion of task deadlines and associated SLA requirements adds another dimension
to the complexity of the problem. In this paper, we propose a tabu search algo-
rithm for efficient task allocation. The algorithm is employee utilization, produc-
tivity and fairness aware. We evaluate the proposed algorithm using real world
transaction processing data from a large service delivery organization. The re-
sults show that the proposed approach can reduce deadline misses substantially
in comparison to the organization’s current approach.
Keywords: Operational Excellence, Transaction Processing, Task Allocation,
Deadline Violation, Tabu-search, Meta heuristic
1 Introduction
Service delivery organizations (SDOs) provide operations support, sales services and
information technology services like transaction processing. It is not uncommon for
organizations to handle large volumes of transactions (of the order of a few hundred
thousands) every day. In addition to the volume, organizations often face the issue of
inter-arrival rate of the task and different types of transactions that they handle. Fur-
thermore, organizations have to meet SLAs agreed upon with clients and are always
required to perform better in terms of optimal cost and their operational efficiency. An
example SLA could be that 98% of transactions should be completed within one hour
(i.e., the turnaround time of transactions should be less than one hour for at least 98%
of transactions).
?
M. Brambilla, T. Hildebrandt (Eds.): BPMN 2017 Industrial Track Proceedings, CEUR-
WS.org, 2017. Copyright 2017 for the individual papers by the papers’ authors. Copying
permitted for private and academic purposes. This volume is published and copyrighted by its
editors.
Rahul Paul, R. P. Jagadeesh Chandra Bose, Stephan K. Chalup, Raravi Gurulingesh
Apart from SLAs, organizations typically define operational key performance in-
dicators (KPIs) to monitor an organization’s performance and its way of working.
Processing time of transactions (i.e., the actual amount of time spent in processing
a transaction), resource utilization and productivity are a few examples of KPIs [1].
Client-level SLAs are often translated into some operational KPIs to keep a close track
on an organization’s performance. For example, turnaround time of each transaction is
broken down into expected processing times (referred to as baselines) for individual ac-
tivities/tasks involved in the execution of the transaction. Once baselines are defined for
each task, the organization can keep track of the number of baseline violations and the
magnitude by which these baselines are violated3 and take corrective actions (if need
be) before it percolates to a SLA violation (in terms of turnaround time).
Task allocation is one of the key planning exercises that plays a significant role in
an organization’s quest to meet SLAs and to achieve operational excellence. Employees
within an organization assume roles based on their skills, proficiency, and experience.
Since the execution of tasks requires specific skills, tasks need to be assigned to em-
ployees (referred to as resources) with appropriate skills/proficiency. Two resources
possessing same skills but having different proficiencies in those skills may take dif-
ferent times to process a task. In spite of all these intricacies, most SDOs still resort to
manual allocation of tasks.
Such a manual allocation in SDOs is generally done by a team lead. A team lead
handles the incoming volume of transactions and depending on the type of transaction
and the tasks that need to be executed to process it, manually allocates the tasks to re-
sources that she manages. While doing so, the team lead needs to consider a multitude
of factors such as task complexity, skill requirements, baseline processing times and re-
source skills/proficiency, workload, utilization, fairness, etc. All of these factors need to
be mentally processed making the problem of task allocation extremely challenging for
the team leads and making it almost impossible to keep in check the above mentioned
factors and thereby has a higher risk of impacting the KPIs and SLAs. Manual task
allocation further imposes a danger of inherent biases that team leads may adopt. Such
biases will impact resources, whose incentive payouts are dependent on the tasks that
they process and their productivity. These factors warrant for the design of efficient and
automated task allocation schemes for SDOs to achieve operational excellence via fair
task allocation, by better utilizing the resources, improving their productivity, reducing
the costs and improving the operational KPIs thereby meeting the SLAs.
Problem Description. In this paper, we address the problem of efficiently allocat-
ing tasks to resources in a service delivery organisation with the objective of allocating
tasks in a real time environment. We try to get final allocations within certain optimality
gap. We also consider several other constraints like the number of baseline violations
is within a specified limit (KPI/SLA-aware), assigned workload is fair among the re-
sources, utilization of each resource should be within the specified lower and upper
bounds to ensure that all the resources are well utilized (utilization-aware) and, produc-
tivity of each resource is within a specified upper limit as described in [1].
3
Typically, SLAs are defined such that the penalty for violations vary based on the magnitude
of violation.
Efficient Task Allocation
Contributions of this work. The main contribution of this paper is: Although [1]
has provided an ILP based solution for the problem, ILP based solution takes much
more time as the number of resources and number of tasks increases. For example, the
ILP based approach doesn’t provide any feasible solution (within 2 hours) even for a
scenario where we have 22 resources and 2000 tasks. As service delivery organisations
need the allocation matrix for the resources in (near-)real time, ILP based solution can-
not be deployed in practice. Therefore, we propose a meta-heuristic based approach in
this paper. It involves two steps:
1. We convert the problem to meta-heuristic based problem in which tabu search al-
gorithms have been proven to be effective and fast.
2. We propose a tabu-search (TS) based algorithm.
In our evaluations, the proposed approach is able to reduce the number of violations
by 20% and the magnitude of violations by up to 75%, furthermore it increases the pro-
ductivity of resources by 10% and average utilization and workload has been reduced
by 35% compared to the currently practiced manual task allocation in the organization.
Organization of the paper. This paper is organized as follows. Section 3 presents
the notations and the system model. Our task allocation approach based on Tabu search
is presented in Section 4. Section 6 presents the experimental setup and discusses the
efficacy of the proposed solution when applied to real-world data from a large SDO.
Finally, Section 7 concludes the paper.
2 Related work
Task allocation problem is well studied in the past [2–9] with a focus on assigning tasks
to machines (non-human resources). These works can not be applied to the problem
under consideration since they cannot handle some of the human related aspects such
as productivity and utilization of employees.
Some of the other works [10–14] have specifically looked into the problem of al-
location of tasks to employees. [11] studied the problem of assigning employees to
shifts based on the estimate of the skills required for the jobs in those shifts. [10] dis-
cuss a class of personnel task scheduling problems (that arise in rostering applications),
mostly related to scheduling of employees in different shifts and assigning different
tasks to a set of shifts. [12] propose a hybrid-heuristic approach in which the objec-
tive is to assign the tasks such that minimum number of resources are used, a problem
clearly different from ours. The approach considers skills of employees and the demand
while recommending the reallocation. The allocation is done considering the availabil-
ity of employees, skills of employees and skills required to perform a task and start and
end date for the task. Some of the other works [13, 14] study the problem with fairness
objective while ensuring the regulatory requirements. These works do not consider the
effect of allocation on operational KPIs and also the key human factors such as employ-
ees productivity and utilization. Thus, none of these works can be directly applied to
the problem under consideration in this work.
Several mechanisms have been proposed in [15–20] which perform allocation of
task to employees that are skill- and fairness-aware. Many of these techniques [15–18]
Rahul Paul, R. P. Jagadeesh Chandra Bose, Stephan K. Chalup, Raravi Gurulingesh
are not utilization, productivity- and SLA-aware (e.g., minimizing the number and mag-
nitude of baseline time violations). In [19], an engine configured to determine an assign-
ment of a resource to a task considering the task and the resource profile is proposed.
It takes into account the resource utilization. However, it is not productivity-aware and
since there is no deadline for tasks, its objective is different than ours. In [20], a con-
straint programming based allocation technique is proposed. It does skill based alloca-
tion and also considers fairness and tries to minimize the cost. However, the allocation
strategy is not productivity-aware, utilization-aware and does not focus on minimizing
the deadline violations.
3 System model
We consider the problem of allocating a set Π = {π1 , π2 , . . ., πn } of n tasks to a set
R = {r1 , r2 , . . . , rm } of m employees (referred to as resources) in a services delivery
setting. Each task πj is characterized by a processing time and a baseline time bj (also
referred to as deadline). The processing time of a task depends on the resource that
processes it and the processing time of πj when processed by ri is denoted by tij ,
where j ∈ {1, 2, . . . , n} and i ∈ {1, 2, . . . , m}. A task πj that cannot be processed by
a resource ri (e.g., if the resource does not have the skills to process it) is modeled by
setting tij to ∞. Ideally, processing of each task πj has to be completed within bj time
units.
For each resource πi , we define the following terms. The workload wi of πi is
defined as:
def
X
wi = tij (1)
πj ∈Π(i)
where Π(i) is the set of tasks assigned to ri . Informally, it is the sum of the processing
times that the resource takes for each task (tij ) that is assigned to it. The utilization ui
of πi is defined as:
def wi
ui = (2)
s
where s is the duration of the shift in which πi works. Informally, utilization of a re-
source indicates the fraction of time the resource will be occupied with the assigned
tasks in a shift. The productivity pi of πi is defined as:
P
def π ∈Π(i) bj
pi = P j (3)
πj ∈Π(i) tij
Informally, it is the ratio of the amount of expected time in which πi needs to complete
all the tasks assigned to her to the amount of actual time in which πi will complete
those tasks.
We also use a few other below mentioned notations in the paper. Upper limit on
the productivity of any resource is denoted by p̄ and upper limit on the number of
baseline violations is denoted by v̄. The lower and upper bounds on the utilization of
any resource is denoted by u and ū, respectively. (Bar is used over a letter to denote the
upper bound and underbar is used to denote the lower bound.) The average workload
Efficient Task Allocation
1
Pm
w̃ is defined as: w̃ = m i=1 wi . The lower and upper bounds on the workload of a
resource are (1 − w̄) × w̃ and (1 + w̄) × w̃, respectively.
4 Tabu Search
Tabu search is generally implemented as a single search trajectory direct search method.
The concept was originally proposed by Glover [21] and since than this research tech-
nique has been used in many applications. Tabu search has been applied to discrete
combinatorial optimization problems such as graph coloring and Travelling Salesman.
Tabu search is initiated at a feasible starting point within a solution. After that, it iden-
tifies sequences of moves and whilst that process is executed, a candidate list is gener-
ated. Evaluation process can determine whether the member belongs to the list or not.
Tabu search has three main advantages [21] : (1) the use of flexible attribute based de-
sign to permit better evaluation criteria and historical search information to exploit the
problem more thoroughly; (2) an associated mechanism of control based on the inter-
play between conditions that constrain and free the search process; (3) Intensification
strategies reinforce move combinations and solution features historically found good.
We use the tabu search approach to refine the solution obtained by using the given
heuristic algorithm. Although a tabu search based algorithm is proposed in [22] for the
Orienteering problem, our algorithm is different from it. Our algorithm works for the
resource allocation matrix with the score of each resource, which is different from the
graph discussed in [22]. In [23] TS-based algorithm is used for wireless relay network
where they simplified the problem as orienteering problem. Then they apply TS algo-
rithm to get best path from the current with a penalty funtion of budget and cost of path.
Furthermore, our algorithm only cares about the last assignment for each resource in
the allocation matrix. Thus, the proposed algorithm is more suitable for our problem.
5 Tabu search based task allocation
According to tabu search we need a first solution to start with. In our method, we have
started with the allocation given from the savings of the resources. Saving of a resource
can be calculated by :
savingsi = bj − tij (4)
where bj is the baseline of the task and tij is the timeline of task j assigned to resource
i. This tij has been taken from random distribution of same task perform by various re-
sources. We calculate the savings of resources and which ever resource has the largest
saving and the resource which can able to handle same type of work, we allocate the
task to that resource in the first step. But, if the savings of all the resources are nega-
tive i.e. tij ≥ bj , we assign the task to the resource which has less negative savings.
Then we check for the performance for the initial allocation. We calculate the utiliza-
tion, productivity, workload and number of violation from the allocation matrix X. The
calculation of these vectors has been discussed in the equations (1), (2), and (3). After
that we make a list of all violated tasks to perform our TS-based algorithm.
Rahul Paul, R. P. Jagadeesh Chandra Bose, Stephan K. Chalup, Raravi Gurulingesh
Algorithm 1 Tabu
1: function TABU(R, Π, t, b, s) . Where R - Resource array, Π - Set of Task, t - Timeline
matrix, b - Baseline matrix, s - Shift time . i - Resource index, j - Task index, X - Allocation
matrix
2: Initialize X
3: Call P ERFORMANCE E VAL(X, t, b)
4: do
5: if Xij == 1 and tij > bj then
6: V task.append(j)
7: end if
8: for each j in V task do
9: for each i in R do
10: if tij 6= −1 then
11: if Ui ≤ ū and Pi ≤ p̄ and Wi ≤ w̄ then
12: T abu listj .append(i)
13: end if
14: end if
15: end for
16: end for
17: X, allocation update from TABU S EARCH(T abu list, X, t, b)
18: while allocation update 6= 0
19: return X
20: end function
To validate or make the allocation close to the optimal solution we work with only
violated tasks in our TS-based algorithm. Take each violated task from the first alloca-
tion X and create a candidate list of resources which can do that task. Before adding
the resource to the candidate list we need to check the current utilization, productiv-
ity and workload of the resource. The current values of these metrics should be less
than ū, p̄, w̄ which are user driven input to the system. Then only the resource will
be added to the current set of resources to perform the violated task. Then we call the
tabu search algorithm with the tabu list and current allocation X. Before going into the
Tabusearch algorithm we need to evaluate a score to choose the best candidate from the
T abu list. A score can be evaluated by the summation of workload and productivity
with the penalty of the solution, i.e.,
scorei = (norm(pi ) + norm(wi )) + peni (5)
where peni is the penalty associated with the solution, and it is given by
(
0, if bj ≤ ri
peni = (6)
φ ∗ (ri − bj ), if bj > ri
Where ri is the remaining time of the resource from its shift. And φ is a penalty param-
eter dynamically updated during the search. The parameter φ is initialized at a value of
1. But the algorithm is robust with respect to this parameter.
Now, we call the TS algorithm with the Tabu list. First we generate the score for
each resources which are present in the tabu list for particular task. Then we select the
Efficient Task Allocation
Algorithm 2 Tabu Search
1: function TABU S EARCH(T abu list, X, t, b) . Where T abu list - Set of candidate list, X -
Allocation matrix . i - Resource index, j - Task index, scorei - score of resource from Eq. 5
2: allocation update = 0
3: for iteration = 1 to maxi terations do
4: tabu update ← 0
5: φ←1
6: for each j in T abu list do
7: X0 ← X
8: select inew ∈ T abu list[j] with the best scoreinew − scoreicur
9: X0icur j ← 0
10: X0inew j ← 1
11: Call P ERFORMANCE E VAL(X0 , t, b)
12: Call P ERFORMANCE E VAL(X, t, b)
13: if magV 0 ≤ magV then
14: X ← X0
15: φ ← φ/2
16: allocation update ← 1
17: tabu update ← 1
18: end if
19: end for
20: if tabu update == 0 then
21: φ←φ∗2
22: end if
23: end for
24: return X, allocation update
25: end function
best resource for the task and assign the task to that perticular resource. We fix the tabu
list elements, which are obtained from the previous function and will be updated in the
score function if assignment is being done. We update the X with new selected assign-
ment. Then again we call the PerformanceEval function to check the obtain solution
(Magnitude of violation) is better or not. If yes, we keep the updated assignment and
update the W, P, U . Other wise we go to the next violated task. After we loop through
all the task which are there in the violated task list, if we get any updated element in
X, we repeat the whole experiment and try to improve our result iteratively. Thus, we
approach for the optimal solution.
6 Experimental Results and Discussion
The proposed task allocation mechanism has been implemented, and in this section, we
discuss the results of applying our approach on real-world data from a transaction pro-
cessing business unit within a large SDO. The resources in the organization are skilled
on processes. Different resources are skilled to execute different processes and the pro-
ficiency levels of resources for the skills can vary. Each team lead is responsible for
handling transactions (of various types) pertaining to certain processes. The team lead
Rahul Paul, R. P. Jagadeesh Chandra Bose, Stephan K. Chalup, Raravi Gurulingesh
monitors the volume of transactions arriving every day (that he/she is expected to han-
dle) and allocates them to resources in his/her team based on their skills/proficiency
and the complexity of the transactions. The team lead manages all these mentally day-
in and day-out. Each transaction type comes with a baseline (unit of time) within which
transaction instances of that type is expected to be completed. Any transaction extend-
ing beyond the baseline is considered to be violating the baseline KPI. We keep track
of this KPI via the number of violations metric, which measure the number of trans-
actions that violated the baseline. We also keep track of the magnitude of violation,
the magnitude of time by which the baseline is violated. For example, if the baseline
of a transaction type is 100 time units and if an instance of that transaction type took
125 time units, then the magnitude of violation is 25 time units. It is important to keep
track of this because the penalty that the organization needs to pay also depends on the
magnitude of violation.
We have applied the proposed approach on the transactions handled by several team
leads to assess the efficacy of our approach. We present the results on the transactions
handled by four team leads, TL1 , TL2 , TL3 , and TL4 for a period of six months, Jan-
uary to June 2016. In order to study the efficacy of our approach, we need to estimate
the likely number of violations and the magnitude of violations if the transactions are
assigned to resources. To enable this, we extracted the historical processing time distri-
butions for each of the employees for the various transaction types. For any transaction
assigned to a resource, we randomly sample4 the time from that resources’ processing
time distribution for the transaction type (pertaining to that transaction). Before taking
randomly sampled processing time from the distribution, we also discard the outliers
values. That means we discard the processing times which are much less than that of
the baseline (e.g., 25% of baseline). We are doing this because these outlier values can
affect the productivity and utilization from the standard values. Assuming that the re-
source would take the sampled time had he/she been assigned that transaction, we check
if that time exceeds the baseline. If so, we record that as a violation and capture the mag-
nitude by which it exceeds the baseline. For each transaction, we do this assignment five
times and take the average metrics along with their confidence intervals.
The initial assignment for tabu search is done using a simple heuristic. For each
transaction from Π, check and assign the transaction to that resource who has the largest
saving for that transaction where saving is defined by :
savingsij = bj − tij (7)
Here bj signifies the baseline time for the transaction and tij denotes the sampled time
for that transaction for resource i. If all the resources have negative savings for a partic-
ular task we assign the task to the least negative savings. The initial allocation matrix
X, obtained thus, is then subjected for tabu search as explained in Section 4.
Table 1 presents the characteristics of the transactions handled by different team
leads and compares the current manual approach w.r.t. our proposed automated task
allocation. We can see that the current approach leads to significant number of violations
4
Other sampling mechanisms such as weighted sampling, where more weights to sampling
processing times from the recent past is applied. A detailed analysis and discussion of different
sampling mechanisms is beyond the scope of this paper.
Efficient Task Allocation
for the team leads, the percentage of violations being in the range of 14% to 46%.
Using our proposed tabu allocation, the deadline violations are in the range between
2% and 24%. On average, the number of violations is improved by 60% across all the
team leads. Fig. 1 depicts the comparison of the proposed approach w.r.t. the current
approach. Fig. 1(a) depicts the percentage of violations for the current approach (dotted
lines) for the four team leads and the average percentage of violations along with the
95% confidence intervals (over five runs) for the proposed tabu-based allocation (solid
lines). Similarly Fig. 1(b) and Fig. 1(c) depict the average utilization and productivity
for the current approach (dotted lines) and the average utilization and productivity along
with the 95% confidence intervals (over five runs) for the tabu-based allocation (solid
lines) respectively. As we can see our approach outperforms the current approach. The
percentage of violations is consistently much smaller than the current approach. Also,
the utilization of resources is smaller than that of the current approach. In other words,
due to the new allocation, the current resources are able to finish the tasks much earlier.
These resources can be better utilized by assigning them other tasks or reallocating
them to other groups. Furthermore, the productivity of resources is higher than that of
the current approach.
60 1
TL1 TL1 3
TL2 TL2 TL1
50 TL3 TL3 TL2
TL4 0.8 TL4 2.5 TL3
Average Utilization
TL4
Average Utilization
% of Violation
40
0.6 2
30
1.5
0.4
20 1
0.2
10 0.5
0 0 0
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
Month Month Month
(a) percentage of violation (b) utilization (c) productivity
Fig. 1. Comparison of percentage of violations, average utilization and productivity metrics for
the four team leads for both the current approach and the proposed tabu-based approach. Solid
line in the figures correspond to the tabu-based approach while the dotted line represents the
current method.
In our evaluations, the proposed approach is able to reduce the number of viola-
tions by 20% and the magnitude of violations by up to 75%, furthermore it increases
the productivity of resources by 10% and the average workload and utilization has been
reduced by 35% compared to the currently practiced manual task allocation in the or-
ganization.
Our proposed approach is computationally tractable with running times of less than
3 minutes. Fig 2 shows the comparison of time taken in ILP and our approach for one
team lead TL1 with one month data. Each day team lead encounters different number
of transaction. For example, from graph (Fig. 2) shows that on 22nd day we have 24
resources with 200 transaction, our tabu-search approach takes only 6.5 seconds with
98% confidence interval in percentage in violation. Another example, for a team lead
which has 1006 tasks in his pool and 20 resources. According to Fig. 2, ILP takes more
Rahul Paul, R. P. Jagadeesh Chandra Bose, Stephan K. Chalup, Raravi Gurulingesh
Table 1. Comparison of the number of violations and their magnitudes for the transactions han-
dled by four team leads of a large service organization for the duration of six months in the year
2016, where tabu based allocation gives us less violation than the current aloocation.
Current allocation Tabu-based allocation
TL1 # Res. # Trans. Cum. Mag. Viol. Avg. Cum. Mag. Viol.
% Viol. Avg. Util. Avg. Prod. Avg. Util. Avg. Prod.
(in secs) % Viol. (in secs)
Jan 308 16.55 23154 12.79 114.72 10.00 11132 11.93 115.59
Feb 100 14.00 11253 11.94 114.73 5.00 3077 11.05 112.30
Mar 111 21.62 62229 18.00 108.34 16.21 11064 14.94 102.50
22
Apr 1620 19.38 140358 36.69 112.34 6.54 46075 32.19 124.70
May 2700 30.52 324849 36.17 106.14 15.11 134256 31.53 121.83
Jun 2346 27.32 234297 35.67 108.31 12.79 109459 31.30 121.80
TL2
Jan 5742 22.34 563531 46.35 127.21 3.03 79614 30.48 193.98
Feb 4782 28.37 572090 46.30 118.75 2.80 83481 28.36 186.89
Mar 6072 26.96 634317 53.54 114.03 2.81 120633 30.10 233.67
17
Apr 6647 27.26 732574 50.25 119.36 2.45 92278 28.78 207.77
May 6493 24.29 457616 44.01 131.65 10.08 121145 29.94 187.24
Jun 5164 23.99 424336 37.88 192.02 5.80 53523 24.27 209.18
TL3
Jan 3737 30.61 985369 53.54 115.17 13.28 429000 43.59 135.58
Feb 2888 35.53 854770 51.17 109.16 13.40 241739 39.45 140.03
Mar 2116 37.43 532662 39.69 109.27 17.72 245589 34.40 134.52
32
Apr 1825 33.60 607748 40.77 111.12 14.85 151599 32.68 133.90
May 1933 35.75 674532 35.75 111.61 24.21 355669 36.76 120.57
Jun 2198 35.21 935117 41.93 108.25 18.47 292266 33.69 150.83
TL4
Jan 1731 45.40 671828 37.68 95.29 20.92 226034 27.90 116.73
Feb 1824 36.51 548773 51.46 105.99 14.65 194856 40.20 165.33
Mar 1317 39.48 490642 42.75 140.01 14.27 146027 31.63 140.01
22
Apr 1488 43.88 470765 54.15 101.34 16.20 144945 39.97 128.46
May 2979 37.70 939586 50.31 91.58 19.40 342126 39.98 118.40
Jun 4560 42.40 793910 46.14 99.30 17.34 297356 34.98 129.12
than 1 hour to assign tasks to the resources but with our approach the assignment takes
less than 10 minutes. This proves our second claim of this paper.
7 Conclusions
In this paper, we studied the problem of automated allocation of tasks to human re-
sources in a service delivery organizational setting with a larger goal of improving the
operational key performance indicators. For this problem, we proposed a metaheuristic
based task allocation scheme which aims to minimize the number of tasks missing the
deadlines and to minimize the magnitude by which they are missed taking into consider-
ation the resource skills, utilization, productivity, fairness and KPIs while allocating the
tasks. In the experimental evaluations on transaction data of a large services organiza-
tion, the proposed approach reduced the number of deadline misses and the magnitude
of violations by 75%. As future work, we intend to design an algorithm that dynami-
cally reallocates tasks periodically by closely monitoring the realtime performance of
Efficient Task Allocation
2500
Time in Tabu
Average Run time (Seconds)
Time in ILP
2000
1500
1000
500
0
5 10 15 20 25
Days
(a) running time comparison
Fig. 2. Comparison of time taken for ILP and the proposed tabu-search approach.
resources. Also, we can use various sampling strategies selecting the processing times
for a particular task instead of a random distribution.
8 Acknowledgement
The first author was supported by a UNRSC50:50 PhD scholarship at the University of
Newcastle, Australia.
References
1. A. Mulla, G. Raravi, T. Rajasubramaniam, R. P. J. C. Bose, and K. Dasgupta. Efficient task
allocation in services delivery organizations. In 2016 IEEE International Conference on
Services Computing (SCC), pages 555–562, June 2016.
2. Camille C Price. Task allocation in distributed systems: A survey of practical strategies. In
Proceedings of the ACM’82 conference, pages 176–181. ACM, 1982.
3. Ronald L Graham, Eugene L Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. Opti-
mization and approximation in deterministic sequencing and scheduling: a survey. Annals of
discrete mathematics, 5:287–326, 1979.
4. Ethel Mokotoff. Parallel machine scheduling problems: a survey. Asia-Pacific Journal of
Operational Research, 18(2):193, 2001.
5. Eugene L Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. Recent developments in deter-
ministic sequencing and scheduling: a survey. In A. H. G. Rinnooy Kan M. A. H. Dempster,
J. K. Lenstra, editor, Deterministic and stochastic scheduling, pages 35–73. Springer, 1982.
6. Edward G Coffman Jr, Michael R Garey, and David S Johnson. Approximation algorithms
for bin-packingan updated survey. In Algorithm design for computer system design, pages
49–106. Springer, 1984.
7. TCE Cheng and CCS Sin. A state-of-the-art review of parallel-machine scheduling research.
European Journal of Operational Research, 47(3):271–292, 1990.
8. Kathryn A Dowsland and William B Dowsland. Packing problems. European Journal of
Operational Research, 56(1):2–14, 1992.
Rahul Paul, R. P. Jagadeesh Chandra Bose, Stephan K. Chalup, Raravi Gurulingesh
9. Andreas Wiese, Vincenzo Bonifaci, and Sanjoy Baruah. Partitioned edf scheduling on a few
types of unrelated multiprocessors. Real-Time Systems, 49(2):219–238, 2013.
10. Mohan Krishnamoorthy and Andreas T Ernst. The personnel task scheduling problem. In
Optimization methods and applications, pages 343–368. Springer, 2001.
11. Andreas T Ernst, Houyuan Jiang, Mohan Krishnamoorthy, and David Sier. Staff scheduling
and rostering: A review of applications, methods and models. European journal of opera-
tional research, 153(1):3–27, 2004.
12. Pieter Smet, Tony Wauters, and Greet Vanden Berghe. Hardness analysis and a new approach
for the shift minimisation personnel task scheduling problem. In Evolutionary Computation,
2002. CEC’02. Proceedings of the 2002 Congress on, volume 1. the 27th Annual Conference
of the Belgian Operations Research Society (ORBEL), 2013.
13. Tanguy Lapègue, Odile Bellenguez-Morineau, and Damien Prot. Methods for the shift de-
sign and personnel task scheduling problem. In MOSIM 2014, 10ème Conférence Franco-
phone de Modélisation, Optimisation et Simulation, 2014.
14. Damien Prot, Tanguy Lapegue, and Odile Bellenguez-Morineau. A two-phase method for
the shift design and personnel task scheduling problem with equity objective. International
Journal of Production Research, 0:1–13, 2015.
15. Timothy Su. Four-dimensional resource allocation system, October 7 2002. US Patent App.
10/065,341.
16. G Edward Powell, Mark T Lane, and Runar Indseth. Method and system for allocating
personnel and resources to efficiently complete diverse work assignments, April 19 1999.
US Patent App. 09/294,251.
17. Debasis Mitra, John A Morrison, and Kajamalai Gopalaswamy Ramakrishnan. Method for
resource allocation and routing in multi-service virtual private networks, December 18 2001.
US Patent 6,331,986.
18. Randall K Fields, Paul R Quinn, and Todd Blackley. System and method for making staff
schedules as a function of available resources as well as employee skill level, availability and
priority, May 5 1992. US Patent 5,111,391.
19. Brian Fletcher, Robert Noel William Laithwaite, Evgeny Selensky, and Paul Sexton. Opti-
mizing resource assignment, October 30 2012. US Patent App. 13/664,338.
20. Youssef Hamadi and Claude-Guy Quimper. Allocating resources to tasks in workflows,
January 30 2007. US Patent App. 11/669,098.
21. Fred Glover. Tabu search: A tutorial. Interfaces, 20(4):74–94, 1990.
22. Yun-Chia Liang, Sadan Kulturel-Konak, and Alice E Smith. Meta heuristics for the ori-
enteering problem. In Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002
Congress on, volume 1, pages 384–389. IEEE, 2002.
23. Hao Zhou, Yusheng Ji, and Baohua Zhao. Tabu-search-based metaheuristic resource-
allocation algorithm for svc multicast over wireless relay networks. IEEE Transactions on
Vehicular Technology, 64(1):236–247, 2015.