Granularity-based workflow scheduling algorithm for cloud computing

The workflow scheduling problem has drawn a lot of attention in the research community. This paper presents a workflow scheduling algorithm, called granularity score scheduling (GSS), which is based on the granularity of the tasks in a given workflow. The main objectives of GSS are to minimize the makespan and maximize the average virtual machine utilization. The algorithm consists of three phases, namely B-level calculation, score adjustment and task ranking and scheduling. We simulate the proposed algorithm using various benchmark scientific workflow applications, i.e., Cybershake, Epigenomic, Inspiral and Montage. The simulation results are compared with two well-known existing workflow scheduling algorithms, namely heterogeneous earliest finish time and performance effective task scheduling, which are also applied in cloud computing environment. Based on the simulation results, the proposed algorithm remarkably demonstrates its performance in terms of makespan and average virtual machine utilization.     

Coordinating patient preferences through automated negotiation: A multiagent systems model for diagnostic services scheduling

This paper presents a multiagent systems model for patient diagnostic services scheduling. We assume a decentralized environment in which patients are modeled as self-interested agents who behave strategically to advance their own benefits rather than the system wide performance. The objective is to improve the utilization of diagnostic imaging resources by coordinating patient individual preferences through automated negotiation. The negotiation process consists of two stages, namely patient selection and preference scheduling. The contract-net protocol and simulated annealing based meta-heuristics are used to design negotiation protocols at the two stages respectively. In terms of game theoretic properties, we show that the proposed protocols are individually rational and incentive compatible. The performance of the preference scheduling protocol is evaluated by a computational study. The average percentage gap analysis of various configurations of the protocol shows that the results obtained from the protocol are close to the optimal ones. In addition, we present the algorithmic properties of the preference scheduling protocol through the validation of a set of eight hypotheses.     

HEART: Unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta-heuristic algorithms

Cloud computing is becoming a profitable technology because of it offers cost-effective IT solutions globally. A well-designed task scheduling algorithm ensures the optimal utilization of clouds resources and reducing execution time dynamically. This research article deals with the task scheduling of inter-dependent subtasks on unrelated parallel computing machines in a cloud computing environment. This article considers two variants of the problem-based on two different objective function values. The first variant considers the minimization of the total completion time objective function while the second variant considers the minimization of the makespan objective function. Heuristic and meta-heuristic (HEART) based algorithms are proposed to solve the task scheduling problems. These algorithms utilize the property of list scheduling algorithm of unrelated parallel machine scheduling problem. A mixed integer linear programming (MILP) formulation has been provided for the two variants of the problem. The optimal solution is obtained by solving MILP formulation using A Mathematical Programming Language (AMPL) software. Extensive numerical experiments have been performed to evaluate the performance of proposed algorithms. The solutions obtained by the proposed algorithms are found to out-perform the existing algorithms. The proposed algorithms can be used by cloud computing service providers (CCSPs) for enhancing their resources utilization to reduce their operating cost.     

Runtime vs. Manual Data Distribution for Architecture-Agnostic Shared-Memory Programming Models

This paper compares data distribution methodologies for scaling the performance of OpenMP on NUMA architectures. We investigate the performance of automatic page placement algorithms implemented in the operating system, runtime algorithms based on dynamic page migration, runtime algorithms based on loop scheduling transformations and manual data distribution. These techniques present the programmer with trade-offs between performance and programming effort. Automatic page placement algorithms are transparent to the programmer, but may compromise memory access locality. Dynamic page migration algorithms are also transparent, but require careful engineering and tuned implementations to be effective. Manual data distribution requires substantial programming effort and architecture-specific extensions to the API, but may localize memory accesses in a nearly optimal manner. Loop scheduling transformations may or may not require intervention from the programmer, but conform better to an architecture-agnostic programming paradigm like OpenMP. We identify the conditions under which runtime data distribution algorithms can optimize memory access locality in OpenMP. We also present two novel runtime data distribution techniques, one based on memory access traces and another based on affinity scheduling of parallel loops. These techniques can be used to effectively replace manual data distribution in regular applications. The results provide a proof of concept that it is possible to scale a portable shared-memory programming model up to more than 100 processors, without modifying the API and without exposing architectural details to the programmer.     

