基于协作相容性的工作流任务分配优化方法

发布时间：2018-05-25 20:52

本文选题：工作流 + 任务分配策略　；参考：《杭州电子科技大学》2016年硕士论文

【摘要】：近年来,随着计算机与通讯技术的快速发展,各企业更加注重使用高度集成的计算机软件来进行日常的生产及办公,从而提高工作的效率和降低成本。而工作流技术顺应了以过程为中心的管理模式的发展趋势,因而得到了国内外研究人员和产业界人士的广泛重视。工作流通过预定义的一些规则,使文档、信息或任务能够在不同的执行者之间传递、执行。工作流的任务分配策略是在工作流实例运行时,对其中待执行的任务分配具体的执行者,良好的任务分配策略能够提高工作流系统的性能,因此研究如何实现对工作流任务分配方法的优化,具有十分重要的现实意义。为了实现对工作流任务分配问题的优化,本文综合考虑工作流实例中任务候选执行者的能力,负载,任务间的交互性以及候选执行者间的协作相容性等要素,研究了一种基于协作相容性的、负载均衡式任务分配模型,以及在此基础上给出了基于协作相容性与负载均衡的任务分配算法,通过最大化全局交互任务执行者的协作相容性的措施,寻求在满足执行者负载相对均衡的同时,提高工作流的整体性能。本文具体工作如下:首先,文章根据对工作流任务分配问题的现有研究进行了分析,针对任务分配过程中可能存在的负载不均衡问题,进行了深入的研究,提出了假设任务以泊松过程分配执行者时两种负载均衡的任务分配模型。在此基础上,给出了两种负载均衡的任务分配算法和时间复杂度分析。其次,通过一个简单的医疗索赔流程的分析,引入了执行者间协作相容性对任务分配影响的内容。在此基础上,进一步考虑执行者当前的任务负载,提出了基于协作相容性的、负载均衡式任务分配模型,并给出了该模型算法的具体实现,用以提高整个流程实例的执行效率,并优化执行者间的负载均衡。为了对该算法的高效性进行分析,我们提出了一个单目标的任务分配算法,即最大化协作相容性算法。由于执行者之间的协作相容性涉及到个人的隐私,因此本文通过对历史日志中协作执行流程实例信息的挖掘,设计了一种计算执行者协作相容的公式,具有一定的合理性和适用性。最后,文章对所提出的几种任务分配算法分别进行了相应的实现和仿真实验,并将得到的各种实验的数据结果进行了比较详细的分析、对比等。同时说明本文最后所提出的基于协作相容性的负载均衡任务分配方法,相较于其他几种算法,在很大程度上减少了工作流实例的平均完成时间、平均处理时间以及执行者的负载均衡性,提高了工作流系统的整体性能。
[Abstract]:In recent years, with the rapid development of computer and communication technology, enterprises pay more attention to the use of highly integrated computer software for daily production and office, thereby improving the efficiency of work and reducing costs. Workflow technology conforms to the development trend of process-centered management model, so it has been widely paid attention to by researchers and industry people at home and abroad. Workflow allows documents, information, or tasks to be passed and executed between different executors through predefined rules. The task allocation strategy of workflow is to assign specific executors to the tasks to be executed while the workflow instance is running. A good task assignment strategy can improve the performance of workflow system. Therefore, it is of great practical significance to study how to optimize the task allocation method of workflow. In order to optimize the task assignment of workflow, this paper comprehensively considers the ability, load, interactivity among tasks and the compatibility of candidate executors in workflow instance. In this paper, a load balancing task allocation model based on collaboration compatibility is studied, and a task allocation algorithm based on collaboration compatibility and load balancing is presented. By maximizing the cooperative compatibility of the global interactive task executors, we seek to improve the overall performance of the workflow while satisfying the relative balance of the executor's load. The specific work of this paper is as follows: firstly, according to the existing research on workflow task allocation, the paper makes a deep research on the possible load imbalance in the task allocation process. Two load balancing task allocation models are proposed, which assume that the task is assigned to the executor by the Poisson process. On this basis, two load balancing task allocation algorithms and time complexity analysis are presented. Secondly, through the analysis of a simple medical claim process, the content of the effect of the cooperation compatibility between the executors on the task assignment is introduced. On the basis of this, considering the current task load of the executor, this paper proposes a cooperative compatible, load-balanced task allocation model, and gives the concrete implementation of the model algorithm to improve the execution efficiency of the whole process instance. And optimize the load balance between the executors. In order to analyze the efficiency of the algorithm, we propose a single objective task assignment algorithm, that is, maximization of coordination compatibility algorithm. Because the compatibility of cooperation between executors involves the privacy of individuals, this paper designs a formula to calculate the compatibility of cooperation between executors by mining the instance information of collaborative execution process in the history log. It has certain rationality and applicability. Finally, the paper carries on the corresponding realization and the simulation experiment to several kinds of task assignment algorithms proposed, and carries on the detailed analysis, the contrast and so on to the obtained each kind of experiment data result. At the end of this paper, the load balancing task allocation method based on collaboration compatibility is presented. Compared with other algorithms, it reduces the average completion time of workflow instance to a great extent. The average processing time and the load balance of the executor improve the overall performance of the workflow system.
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6

【引证文献】