A hybrid cuckoo search and variable neighborhood descent for single and multiobjective scheduling problems

Cuckoo search (CS) is a relatively new meta-heuristic that has proven its strength in solving continuous optimization problems. This papers applies cuckoo search to the class of sequencing problems by hybridizing it with a variable neighborhood descent local search for enhancing the quality of the obtained solutions. The Lévy flight operator proposed in the original CS is modified to address the discrete nature of scheduling problems. Two well-known problems are used to demonstrate the effectiveness of the proposed hybrid CS approach. The first is the NP-hard single objective problem of minimizing the weighted total tardiness time (Formula presented.) and the second is the multiobjective problem of minimizing the flowtime ¯ and the maximum tardiness Tmaxfor single machine (Formula presented.). For the first problem, computational results show that the hybrid CS is able to find the optimal solutions for all benchmark test instances with 40, 50, and 100 jobs and for most instances with 150, 200, 250, and 300 jobs. For the second problem, the hybrid CS generated solutions on and very close to the exact Pareto fronts of test instances with 10, 20, 30, and 40 jobs. In general, the results reveal that the hybrid CS is an adequate and robust method for tackling single and multiobjective scheduling problems.

Extending scheduling algorithms to minimise the impact of bounded uncertainty using interval programming

 This research proposed a new methodology to extend algorithms to accept interval-based uncertain parameters. The methodology is applied on scheduling algorithms, including heuristic and meta-heuristic algorithms and produced optimal results with higher accuracy. The research outcomes are effective for decision making process using uncertain or predicted data.

Efficient consolidation-aware VCPU scheduling on multicore virtualization platform

Multicore processors are widely used in today's computer systems. Multicore virtualization technology provides an elastic solution to more efficiently utilize the multicore system. However, the Lock Holder Preemption (LHP) problem in the virtualized multicore systems causes significant CPU cycles wastes, which hurt virtual machine (VM) performance and reduces response latency. The system consolidates more VMs, the LHP problem becomes worse. In this paper, we propose an efficient consolidation-aware vCPU (CVS) scheduling scheme on multicore virtualization platform. Based on vCPU over-commitment rate, the CVS scheduling scheme adaptively selects one algorithm among three vCPU scheduling algorithms: co-scheduling, yield-to-head, and yield-to-tail based on the vCPU over-commitment rate because the actions of vCPU scheduling are split into many single steps such as scheduling vCPUs simultaneously or inserting one vCPU into the run-queue from the head or tail. The CVS scheme can effectively improve VM performance in the low, middle, and high VM consolidation scenarios. Using real-life parallel benchmarks, our experimental results show that the proposed CVS scheme improves the overall system performance while the optimization overhead remains low.

ANGEL: agent-based scheduling for real-time tasks in virtualized clouds

The success of cloud computing makes an increasing number of real-time applications such as signal processing and weather forecasting run in the cloud. Meanwhile, scheduling for real-time tasks is playing an essential role for a cloud provider to maintain its quality of service and enhance the system's performance. In this paper, we devise a novel agent-based scheduling mechanism in cloud computing environment to allocate real-time tasks and dynamically provision resources. In contrast to traditional contract net protocols, we employ a bidirectional announcement-bidding mechanism and the collaborative process consists of three phases, i.e., basic matching phase, forward announcement-bidding phase and backward announcement-bidding phase. Moreover, the elasticity is sufficiently considered while scheduling by dynamically adding virtual machines to improve schedulability. Furthermore, we design calculation rules of the bidding values in both forward and backward announcement-bidding phases and two heuristics for selecting contractors. On the basis of the bidirectional announcement-bidding mechanism, we propose an agent-based dynamic scheduling algorithm named ANGEL for real-time, independent and aperiodic tasks in clouds. Extensive experiments are conducted on CloudSim platform by injecting random synthetic workloads and the workloads from the last version of the Google cloud tracelogs to evaluate the performance of our ANGEL. The experimental results indicate that ANGEL can efficiently solve the real-time task scheduling problem in virtualized clouds.

FESTAL: fault-tolerant elastic scheduling algorithm for real-time tasks in virtualized clouds