Adaptable Scheduling Algorithm for Grids with Resource Redeployment Capability

Two distinct characteristics of grid computing systems are resource heterogeneity and availability variation. There are many well-designed scheduling algorithms proposed for heterogeneous computing systems. However, the availability variation is seldom considered in developing scheduling ongoing applications on a grid. In this paper, two scheduling algorithms called AMOF and AMOSF are proposed. Both of them consider availability variation as well as resource heterogeneity while scheduling an ongoing workflow application on the grid. An experiment has been conducted to demonstrate that AMOF and AMOSF algorithms outperform the well-known scheduling algorithms: GS and HEFT in most of the cases.     

A cost-aware auto-scaling approach using the workload prediction in service clouds

Service clouds are distributed infrastructures which deploys communication services in clouds. The scalability is an important characteristic of service clouds. With the scalability, the service cloud can offer on-demand computing power and storage capacities to different services. In order to achieve the scalability, we need to know when and how to scale virtual resources assigned to different services. In this paper, a novel service cloud architecture is presented, and a linear regression model is used to predict the workload. Based on this predicted workload, an auto-scaling mechanism is proposed to scale virtual resources at different resource levels in service clouds. The auto-scaling mechanism combines the real-time scaling and the pre-scaling. Finally experimental results are provided to demonstrate that our approach can satisfy the user Service Level Agreement (SLA) while keeping scaling costs low.     

Slack computation for DVS algorithms in fixed-priority real-time systems using fluid slack analysis

This work presents a scheduling algorithm to reduce the energy of hard real-time tasks with fixed priorities assigned in a rate-monotonic policy. Sets of independent tasks running periodically on a processor with dynamic voltage scaling (DVS) are considered as well. The proposed online approach can cooperate with many slack-time analysis methods based on low-power work demand analysis (lpWDA) without increasing the computational complexity of DVS algorithms. The proposed approach introduces a novel technique called low-power fluid slack analysis (lpFSA) that extends the analysis interval produced by its cooperative methods and computes the available slack in the extended interval. The lpFSA regards the additional slack as fluid and computes its length, such that it can be moved to the current job. Therefore, the proposed approach provides the cooperative methods with additional slack. Experimental results show that the proposed approach combined with lpWDA-based algorithms achieves more energy reductions than do the initial algorithms alone.     

Reliability-aware low energy scheduling in real time systems with shared resources

Dynamic voltage scaling (DVS) is a technique which is widely used to save energy in a real time system. Recent research shows that it has a negative impact on the system reliability. In this paper, we consider the problem of the system reliability and focus on a periodic task set that the task instance shares resources. Firstly, we present a static low power scheduling algorithm for periodic tasks with shared resources called SLPSR which ignores the system reliability. Secondly, we prove that the problem of the reliability-aware low power scheduling for periodic tasks with shared resources is NP-hard and present two heuristic algorithms called SPF and LPF respectively. Finally, we present a dynamic low power scheduling algorithm for periodic tasks with shared resources called DLPSR to reclaim the dynamic slack time to save energy while preserving the system reliability. Experimental results show that the presented algorithm can reduce the energy consumption while improving the system reliability.     

Online rescheduling of multiple picking agents for warehouse management

In this paper, we present a solution for a dynamic rescheduling problem involving new orders arriving randomly while static orders have been given in advance in warehouse environments. We propose two variations of an incremental static scheduling scheme: one based on the steepest descent insertion, called OR1, and the other, on multistage rescheduling, called OR2. Both techniques are enhanced by a local search procedure specifically designed for the problem at hand. We also implemented several existing online algorithms to our problem for evaluative purposes. Extensive statistical experiments based on real picking data indicate that the proposed methodologies are competitive with existing online schedulers and show that load-balancing algorithms, such as OR1, yield the best results on the average and that OR2 is effective in reducing the picking time when dynamism is low to moderate.     

Novel dynamic load balancing algorithm for cloud-based big data analytics

