Queue Waiting Time Aware Dynamic Workflow Scheduling in Multicluster Environments

Workflows are prevailing in scientific computation. Multicluster environments emerge and provide more resources, benefiting workflows but also challenging the traditional workflow scheduling heuristics. In a multicluster environment, each cluster has its own independent workload management system. Jobs are queued up before getting executed, they experience different resource availability and wait time if dispatched to different clusters. However, existing scheduling heuristics neither consider the queue wait time nor balance the performance gain with data movement cost. The proposed algorithm leverages the advancement of queue wait time prediction techniques and empirically studies if the tunability of resource requirements helps scheduling. The extensive experiment with both real workload traces and test bench shows that the queue wait time aware algorithm improves workflow performance by 3 to 10 times in terms of average makespan with relatively very low cost of data movement.     

Mapping workflow applications with types on heterogeneous specialized platforms

In this paper, we study the problem of optimizing the throughput of coarse-grain workflow applications, for which each task of the workflow is of a given type, and subject to failures. The goal is to map such an application onto a heterogeneous specialized platform, which consists of a set of processors that can be specialized to process one type of tasks. The objective function is to maximize the throughput of the workflow, i.e., the rate at which the data sets can enter the system. If there is exactly one task per processor in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same processor. Several polynomial time heuristics are presented for the most realistic specialized setting, in which tasks of the same type can be mapped onto the same processor, but a processor cannot process two tasks of different types. Also, we give an integer linear program formulation of this problem, which allows us to find the optimal solution (in exponential time) for small problem instances. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed (small problem instances or particular mappings).     

基于时序一致的工作流费用优化方法

针对效用网格下的工作流时间约束-费用优化问题,分层算法将工作流进行分层并逐层进行优化调度,取得了良好效果.然而,这类分层算法由于缺乏更有效的截止时间确定策略来保证时间约束而使得算法的适用性受限.在已有算法截止期约束的逆向分层算法(deadline bottom level,DBL)的基础上,研究工作流的时序特征,并基于任务的一致性状态对费用进行优化,提出了基于时序一致的截止期约束逆向分层算法(temporal consistency based deadline bottom level,TCDBL).TCDBL通过一致性时间点来保证时间约束,解决了DBL的适用性受限问题;同时基于各层并行度分配冗余时间,基于宽松时间约束策略进行费用优化,达到了进一步减少工作流执行费用的目标.实验结果表明TCDBL的费用优化效果比DBL改进了约14%.     

网格工作流调度算法研究综述*

作为一个NP完全问题,通常采用启发式算法来解决网格工作流调度。首先对网格工作流调度算法进 行了分类,然后对其典型算法进行了分析和讨论,并阐述了一些典型网格工作流调度系统,最后指出了现有算法 中的一些不足之处,展望了该领域的进一步研究方向。     

Overhead Analysis of Scientific Workflows in Grid Environments

Scientific workflows are a topic of great interest in the grid community that sees in the workflow model an attractive paradigm for programming distributed wide-area grid infrastructures. Traditionally, the grid workflow execution is approached as a pure best effort scheduling problem that maps the activities onto the grid processors based on appropriate optimization or local matchmaking heuristics such that the overall execution time is minimized. Even though such heuristics often deliver effective results, the execution in dynamic and unpredictable grid environments is prone to severe performance losses that must be understood for minimizing the completion time or for the efficient use of high-performance resources. In this paper, we propose a new systematic approach to help the scientists and middleware developers understand the most severe sources of performance losses that occur when executing scientific workflows in dynamic grid environments. We introduce an ideal model for the lowest execution time that can be achieved by a workflow and explain the difference to the real measured grid execution time based on a hierarchy of performance overheads for grid computing. We describe how to systematically measure and compute the overheads from individual activities to larger workflow regions and adjust well-known parallel processing metrics to the scope of grid computing, including speedup and efficiency. We present a distributed online tool for computing and analyzing the performance overheads in real time based on event correlation techniques and introduce several performance contracts as quality-of-service parameters to be enforced during the workflow execution beyond traditional best effort practices. We illustrate our method through postmortem and online performance analysis of two real-world workflow applications executed in the Austrian grid environment.     

Rolling-horizon and fix-and-relax heuristics for the multi-product multi-level capacitated lotsizing problem with sequence-dependent setups

This paper discusses the multi-product multi-level capacitated lotsizing and scheduling problem with sequence-dependent setups. An exact formulation of the problem is provided as a mixed-integer program which is impractical to solve in reasonable computing time for non-small instances. To solve non-small instances of the problem, MIP-based heuristics are provided. To test the accuracy of heuristics, two lower bounds are developed and compared against the optimal solution. The trade-offs between schedule quality and computational time of heuristics are also provided.     

