Fault-tolerant scheduling with dynamic number of replicas in heterogeneous systems

In the existing studies on fault-tolerant scheduling, the active replication schema makes use of ε + 1 replicas for each task to tolerate ε failures. However, in this paper, we show that it does not always lead to a higher reliability with more replicas. Besides, the more replicas implies more resource consumption and higher economic cost. To address this problem, with the target to satisfy the user’s reliability requirement with minimum resources, this paper proposes a new fault tolerant scheduling algorithm: MaxRe. In the algorithm, we incorporate the reliability analysis into the active replication schema and the theoretical analysis and experiments prove that the MaxRe algorithm’s schedule can certainly satisfy user’s reliability requirements. And the MaxRe scheduling algorithm can achieve the corresponding reliability with at most 70% fewer resources than the FTSA algorithm.

Pareto archived simulated annealing for single machine job shop scheduling with multiple objectives

In this paper, the single machine job shop scheduling problem is studied with the objectives of minimizing the tardiness and the material cost of jobs. The simultaneous consideration of these objectives is the multi-criteria optimization problem under study. A metaheuristic procedure based on simulated annealing is proposed to find the approximate Pareto optimal (non-dominated) solutions. The two objectives are combined in one composite utility function based on the decision maker’s interest in having a schedule with weighted combination. In view of the unknown nature of the weights for the defined objectives, a priori approach is applied to search for the non-dominated set of solutions based on the Pareto dominance. The obtained solutions set is presented to the decision maker to choose the best solution according to his preferences. The performance of the algorithm is evaluated in terms of the number of non-dominated schedules generated and the proximity of the obtained non-dominated front to the true Pareto front. Results show that the produced solutions do not differ significantly from the optimal solutions.

A multi-agent incremental negotiation scheme for meetings scheduling

We present an agent-oriented approach to the meeting scheduling problem and propose an incremental negotiation scheme that makes use of a hierarchical structure of an individual agent's working knowledge. First, we formalise the meeting scheduling problem in a multi-agent context, then elaborate on the design of a common agent architecture of all agents in the system. As a result, each agent becomes a modularised computing unit yet possesses high autonomy and robust interface with other agents. The system reserves the meeting participants' privacy since there are no agents with dominant roles, and agents can communicate at an abstract level in their hierarchical structures

A profiling based task scheduling approach for multicore network processors

 Multicore network processors have been playing an increasingly important role in computational processes, which emphasize on scalability and parallelism of the systems, in distributed environments especially in Internet-based delay-sensitive applications. It is an important but unsolved issue, however, to efficiently schedule tasks in network processors with multicore and multithread for improving the system throughput as much as possible. Profiling can gather runtime environment information and guide the compiler to optimize programs through scheduling tasks based on the runtime context. This paper proposes a profiling-based task scheduling approach, targeting on improving the throughput of multicore network processor (Intel IXP) systems in the balanced pipeline way. In this work, we investigate a profiling-based task scheduling framework, a task scheduling algorithm, and a set of performance models. Our task allocation scheme maps tasks onto the pipeline architecture and multiple threads of network processors in parallel, which incorporates the profiling context and global thread refinement. We evaluate our task scheduling algorithm by implementing representative network applications on the Intel IXP network processor. Experimental results demonstrate that our algorithm is able to schedule tasks in a balanced pipeline fashion and achieve the high throughput and data transmission rate. Copyright © 2012 John Wiley & Sons, Ltd.

Solving a multiobjective job shop scheduling problem using Pareto Archived Cuckoo Search

This paper investigates a new approach for solving the multiobjective job shop scheduling problem, namely the Cuckoo Search ( CS) approach. The requirement is to schedule jobs on a single machine so that the total material waste is minimised as well as the total tardiness time. The material waste is quantified in terms of saving factors to show the reduction in material that can be achieved when producing two jobs with the same materials in sequence. The estimated saving factor is used to calculate a cost savings for each job based on its material type. A formulation of multiobjective optimisation problems is adopted to generate the set of schedules that maximise the overall cost savings and minimise the total tardiness time. where all trade-offs are considered for the two conflicting objectives. A Pareto Archived Multiobjective Cuckoo Search (PAMOCS) is developed to find the set ofnondominated Pareto optimal solutions. The solution accuracy of PAMOCS is shown by comparing the closeness of the obtained solutions to the true Pareto front generated by the complete enumeration methad. Results shaw that CS is a very effective and promising technique to solve job shop scheduling problems.