Big data analytics in cloud environments introduces challenges such as real-time load balancing besides security, privacy, and energy efficiency. This paper proposes a novel load balancing algorithm in cloud environments that performs resource allocation and task scheduling efficiently. The proposed load balancer reduces the execution response time in big data applications performed on clouds. Scheduling, in general, is an NP-hard problem. Our proposed algorithm provides solutions to reduce the search area that leads to reduced complexity of the load balancing. We recommend two mathematical optimization models to perform dynamic resource allocation to virtual machines and task scheduling. The provided solution is based on the hill-climbing algorithm to minimize response time. We evaluate the performance of proposed algorithms in terms of response time, turnaround time, throughput metrics, and request distribution with some of the existing algorithms that show significant improvements.

     

The design and evaluation of fair scheduling in wireless mesh networks

In this paper we address the problem of scheduling in wireless mesh networks. First, we provide a comparison of existing scheduling algorithms and classify them based on the degree of fairness, the scheduling techniques and their implementation frameworks. Then we propose a fair scheduling approach using multiple gateways. The proposed scheduling approach consists of four important steps, namely, requirement tables, requirement propagation, clique generation and schedule generation. Simulation experiments are conducted to compare the performance of fair scheduling with the method that does not use fair scheduling. The simulation results confirm that the proposed scheduling has better performance with respect to the metrics used for performance evaluation.     

Applying Lagrangian relaxation-based algorithms for airline coordinated flight scheduling problems

20 and 21 employed network flow techniques to construct coordinated scheduling models for passenger- and cargo-transportation, respectively. These models are formulated as mixed integer multiple commodity network flow problems with side constraints (NFPWS) that are characterized as NP-hard. Problem sizes are expected to be huge making the model more difficult to solve than traditional passenger/cargo flight scheduling problems. Therefore, a family of Lagrangian based algorithm is developed to solve the coordinated fleet routing and flight scheduling problems. Numerical tests are performed to evaluate the proposed algorithm using real operating data from two Taiwan airlines. The test results indicate that these solution algorithms are a significant improvement over those obtained with CPLEX. Moreover, the Lagrangian based algorithms are better than the mixed-stop heuristic, consequently they could be useful for allied airlines to solve coordinated fleet routing and flight scheduling problems.     

A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds

Recently, a growing number of scientific applications have been migrated into the cloud. To deal with the problems brought by clouds, more and more researchers start to consider multiple optimization goals in workflow scheduling. However, the previous works ignore some details, which are challenging but essential. Most existing multi-objective workflow scheduling algorithms overlook weight selection, which may result in the quality degradation of solutions. Besides, we find that the famous partial critical path (PCP) strategy, which has been widely used to meet the deadline constraint, can not accurately reflect the situation of each time step. Workflow scheduling is an NP-hard problem, so self-optimizing algorithms are more suitable to solve it.In this paper, the aim is to solve a workflow scheduling problem with a deadline constraint. We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning (RL) called DCMORL. DCMORL uses the Chebyshev scalarization function to scalarize its Q-values. This method is good at choosing weights for objectives. We propose an improved version of the PCP strategy calledMPCP. The sub-deadlines in MPCP regularly update during the scheduling phase, so they can accurately reflect the situation of each time step. The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline. Finally, we use four scientific workflows to compare DCMORL and several representative scheduling algorithms. The results indicate that DCMORL outperforms the above algorithms. As far as we know, it is the first time to apply RL to a deadline constrained workflow scheduling problem.     

基于DVS的实时多核嵌入式系统低功耗算法

动态电压调整（DVS）是低功耗设计方法中最基本的技术。然而,大部分的算法是基于单处理器平台的,并且仅考虑了相互独立的任务,这时使用DVS往往不能取得较好的效果。基于DVS提出了一种循环旋转调度技术来降低功耗,通过对程序中的循环进行重组,使得在满足时限的同时功耗最小,同时也考虑了电压转换所消耗的时间和功耗。     

基于多种云环境的任务调度算法综述

