An integrated security-aware job scheduling strategy for large-scale computational grids

All existing fault-tolerance job scheduling algorithms for computational grids were proposed under the assumption that all sites apply the same fault-tolerance strategy. They all ignored that each grid site may have its own fault-tolerance strategy because each site is itself an autonomous domain. In fact, it is very common that there are multiple fault-tolerance strategies adopted at the same time in a large-scale computational grid. Various fault-tolerance strategies may have different hardware and software requirements. For instance, if a grid site employs the job checkpointing mechanism, each computation node must have the following ability. Periodically, the computational node transmits the transient state of the job execution to the server. If a job fails, it will migrate to another computational node and resume from the last stored checkpoint. Therefore, in this paper we propose a genetic algorithm for job scheduling to address the heterogeneity of fault-tolerance mechanisms problem in a computational grid. We assume that the system supports four kinds fault-tolerance mechanisms, including the job retry, the job migration without checkpointing, the job migration with checkpointing, and the job replication mechanisms. Because each fault-tolerance mechanism has different requirements for gene encoding, we also propose a new chromosome encoding approach to integrate the four kinds of mechanisms in a chromosome. The risk nature of the grid environment is also taken into account in the algorithm. The risk relationship between jobs and nodes are defined by the security demand and the trust level. Simulation results show that our algorithm has shorter makespan and more excellent efficiencies on improving the job failure rate than the Min–Min and sufferage algorithms.     

An efficient memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

A Bee Colony based optimization approach for simultaneous job scheduling and data replication in grid environments

This paper presents a novel Bee Colony based optimization algorithm, named Job Data Scheduling using Bee Colony (JDS-BC). JDS-BC consists of two collaborating mechanisms to efficiently schedule jobs onto computational nodes and replicate datafiles on storage nodes in a system so that the two independent, and in many cases conflicting, objectives (i.e., makespan and total datafile transfer time) of such heterogeneous systems are concurrently minimized. Three benchmarks – varying from small- to large-sized instances – are used to test the performance of JDS-BC. Results are compared against other algorithms to show JDS-BC's superiority under different operating scenarios. These results also provide invaluable insights into data-centric job scheduling for grid environments.     

一种快速网格任务调度策略

网格任务调度目标有很多,如用户要求任务轮转时间短、花费代价小,而资源提供者希望资源利用率高等,这些目标相互冲突,因此网格任务调度不仅是一个NP难问题,而且是一个多目标优化问题.本文根据网格环境下任务的时间相关性特点,对传统蚁群算法进行了改进,提出了一种快速网格任务调度算法.该算法不仅解决了网格调度中多目标优化问题,而且依据任务调度历史信息生成蚁群算法的初始信息素分布,提高了蚁群算法的求解速度.     

An improved approximation algorithm for single machine scheduling with job delivery

In single machine scheduling with release times and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2.     

Toward balanced and sustainable job scheduling for production supercomputers

Job scheduling on production supercomputers is complicated by diverse demands of system administrators and amorphous characteristics of workloads. Specifically, various scheduling goals such as queuing efficiency and system utilization are usually conflicting and thus need to be balanced. Also, changing workload characteristics often impact the effectiveness of the deployed scheduling policies. Thus it is challenging to design a versatile scheduling policy that is effective in all circumstances. In this paper, we propose a novel job scheduling strategy to balance diverse scheduling goals and mitigate the impact of workload characteristics. First, we introduce metric-aware scheduling, which enables the scheduler to balance competing scheduling goals represented by different metrics such as job waiting time, fairness, and system utilization. Second, we design a scheme to dynamically adjust scheduling policies based on feedback information of monitored metrics at runtime. We evaluate our design using real workloads from supercomputer centers. The results demonstrate that our scheduling mechanism can significantly improve system performance in a balanced, sustainable fashion.     

An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting

This paper proposes several novel hybrid ant colony optimization (ACO)-based algorithms to resolve multi-objective job-shop scheduling problem with equal-size lot splitting. The main issue discussed in this paper is lot-splitting of jobs and tradeoff between lot-splitting costs and makespan. One of the disadvantages of ACO is its uncertainty on time of convergence. In order to enrich search patterns of ACO and improve its performance, five enhancements are made in the proposed algorithms including: A new type of pheromone and greedy heuristic function; Three new functions of state transition rules; A nimble local search algorithm for the improvements of solution quality; Mutation mechanism for divisive searching; A particle swarm optimization (PSO)-based algorithm for adaptive tuning of parameters. The objectives that are used to measure the quality of the generated schedules are weighted-sum of makespan, tardiness of jobs and lot-splitting cost. The developed algorithms are analyzed extensively on real-world data obtained from a printing company and simulated data. A mathematical programming model is developed and paired-samples t-tests are performed between obtained solutions of mathematical programming model and proposed algorithms in order to verify effectiveness of proposed algorithms.     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

Ant colony optimization combined with taboo search for the job shop scheduling problem

In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizations of partial schedules. Besides, a taboo search algorithm is embedded to improve the solution quality. We run the proposed algorithm on 101 benchmark instances and obtain competitive results and a new best upper bound for one open benchmark instance is found.     

An incentive-based heuristic job scheduling algorithm for utility grids

Job scheduling in utility grids should take into account the incentives for both grid users and resource providers. However, most of existing studies on job scheduling in utility grids only address the incentive for one party, i.e., either the users or the resource providers. Very few studies on job scheduling in utility grids consider incentives for both parties, in which the cost, one of the most attractive incentives for users, is not addressed. In this paper, we study the job scheduling in utility grid by optimizing the incentives for both parties. We propose a multi-objective optimization approach, i.e., maximizing the successful execution rate of jobs and minimizing the combined cost (incentives for grid users), and minimizing the fairness deviation of profits (incentive for resource providers). The proposed multi-objective optimization approach could offer sufficient incentives for the two parties to stay and play in the utility grid. A heuristic scheduling algorithm called Cost-Greedy Price-Adjusting (CGPA) algorithm is developed to optimize the incentives for both parties. Simulation results show that the CGPA algorithm is effective and could lead to higher successful execution rate, lower combined cost and lower fairness deviation compared with some popular algorithms in most cases.     

An SCP-based heuristic approach for scheduling distributed data-intensive applications on global grids

Data-intensive Grid applications need access to large data sets that may each be replicated on different resources. Minimizing the overhead of transferring these data sets to the resources where the applications are executed requires that appropriate computational and data resources be selected. In this paper, we consider the problem of scheduling an application composed of a set of independent tasks, each of which requires multiple data sets that are each replicated on multiple resources. We break this problem into two parts: one, to match each task (or job) to one compute resource for executing the job and one storage resource each for accessing each data set required by the job and two, to assign the set of tasks to the selected resources. We model the first part as an instance of the well-known Set Covering Problem (SCP) and apply a known heuristic for SCP to match jobs to resources. The second part is tackled by extending existing MinMin and Sufferage algorithms to schedule the set of distributed data-intensive tasks. Through simulation, we experimentally compare the SCP-based matching heuristic to others in conjunction with the task scheduling algorithms and present the results.     

基于改进蚁群算法的云计算任务调度

利用云中资源进行高效任务调度是保证云计算系统可靠运行的关键问题。提出一种基于改进蚁群优化算法的任务调度方法。算法采用蚂蚁系统的伪随机比例规则进行寻优,防止算法过快收敛到局部最优解,同时结合排序蚂蚁系统和最大最小蚂蚁系统的设计思想完成信息素更新,有效求解优化问题。实验结果显示,该算法具有很好的寻优能力,提高了云资源的利用率。     

信任驱动的网格作业调度遗传算法