As clouds have been deployed widely in various fields, the reliability and availability of clouds become the major concern of cloud service providers and users. Thereby, fault tolerance in clouds receives a great deal of attention in both industry and academia, especially for real-time applications due to their safety critical nature. Large amounts of researches have been conducted to realize fault tolerance in distributed systems, among which fault-tolerant scheduling plays a significant role. However, few researches on the fault-tolerant scheduling study the virtualization and the elasticity, two key features of clouds, sufficiently. To address this issue, this paper presents a fault-tolerant mechanism which extends the primary-backup model to incorporate the features of clouds. Meanwhile, for the first time, we propose an elastic resource provisioning mechanism in the fault-tolerant context to improve the resource utilization. On the basis of the fault-tolerant mechanism and the elastic resource provisioning mechanism, we design novel fault-tolerant elastic scheduling algorithms for real-time tasks in clouds named FESTAL, aiming at achieving both fault tolerance and high resource utilization in clouds. Extensive experiments injecting with random synthetic workloads as well as the workload from the latest version of the Google cloud tracelogs are conducted by CloudSim to compare FESTAL with three baseline algorithms, i.e., Non-M igration-FESTAL (NMFESTAL), Non-Overlapping-FESTAL (NOFESTAL), and Elastic First Fit (EFF). The experimental results demonstrate that FESTAL is able to effectively enhance the performance of virtualized clouds.

A multiobjective state transition algorithm for single machine scheduling

In this paper, a discrete state transition algorithm is introduced to solve a multiobjective single machine job shop scheduling problem. In the proposed approach, a non-dominated sort technique is used to select the best from a candidate state set, and a Pareto archived strategy is adopted to keep all the non-dominated solutions. Compared with the enumeration and other heuristics, experimental results have demonstrated the effectiveness of the multiobjective state transition algorithm.

A multi-objective evolutionary algorithm-based decision support system: a case study on job-shop scheduling in manufacturing

In this paper, an evolutionary algorithm is used for developing a decision support tool to undertake multi-objective job-shop scheduling problems. A modified micro genetic algorithm (MmGA) is adopted to provide optimal solutions according to the Pareto optimality principle in solving multi-objective optimisation problems. MmGA operates with a very small population size to explore a wide search space of function evaluations and to improve the convergence score towards the true Pareto optimal front. To evaluate the effectiveness of the MmGA-based decision support tool, a multi-objective job-shop scheduling problem with actual information from a manufacturing company is deployed. The statistical bootstrap method is used to evaluate the experimental results, and compared with those from the enumeration method. The outcome indicates that the decision support tool is able to achieve those optimal solutions as generated by the enumeration method. In addition, the proposed decision support tool has advantage of achieving the results within a fraction of the time.

A multi-level approach to planning and scheduling resources for aviation training

This paper describes a multi-level system dynamics (SD) / discrete event simulation (DES) approach for assessing planning and scheduling problems within an aviation training continuum. The aviation training continuum is a complex system, consisting of multiple aviation schools interacting through interschool student and instructor flows that are affected by external triggers such as resource availability and the weather.
SD was used to model the overall training continuum at a macro level to ascertain relationships between system entities. SD also assisted in developing a shared understanding of the training continuum, which involves constructing the definitions of the training requirements, resources and policy objectives. An end-to-end model of the continuum is easy to relate to, while dynamic visualisation of system behaviour provides a method for exploration of the model.
DES was used for micro level exploration of an individual school within the training continuum to capture the physical aspects of the system including resource capacity requirements, bottlenecks and student waiting times. It was also used to model stochastic events such as weather and student availability. DES has the advantage of being able to represent system variability and accurately reflect the limitations imposed on a system by resource constraints.
Through sharing results between the models, we demonstrate a multi-level approach to the analysis of the overall continuum. The SD model provides the school’s targeted demand to the DES model. The detailed DES model is able to assess schedules in the presence of resource constraints and variability and provide the expected capacity of a school to the high level SD model, subjected to constraints such as instructor availability or budgeted number of training systems. The SD model allows stakeholders to assess how policy and planning affect the continuum, both in the short and the long term.
The development of this approach permits moving the analysis of the continuum between SD and DES models as appropriate for given system entities, scales and tasks. The resultant model outcomes are propagated between the continuum and the detailed DES model, iteratively generating an assessment of the entire set of plans and schedule across the continuum. Combining data and information between SD and DES models and techniques assures relevance to the stakeholder needs and effective problem scoping and scaling that can also evolve with dynamic architecture and policy requirements.
An example case study shows the combined use of the two models and how they are used to evaluate a typical scenario where increased demand is placed on the training continuum. The multi-level approach provides a high level indication of training requirements to the model of the new training school, where the detailed model indicates the resources required to achieve those particular student levels.

Layered workflow scheduling algorithm

Workflow applications require workflow processing in which workflow tasks are processed based on their dependencies. With the emergency of complex distributed systems such as grids and clouds, efficient workflow scheduling (WFS) algorithms have become the core components of the workflow management systems (WfMS). Thus, WFS that allocates each task in the workflow to a relevant resource with the aim of improving system performance and end user satisfaction is fundamentally important. In this paper, we propose a new workflow scheduling algorithm called Layered Workflow Scheduling Algorithm (LWFS) for scheduling workflow applications. We studied the efficacy of the LWFS scheduling experimentally and compared its performance with approaches including Improved Critical Path using Descendant Prediction (ICPDP), Highest Level First with Estimated Time (HLFET), Modified Critical Path (MCP) and Earliest Time First (ETF). The results of the experiments show that the proposed approach outperforms other approaches.