Application Layer Scheduling in Cloud: Fundamentals,Review and Research Directions

The cloud computing paradigm facilitates a finite pool of on-demand virtualized resources on a pay-per-use basis. For large-scale heterogeneous distributed systems like a cloud, scheduling is an essential component of resource management at the application layer as well as at the virtualization layer in order to deliver the optimal Quality of Services (QoS). The cloud scheduling, in general, is an NP-hard problem due to large solution space, thus, it is difficult to find an optimal solution within a reasonable time. In application layer scheduling, the tasks are mapped to logical resources (i.e., virtual machines), aiming to optimize one or more QoS parameters, and conforming to several constraints. Various algorithms have been proposed in the literature for application layer scheduling, where each of them is based on some fundamental design techniques like simple heuristics, meta-heuristics, and most recently hybrid heuristics. Although ample literature survey exists for cloud scheduling algorithms, none of them present their study exclusively for the application layer. In this survey paper, we present a study on task scheduling algorithms used only at the application layer of the cloud. We classify our study according to various fundamental techniques used in designing such scheduling algorithms. One of the main features of our study is that it covers numerous application type e.g., a set of independent tasks, simple workflow, scientific workflow, and MapReduce jobs. We also provide a comparative analysis of existing algorithms on various parameters like makespan, cost, resource utilization, etc. In the end, research directions for future work have been provided.     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

Modeling and heuristics for scheduling of distributed job shops

This paper deals with the problem of distributed job shop scheduling in which the classical single-facility job shop is extended to the multi-facility one. The mathematical formulation of the problem is comprehensively discussed. Two different mixed integer linear programming models in form of sequence and position based variables are proposed. Using commercial software of CPLEX, the small sized problems are optimally solved. To solve large sized problems, besides adapting three well-known heuristics, three greedy heuristics are developed. The basic idea behind the developed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The permutation scheme, although having several advantages, suffers from redundancy which is having many different permutations representing the same schedule. The issue is analyzed to recognize the redundant permutation. That improves efficiency of heuristics. Comprehensive experiments are conducted to evaluate the performance of the two models and the six heuristics. The results show sequence based model and greedy heuristics equipped with redundancy exclusion are effective for the problem.     

多目标最优化云工作流调度进化遗传算法

为了实现云环境中科学工作流调度的执行跨度和执行代价的同步优化,提出了一种多目标最优化进化遗传调度算法MOEGA。该算法以进化遗传为基础,定义了任务与虚拟机映射、虚拟机与主机部署间的编码机制,设计了满足多目标优化的适应度函数。同时,为了满足种群的多样性,在调度方案中引入了交叉与变异操作,并使用启发式方法进行种群初始化。通过4种现实科学工作流的仿真实验,将其与同类型算法进行了性能比较。结果表明,MOEGA算法不仅可以满足工作流截止时间约束,而且在降低任务执行跨度与执行代价的综合性能方面也优于其他算法。     

支持工作流动态变化的过程元模型

支持动态可变并具备灵活性是人们在实际应用中对工作流管理系统提出的新要求,已有的相关研究工作都集中在对工作流中发生变化的某个具体问题上.提出了支持动态特性的工作流过程元模型,可以为动态过程模型的设计提供指导.从时间和工作流组成的过程级别两个角度分析了其动态特性的表现,扩展了工作流管理联盟的工作流元模型.扩展后的过程元模型在工作流的建立阶段力求将动态特性进行描述和定义,在工作流执行阶段可以根据已定义的动态属性,处理过程的变化情况.基于该元模型,工作流管理系统既具有灵活性,又有利于变化控制操作.     

A location–inventory supply chain problem: Reformulation and piecewise linearization

In this paper, we study a two-echelon inventory management problem with multiple warehouses and retailers. The problem is a natural extension to the well-known one-warehouse multi-retailer inventory problem. The problem is formulated as a mixed integer non-linear program such that its continuous relaxation is non-convex. We propose an equivalent formulation with fewer non-linear terms in the objective function so that the continuous relaxation of the new model is a convex optimization problem. We use piecewise linearization to transform the resulting MINLP to a mixed integer program and we solve it using CPLEX. Through numerical experiments, we compare the solutions obtained by solving the new formulation using CPLEX with two previously published Lagrangian relaxation based heuristics to solve the original mixed integer non-linear program. We demonstrate that the new approach is capable of providing almost the same solutions without the need of using specialized algorithms. This important contribution further implies that additional variants of the problem, such as multiple products, capacitated warehouses and routing, can be added to result in a problem that will again be solvable by commercial optimization software, while the respective Lagrangian heuristics will fail to solve such variants or extended problems.     