Minimizing bounded uncertainty impact on scheduling with earliest start and due-date constraints via interval computation

Bounded uncertainty is a major challenge to real life scheduling as it increases the risk and cost depending on the objective function. Bounded uncertainty provides limited information about its nature. It provides only the upper and the lower bounds without information in between, in contrast to probability distributions and fuzzymembership functions. Bratley algorithm is usually used for scheduling with the constraints of earliest start and due-date. It is formulated as . The proposed research uses interval computation to minimize the impact of bounded uncertainty of processing times on Bratley’s algorithm. It minimizes the uncertainty of the estimate of the objective function. The proposed concept is to do the calculations on the interval values and approximate the end result instead of approximating each interval then doing numerical calculations. This methodology gives a more certain estimate of the objective function.

An effective heuristic for stockyard planning and machinery scheduling at a coal handling facility

Coal handling is a complex process involving different correlated and highly dependent operations such as selecting appropriate product types, planning stockpiles, scheduling stacking and reclaiming activities and managing train loads. Planning these operations manually is time consuming and can result in non-optimized schedules as future impact of decisions may not be appropriately considered. This paper addresses the operational scheduling of the continuous coal handling problem with multiple conflicting objectives. As the problem is NP-hard in nature, an effective heuristic is presented for planning stockpiles and scheduling resources to minimize delays in production and the coal age in the stockyard. A model of stockyard operations within a coal mine is described and the problem is formulated as a Bi- Objective Optimization Problem (BOOP). The algorithm efficacy is demonstrated on different real-life data scenarios. Computational results show that the solution algorithm is effective and the coal throughput is substantially impacted by the conflicting objectives. Together, the model and the proposed heuristic, can act as a decision support system for the stockyard planner to explore the effects of alternative decisions, such as balancing age and volume of stockpiles, and minimizing conflicts due to stacker and reclaimer movements.

Minimizing impact of bounded uncertainty on McNaughton's scheduling algorithm via interval programming

Uncertainty of data affects decision making process as it increases the risk and the costs of the decision. One of the challenges in minimizing the impact of the bounded uncertainty on any scheduling algorithm is the lack of information, as only the upper bound and the lower bound are provided without any known probability or membership function. On the contrary, probabilistic uncertainty can use probability distributions and fuzzy uncertainty can use the membership function. McNaughton's algorithm is used to find the optimum schedule that minimizes the makespan taking into consideration the preemption of tasks. The challenge here is the bounded inaccuracy of the input parameters for the algorithm, namely known as bounded uncertain data. This research uses interval programming to minimise the impact of bounded uncertainty of input parameters on McNaughton’s algorithm, it minimises the uncertainty of the cost function estimate and increase its optimality. This research is based on the hypothesis that doing the calculations on interval values then approximate the end result will produce more accurate results than approximating each interval input then doing numerical calculations.

GLOA : a new job scheduling algorithm for grid computing

The purpose of grid computing is to produce a virtual supercomputer by using free resources available through widespread networks such as the Internet. This resource distribution, changes in resource availability, and an unreliable communication infrastructure pose a major challenge for efficient resource allocation. Because of the geographical spread of resources and their distributed management, grid scheduling is considered to be a NP-complete problem. It has been shown that evolutionary algorithms offer good performance for grid scheduling. This article uses a new evaluation (distributed) algorithm inspired by the effect of leaders in social groups, the group leaders' optimization algorithm (GLOA), to solve the problem of scheduling independent tasks in a grid computing system. Simulation results comparing GLOA with several other evaluation algorithms show that GLOA produces shorter makespans.

An efficient scheduling method for grid systems based on a hierarchical stochastic petri net

This paper addresses the problem of resource scheduling in a grid computing environment. One of the main goals of grid computing is to share system resources among geographically dispersed users, and schedule resource requests in an efficient manner. Grid computing resources are distributed, heterogeneous, dynamic, and autonomous, which makes resource scheduling a complex problem. This paper proposes a new approach to resource scheduling in grid computing environments, the hierarchical stochastic Petri net (HSPN). The HSPN optimizes grid resource sharing, by categorizing resource requests in three layers, where each layer has special functions for receiving subtasks from, and delivering data to, the layer above or below. We compare the HSPN performance with the Min-min and Max-min resource scheduling algorithms. Our results show that the HSPN performs better than Max-min, but slightly underperforms Min-min.