任务调度算法是云计算资源分配部署的核心方法。针对当前云计算发展面临的任务需求和数据量指数级增长的问题,重点对任务调度算法进行了系统的梳理和归纳,以云环境为分类依据,研究分析了单云、联盟云、混合云、多云四类调度算法。在单云环境中,从传统启发式、元启发式以及混合式任务调度算法角度进行阐述。在联盟云、混合云、多云环境中,从工作流和独立任务调度算法角度进行阐述。通过比较,总结了现有算法的优点、缺点以及优化性能,并形成结论性意见和开放性问题,为未来对容器云、数据云以及兼顾资源分配与任务调度算法的研究奠定基础。     

基于优先级的任务调度与负载均衡模型研究

在分布式计算环境下，为了有效地利用计算资源、快速完成协同计算任务，提出了基于优先级的任务调度与负载均衡模型．首先根据就绪任务队列和任务调度器所处的位置以及两者之间的关系，将任务调度划分为集中式任务调度和非集中式任务调度两种方式，在此基础上，利用时间Petri网建模技术，分别给出了采用这两种任务调度方式的、基于优先级的任务调度与负载均衡模型，并对各种模型的特点进行了详细分析．以此模型为基础，可以利用现有的时间Petri分析技术，对采用上述任务调度方式的任务调度算法进行模拟和分析，以便找出满足给定条件的最优的任务调度算法．     

Online Speed Scaling Based on Active Job Count to Minimize Flow Plus Energy

This paper is concerned with online scheduling algorithms that aim at minimizing the total flow time plus energy usage. The results are divided into two parts. First, we consider the well-studied “simple” speed scaling model and show how to analyze a speed scaling algorithm (called AJC) that changes speed discretely. This is in contrast to the previous algorithms which change the speed continuously. More interestingly, AJC admits a better competitive ratio, and without using extra speed. In the second part, we extend the study to a more general speed scaling model where the processor can enter a sleep state to further save energy. A new sleep management algorithm called IdleLonger is presented. This algorithm, when coupled with AJC, gives the first competitive algorithm for minimizing total flow time plus energy in the general model.     

An intelligent scheduling system using fuzzy logic controller for management of services in WiMAX networks

The appearance of media applications with high bandwidth and quality of service requirements has made a significant impact in telecommunications technology. In this direction, the IEEE802.16 has defined wireless access systems called WiMAX. These systems provide high-speed communications over a long distance. For this purpose some service classes with QoS requirements are defined; but the QoS scheduler is not standardized in IEEE802.16. The scheduling mechanism has a significant effect on the performance of WiMAX systems for use of bandwidth and radio resources. Some scheduling algorithms have been introduced by researchers; but they only provide some limited aspects of QoS. An intelligent decision support system is therefore necessary for scheduling. In this paper a fuzzy based scheduling system is proposed for compounds of real-time and non-real-time polling services which provide QoS requirements and fairness in dynamic conditions. A series of simulation experiments have been carried out to evaluate the performance of the proposed scheduling algorithm in terms of latency and throughput QoS parameters. The results show that the proposed method performs effectively regarding both of these criteria and achieves proportional system performance and fairness among different types of traffic.     

Scheduling parameter sweep applications on global Grids: a deadline and budget constrained cost–time optimization algorithm

Computational Grids and peer‐to‐peer (P2P) networks enable the sharing, selection, and aggregation of geographically distributed resources for solving large‐scale problems in science, engineering, and commerce. The management and composition of resources and services for scheduling applications, however, becomes a complex undertaking. We have proposed a computational economy framework for regulating the supply of and demand for resources and allocating them for applications based on the users' quality‐of‐service requirements. The framework requires economy‐driven deadline‐ and budget‐constrained (DBC) scheduling algorithms for allocating resources to application jobs in such a way that the users' requirements are met. In this paper, we propose a new scheduling algorithm, called the DBC cost–time optimization scheduling algorithm, that aims not only to optimize cost, but also time when possible. The performance of the cost–time optimization scheduling algorithm has been evaluated through extensive simulation and empirical studies for deploying parameter sweep applications on global Grids. Copyright © 2005 John Wiley & Sons, Ltd.