基于路径平衡的工作流费用优化方法

针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(path balance,简称 PB)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(path balance based cost optimization,简称PBCO)算法。 PBCO 基于 PB 的计算结果设置初始约束时间,充分利用了工作流的费用优化空间。同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果。实验结果表明,PBCO比另外几种著名算法(如DET,DBL等)改进了约35%。     

水下机器人任务流程建模与管理

为实现水下机器人任务流程的快速建模与自动管理,通过改进传统的工作流理论,提出了一种实用的任务流程模型——任务工作流.介绍了作为任务工作流理论基础的传统Petri网及工作流模型,指出了原有理论的缺陷并介绍了任务工作流的基本理论.以任务工作流模型为基础,实现了一款任务流程管理系统,为其定义了完善的图形化建模手段与标准的文本化的描述语言,并建立了一套担负着运行时任务管理工作的核心应用程序,能够实现任务的描述与建模、自动运行与管理,以及任务流程的动态更改.实践表明,任务工作流建模简单快捷、方便编程实现,是机器人任务建模与管理的理想工具.     

基于Web Service的异构工作流管理系统的集成和互操作研究

本文首先分析了分布、异构工作流管理系统的互操作对各种交互模式的需求，针对 现有的工作流管理系统的分布式应用解决方案的不足之处，提出了一种基于Web Service的支持分布、异构工作流管理系统之间集成和互操作的实现方法．Web Service因其开放、标准化而受到业界广泛重视，已成为新一代基于Internet建立分布式应用的规范．本文从异构工作流管理系统之间的信息集成、工作流引擎之间调用语义的实现、工作流执行服务的描述、发布和绑定等方面，论述了Web Service对异构工作流管理系统之间集成和互操作的支持．     

ECA规则在工作流管理系统中的应用

针对工作流管理系统的实现复杂性及模型可靠性的验证问题，提出了一种结合工作流网和ECA规则来创建工作流管理系统的方法。这种基于ECA规则的工作流描述和执行机制较好地实现了工作流网模型的语义描述和控制的统一。通过建立基于ECA规则的工作流描述表，将ECA 规则引入到工作流路由机制中，灵活地控制了工作流的流程。通过事件触发和消息处理机制，工作流描述表处理可以被实际系统加以执行和控制。     

一种模型驱动的工作流过程定义途径

传统的工作流管理系统在互操作性,可复用性,可移植性和开发效率等方面遇到了挑战,MDA是解决上述挑战和问题的一种途径。在模型驱动的工作流管理系统中,工作流模型处于核心地位,本文首先给出了扩展的工作流元模型和基于Petri网的形式化工作流模型过程网。其次,运用模型驱动的途径,依据给出的工作流模型,本文提出了一种模型驱动的,用于快速构造工作流管理系统的框架。针对工作流过程模型,着重讨论了从基于EPC的过程CIM到基于过程网的过程PIM的转换（转换过程和转换规则）,并以扩展的Petri网标注语言E-PNML规约了过程PIM。     

一种基于同步网的工作流管理系统

作为一类典型的CSCW系统,工作流管理系统主要提供异步、结构化的协同支持。本文从模型入手,介绍了一种基于Petri网的工作流模型——同步网。它采用分层视图描述了过程逻辑、语义及管理,过程模型和管理模型的互动关系用来指导工作流引擎的构造。本文基于同步网开发了工作流管理系统,支持工作流的定义、执行和管理。为了满足CSCW的需要,工作流管理系统中增加了同步协作机制。     

A Conceptual Approach for Data Integration in Business Analytics

We present some basic concepts of a modelling environment for data integration in business analytics. Main emphasis is on defining a process model for the different activities occurring in connection with data integration, which allow later on assessment of the quality of the data. The model is based on combination of knowledge and techniques from statistical metadata management and from workflow processes. The modelling concepts are presented in a problem oriented formulation. The approach is embedded into an open model framework which aims for a modelling platform for all kinds of models useful in business applications.     

基于Shark的工作流日志迁移研究及其实现

工作流日志数据中可能记录着非常有价值的信息,它们对于流程优化和工作流挖掘具有重要意义.然而,传统工作流系统缺乏对工作流日志迁移的有效支持.基于对工作流日志数据的分析,提出了一种支持日志迁移的分布式工作流系统框架.该框架通过工作流实例数据与历史数据的分离,以实现工作流日志数据的分布式管理.基于开源工作流Shark,通过扩展WfMC相关接口,给出了该框架的实现方案.