Information Technology Reference
In-Depth Information
work team completing a process together. As a result, all the previous resources
may affect the candidate resources of the successive task. This is because the
candidate resources may need to refer back to the resources of the previous tasks.
There were many algorithms for task allocation. Such as the shortest work
list allocation, the shortest processing time allocation and the shortest complete
time allocation [4]. All these algorithms have some disadvantages such as load
imbalance [4]. Q-learning is a more effective algorithm for task allocation, the
reasons are as follow: first, task allocation is an interactive problem which can
be modeled as Markov Decision Processes (MDPs), and Q-learning is a rein-
forcement learning algorithm that canbeusedtosolvetheMDPsproblems;
second, Q-learning algorithm can choose the optimal action to achieve its goals
through learning without the knowledge of state's transfer function [5]; third,
the Q-learning algorithm can make resource's load balance.
In this paper, a method to compute the social relation between two resources
and a model to capture the influence of the previous resources when doing task
allocation are presented. The task allocation problem is modeled as a MDPs
problem, which is solved by Q-learning algorithm. A real world data set and a
simulateddatasetareusedintheexperiment. Using these data sets can prove
the idea better.
The paper is organized as follow: Section 2 introduces the related work about
task allocation and reinforcement learning algorithm; Section 3 gives concepts
and definitions proposed in this paper; Section 4 describes the MDPs model
of task allocation; Section 5 gives details of the Q-learning algorithm for task
allocation; Experiment and results are described in Section 6; Conclusions are
made in Section 7.
2 Related Work
2.1 Task Allocation
Task allocation in business process aims to choose the appropriate resources to
do certain tasks. Resource's behavior influences the performance of the workflow
management system, and many other factors affect the resources behavior at the
same time. Joyce Nakatumba and WilM.P.van der Aalst et al. used process min-
ing to explore the effect of workload on service time of every resource which is
known as ”Yerkes-Dodson Law of Arousal” [6]. They also presented an approach
based on regression analysis to quantify the relationship between workload and
processing speed. In [7], the author proposed a novel resource model of resources'
community, which was also used to accelerate the collaboration between various
resources. But the concept of teamwork wasn't used for dynamic task allocation.
The interest of resource on the task would be considered in [8], it is dicult to
measure this index exactly in reality. Yi Liu et al. presented a strategy for task
allocation which supported load-balancing of resources and considered experien-
tial value [9]. However, it is dicult to measure the experiential value precisely
in reality. Jiaxing Xu et al. presented social context which only considered the
handover relation [3].