作业调度是网格计算的关键技术之一.近年来,人们将信任机制融入到作业调度算法中,以满足作业调度对网格服务质量提出的需求.根据一信任模型,设计了求解基于该信任模型的遗传算法,该算法在保持种群多样性的同时,提高了局部搜索能力.仿真结果表明,该算法可以获得较好的调度结果,且收敛速度快.     

基于信息素调整的蚁群算法求解JSP问题

为更好的求解作业车间调度问题,针对基本蚁群算法求解作业车间调度问题容易进入局部最优问题的情况,提出了一种基于信息素调整的蚁群算法.该算法通过判断信息素矩阵中最大值与最小值之间的比值,当该比值达到算法设定的阀值时,根据相应策略时信息素矩阵进行调整,有效地缩小了信息素之间的差距,有利于跳出局部最优状态;给出了该算法实施的具体步骤.用该算法求解作业车间调度问题,仿真实验结果表明,该算法与基本蚁群算法相比在收敛速度和计算最优解方面都有了改进.     

Task scheduling using NSGA II with fuzzy adaptive operators for computational grids

Scheduling algorithms have an essential role in computational grids for managing jobs, and assigning them to appropriate resources. An efficient task scheduling algorithm can achieve minimum execution time and maximum resource utilization by providing the load balance between resources in the grid. The superiority of genetic algorithm in the scheduling of tasks has been proven in the literature. In this paper, we improve the famous multi-objective genetic algorithm known as NSGA-II using fuzzy operators to improve quality and performance of task scheduling in the market-based grid environment. Load balancing, Makespan and Price are three important objectives for multi-objective optimization in the task scheduling problem in the grid. Grid users do not attend load balancing in making decision, so it is desirable that all solutions have good load balancing. Thus to decrease computation and ease decision making through the users, we should consider and improve the load balancing problem in the task scheduling indirectly using the fuzzy system without implementing the third objective function. We have used fuzzy operators for this purpose and more quality and variety in Pareto-optimal solutions. Three functions are defined to generate inputs for fuzzy systems. Variance of costs, variance of frequency of involved resources in scheduling and variance of genes values are used to determine probabilities of crossover and mutation intelligently. Variance of frequency of involved resources with cooperation of Makespan objective satisfies load balancing objective indirectly. Variance of genes values and variance of costs are used in the mutation fuzzy system to improve diversity and quality of Pareto optimal front. Our method conducts the algorithm towards best and most appropriate solutions with load balancing in less iteration. The obtained results have proved that our innovative algorithm converges to Pareto-optimal solutions faster and with more quality.     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

基于蚁群算法的网格资源调度策略研究

网格计算中的资源调度技术是连接网格底层和高层功能的纽带.蚁群算法作为一种成熟的分布式、启发式搜索鼢算法,其实质上是一种通过群体智能间接散布最优解信息,采用逐步收敛的方式求解最优解的算法.通过介绍蚁群算法的原理,对使用蚁群算法作为网格计算资源调度策略的可行性进行了分析,并在此基础上探讨了基于蚁群算法的网格计算资源调度的设计思路、运作流程、需要考虑的信息素更新方式等关键问题,最后给出了基于蚁群算法的网格计算资源调度总控程序.     

云计算环境下融合遗传算法和蚁群算法QoS约束任务调度

针对已有云计算任务调度算法为实现最短时间跨度而不能兼顾负载均衡和服务质量的问题,提出基于遗传算法和蚁群算法融合的QoS约束任务调度策略CAAC。CAAC利用任务的预测完成时间和成本耗费定义适应度函数;通过遗传算子全局搜索最优解,融合蚁群算子提高解的精确度;当任务数量大于50时,该算法收敛速度和资源利用率比蚁群算法平均提高4.7'和30.8'。仿真结果表明,该算法在保证服务质量和资源负载均衡方面具有优越性。     

A very fast TS/SA algorithm for the job shop scheduling problem

The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.