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 combination of task deadlines and associated SLA requirements adds another dimension to the complexity of the problem. In this paper, we propose a tabu search algorithm for efficient task allocation. The algorithm is employee utilization, productivity and fairness aware. We evaluate the proposed algorithm using real world transaction processing data from a large service delivery organization. The results show that the proposed approach can reduce deadline misses substantially in comparison to the organization's current approach.
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.
Furthermore, 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).
Apart from SLAs, organizations typically define operational key performance
indicators (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 [
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 employees (referred to as resources) with appropriate skills/proficiency. Two resources possessing same skills but having different proficiencies in those skills may take different 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 resources 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 resource 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
allocating 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
resources, 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,
productivity of each resource is within a specified upper limit as described in [
Contributions of this work. The main contribution of this paper is: Although [
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 productivity 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
Task allocation problem is well studied in the past [
Some of the other works [
Several mechanisms have been proposed in [
We consider the problem of allocating a set = f 1, 2, : : :, ng of n tasks to a set R = fr1; r2; : : : ; rmg 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 2 f1; 2; : : : ; ng and i 2 f1; 2; : : : ; mg. 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 1. 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: wi d=ef
X j2 (i)
tij ui d=ef wi
s pi d=ef
P P j2 (i) bj j2 (i) tij 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: where s is the duration of the shift in which i works. Informally, utilization of a resource 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: (1) (2) (3) 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 u, respectively. (Bar is used over a letter to denote the upper bound and underbar is used to denote the lower bound.) The average workload w~ is defined as: w~ = m1 Pm
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 is generally implemented as a single search trajectory direct search method.
The concept was originally proposed by Glover [
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 [
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 resources. 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 negative 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 utilization, 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.
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
Initialize X Call PERFORMANCEEVAL(X; t; b) do
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 allocation 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, productivity and workload of the resource. The current values of these metrics should be less than u, 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 where peni is the penalty associated with the solution, and it is given by peni = (0; if bj
ri (ri bj ); if bj > ri (5) (6) Where ri is the remaining time of the resource from its shift. And is a penalty parameter 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 1: function TABUSEARCH(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 allocation update = 0 for iteration = 1 to maxiterations do tabu update 0
1 for each j in T abu list do
X0 X select inew 2 T abu list[j] with the best scoreinew scoreicur Algorithm 2 Tabu Search X0icurj 0 X0inewj 1 Call PERFORMANCEEVAL(X0; t; b) Call PERFORMANCEEVAL(X; t; b) if magV 0 magV then
X
1 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 assignment. 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
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 processing 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 proficiency 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 monitors the volume of transactions arriving every day (that he/she is expected to handle) 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 dayin 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 extending 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 transactions 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, January 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 distributions 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 resource 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 magnitude 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 particular 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. 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.
TL1 TL2 TL3 TL4 1 0.8 n o it iza0.6 lit U ge0.4 a r e v A0.2
TL1 TL2 TL3 TL4 3 2.5 itano 2 z ilitU1.5 e g a re 1 v A 0.5
TL1 TL2 TL3 TL4 0 1 2 3 Mon4th 5 6 7 (a) percentage of violation 0 1 2 3 Mon4th 5 6 7 (b) utilization 0 1 2 3 Mon4th 5 6 7 (c) productivity
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 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 organization.
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 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.
(in secs)
% Viol. (in secs) Jan Feb Mar Apr May Jun TL2 Jan Feb Mar Apr May Jun TL3 Jan Feb Mar Apr May Jun TL4 Jan Feb Mar Apr May Jun 22 17 32 22 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
In this paper, we studied the problem of automated allocation of tasks to human resources 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 consideration the resource skills, utilization, productivity, fairness and KPIs while allocating the tasks. In the experimental evaluations on transaction data of a large services organization, 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 dynamically reallocates tasks periodically by closely monitoring the realtime performance of Time in Tabu
Time in ILP 5 10
15 Days 20
25 (a) running time comparison resources. Also, we can use various sampling strategies selecting the processing times for a particular task instead of a random distribution. 8
The first author was supported by a UNRSC50:50 PhD scholarship at the University of Newcastle, Australia.