Workflow scheduling on distributed systems

Growing evidence shows that in obtaining high performance, a well-managed time-constrained workflow scheduling is needed. Efficient workflow scheduling is critical for achieving high performance especially in heterogeneous computing system. However, it is a great challenge to improve performance and to optimize several objectives simultaneously. We propose a workflow scheduling algorithm that minimizes the makespan of the workflow application modeled by a Directed Acyclic Graph (DAG). The new proposed scheduling algorithm is named Multi Dependency Joint (MDJ) Algorithm. The performance of MDJ is compared with existing algorithms such as, Highest Level First with Estimated Time (HLFET), Modified Critical Path (MCP) and Earliest Time First (ETF). As a result, the experiments show that our proposed MDJ algorithm outperforms HLEFT, MCP, and EFT with a 7% lower overall completion time.

An alternative data collection scheduling scheme in wireless sensor networks

Despite significant advancements in wireless sensor networks (WSNs), energy conservation remains one of the most important research challenges. Recently, the problem of energy conservation has been addressed by applying mobile sink as an effective technique that can enhance efficiency of energy consumption in the networks. In this paper, the energy conservation problem is firstly formulated to maximize the lifetime of WSN subject to delay and node energy constraints. Then, to solve the defined energy conservation problem, a data collection scheduling with a mobile sink scheme is proposed. In the proposed approach, the sink movement is governed by a type-2 fuzzy controller to be located at the best location and time to collect sensory data. We conducted extensive experiments to study the effectiveness of the proposed protocol and compared it against the streaming data delivery (SDD) and virtual circle combined straight routing (VCCS) protocols. We observed that the proposed protocol outperforms both SDD and VCCS approaches by reducing energy consumption, minimize delays and enhance data collection quality.

A novel time computation model based on algorithm complexity for data intensive scientific workflow design and scheduling

Scientific workflow offers a framework for cooperation between remote and shared resources on a grid computing environment (GCE) for scientific discovery. One major function of scientific workflow is to schedule a collection of computational subtasks in well-defined orders for efficient outputs by estimating task duration at runtime. In this paper, we propose a novel time computation model based on algorithm complexity (termed as TCMAC model) for high-level data intensive scientific workflow design. The proposed model schedules the subtasks based on their durations and the complexities of participant algorithms. Characterized by utilization of task duration computation function for time efficiency, the TCMAC model has three features for a full-aspect scientific workflow including both dataflow and control-flow: (1) provides flexible and reusable task duration functions in GCE;(2) facilitates better parallelism in iteration structures for providing more precise task durations;and (3) accommodates dynamic task durations for rescheduling in selective structures of control flow. We will also present theories and examples in scientific workflows to show the efficiency of the TCMAC model, especially for control-flow. Copyright©2009 John Wiley & Sons, Ltd.

Reliability-aware distributed computing scheduling policy

One of the primary issues associated with the efficient and effective utilization of distributed computing is resource management and scheduling. As distributed computing resource failure is a common occurrence, the issue of deploying support for integrated scheduling and fault-tolerant approaches becomes paramount importance. To this end, we propose a fault-tolerant dynamic scheduling policy that loosely couples dynamic job scheduling with job replication scheme such that jobs are efficiently and reliably executed. The novelty of the proposed algorithm is that it uses passive replication approach under high system load and active replication approach under low system loads. The switch between these two replication methods is also done dynamically and transparently. Performance evaluation of the proposed fault-tolerant scheduler and a comparison with similar fault-tolerant scheduling policy is presented and shown that the proposed policy performs better than the existing approach.

Adaptive energy-efficient qos-aware scheduling algorithm for TCP/IP mobile cloud

The expected pervasive use of mobile cloud computing and the growing number of Internet data centers have brought forth many concerns, such as, energy costs and energy saving management of both data centers and mobile connections. Therefore, the need for adaptive and distributed resource allocation schedulers for minimizing the communication-plus-computing energy consumption has become increasingly important. In this paper, we propose and test an efficient dynamic resource provisioning scheduler that jointly minimizes computation and communication energy consumption, while guaranteeing user Quality of Service (QoS) constraints. We evaluate the performance of the proposed dynamic resource provisioning algorithm with respect to the execution time, goodput and bandwidth usage and compare the performance of the proposed scheduler against the exiting approaches. The attained experimental results show that the proposed dynamic resource provisioning algorithm achieves much higher energy-saving than the traditional schemes.