The Tricriteria Two-Machine Flowshop Scheduling Problem

The literature on the two-machine flowshop scheduling problem reveals that the problem has been addressed with bicriteria of either makespan and mean flowtime or makespan and maximum tardiness (lateness). This paper extends the problem to all the three criteria (tricriteria) where the objective is to minimize a weighted sum of makespan, mean flowtime, and maximum lateness. A dominance relation and a lower bound are established. The dominance relation and the lower bound are used to develop a branch-and-bound algorithm. The dominance relation is also used to develop several heuristics. An extensive computational analysis is conducted to evaluate the performance of the dominance relation and the heuristics. The analysis shows that the dominance relation is effective. The analysis also shows that the heuristics are quite efficient, and some heuristics have an error of less than 1%. Moreover, these heuristics have the desirable property that the error does not increase by the number of jobs.     

Minimizing mean flowtime and makespan on master–slave systems

The master–slave scheduling model is a new model recently introduced by Sahni. It has many important applications in parallel computer scheduling and industrial settings such as semiconductor testing, machine scheduling, etc. In this model each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. While the preprocessing and postprocessing tasks are scheduled on the master machine, the slave tasks are scheduled on the slave machines. In this paper, we consider scheduling problems on single-master master–slave systems. We first strengthen some previously known complexity results for makespan problems, by showing them to be strongly NP-hard. We then show that the problem of minimizing the mean flowtime is strongly NP-hard even under severe constraints. Finally, we propose some heuristics for the mean flowtime and makespan problems subject to some constraints, and we analyze the worst-case performance of these heuristics.     

Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

Algorithm-system scalability of heterogeneous computing

Scalability is a key factor of the design of distributed systems and parallel algorithms and machines. However, conventional scalabilities are designed for homogeneous parallel processing. There is no suitable and commonly accepted definition of scalability metric for heterogeneous systems. Isospeed scalability is a well-defined metric for homogeneous computing. This study extends the isospeed scalability metric to general heterogeneous computing systems. The proposed isospeed-efficiency model is suitable for both homogeneous and heterogeneous computing. Through theoretical analyses, we derive methodologies of scalability measurement and prediction for heterogeneous systems. Experimental results have verified the analytical results and confirmed that the proposed isospeed-efficiency scalability works well in both homogeneous and heterogeneous environments.     

Energy-Aware Scheduling on Multicore Heterogeneous Grid Computing Systems

We address a multicriteria non-preemptive energy-aware scheduling problem for computational Grid systems. This work introduces a new formulation of the scheduling problem for multicore heterogeneous computational Grid systems in which the minimization of the energy consumption, along with the makespan metric, is considered. We adopt a two-level model, in which a meta-broker agent (level 1) receives all user tasks and schedules them on the available resources, belonging to different local providers (level 2). The computing capacity and energy consumption of resources are taken from real multi-core processors from the main current vendors. Twenty novel list scheduling methods for the problem are proposed, and a comparative analysis of all of them over a large set of problem instances is presented. Additionally, a scalability study is performed in order to analyze the contribution of the best new bi-objective list scheduling heuristics when the problem dimension grows. We conclude after the experimental analysis that accurate trade-off schedules are computed by using the new proposed methods.     

Heterogeneous Computing and Parallel Genetic Algorithms

This paper analyzes some technical and practical issues concerning the heterogeneous execution of parallel genetic algorithms (PGAs). In order to cope with a plethora of different operating systems, security restrictions, and other problems associated to multi-platform execution, we use Java to implement a distributed PGA model. The distributed PGA runs at the same time on different machines linked by different kinds of communication networks. This algorithm benefits from the computational resources offered by modern LANs and by Internet, therefore allowing researchers to solve more difficult problems by using a large set of available machines. We analyze the way in which such heterogeneous systems affect the genetic search for two problems. Our conclusion is that super-linear performance can be achieved not only in homogeneous but also in heterogeneous clusters of machines. In addition, we study some special features of the running platforms for PGAs, and basically find out that heterogeneous computing can be as efficient or even more efficient than homogeneous computing for parallel heuristics.     

Makespan minimization subject to flowtime optimality on identical parallel machines

We consider the identical parallel machine problem with makespan minimization subject to minimum total flowtime. First, we develop an optimal algorithm to the identical parallel machine problem with the objective of minimizing makespan. To improve the computational efficiency, two implementation techniques, the lower bound calculation and the job replacement rule, are applied. Based on the algorithm, an optimal algorithm, using new lower bounds, to the considered problem is developed. The result of this study can also be used to solve the bicriteria problem of minimizing the weighted sum of makespan and mean flowtime. Computational experiments are conducted up to six machines and 1000 jobs. Although the proposed algorithm has an exponential time complexity, the computational results show that it is efficient to find the optimal solution.     

Physis语言框架在WENO高阶数值格式异构计算中的应用

WENO(weighted essentially non-oscillatory)是计算流体力学中广泛采用的一种高阶数值格式。由于算法本身和异构计算编程的复杂性,需要开展异构计算代码自动生成的研究,以加速更多的应用。本文基于Physis这一领域编程语言框架,针对三维五阶WENO计算的天文应用,实现了其异构代码的自动生成。在超级计算机"元"上的测试结果表明,自动生成的异构计算代码具有良好的可扩展性,计算性能达到手工优化异构代码的72%,可为相关流体计算的异构代码生成提供借鉴。     

Heterogeneous computing scheduling with evolutionary algorithms

This work presents sequential and parallel evolutionary algorithms (EAs) applied to the scheduling problem in heterogeneous computing environments, a NP-hard problem with capital relevance in distributed computing. These methods have been specifically designed to provide accurate and efficient solutions by using simple operators that allow them to be later extended for solving realistic problem instances arising in distributed heterogeneous computing (HC) and grid systems. The EAs were codified over MALLBA, a general-purpose library for combinatorial optimization. Efficient numerical results are reported in the experimental analysis performed on well-known problem instances. The comparative study of scheduling methods shows that the parallel versions of the implemented evolutionary algorithms are able to achieve high problem solving efficacy, outperforming traditional scheduling heuristics and also improving over previous results already reported in the related literature.     

Integration of task abortion and security requirements in GA-based meta-heuristics for independent batch grid scheduling

Scheduling and resource allocation in large scale distributed environments, such as Computational Grids (CGs), arise new requirements and challenges not considered in traditional distributed computing environments. Among these new requirements, task abortion and security become needful criteria for Grid schedulers. The former arises due to the dynamics of the Grid systems, in which resources are expected to enter and leave the system in an unpredictable way. The latter requirement appears crucial in Grid systems mainly due to a multi-domain nature of CGs. The main aim of this paper is to develop a scheduling model that enables the aggregation of task abortion and security requirements as additional, together with makespan and flowtime, scheduling criteria into a cumulative objective function. We demonstrate the high effectiveness of genetic-based schedulers in finding near-optimal solutions for multi-objective scheduling problem, where all criteria (objectives) are simultaneously optimized. The proposed meta-heuristics are experimentally evaluated in static and dynamic Grid scenarios by using a Grid simulator. The obtained results show the fast reduction of the values of basic scheduler performance metrics, especially in the dynamic case, that confirms the usefulness of the proposed approach in real-life scenarios.     

Platform impact on performance of parallel genetic algorithms: Design and implementation considerations

Many problems in the operations research field cannot be solved to optimality within reasonable amounts of time with current computational resources. In order to find acceptable solutions to these computationally demanding problems, heuristic methods such as genetic algorithms are often developed. Parallel computing provides alternative design options for heuristic algorithms, as well as the opportunity to obtain performance benefits in both computational time and solution quality of these heuristics. Heuristic algorithms may be designed to benefit from parallelism by taking advantage of the parallel architecture. This study will investigate the performance of the same global parallel genetic algorithm on two popular parallel architectures to investigate the interaction of parallel platform choice and genetic algorithm design. The computational results of the study illustrate the impact of platform choice on parallel heuristic methods. This paper develops computational experiments to compare algorithm development on a shared memory architecture and a distributed memory architecture. The results suggest that the performance of a parallel heuristic can be increased by considering the desired outcome and tailoring the development of the parallel heuristic to a specific platform based on the hardware and software characteristics of that platform.     

Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect

In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics are provided.     

Allocating task interaction graphs to processors in heterogeneousnetworks

The problem of allocating task interaction graphs (TIGs) to heterogeneous computing systems to minimize job completion time is investigated. The only restriction is that the interprocessor communication cost is the same for any pair of processors. This is suitable for local area network based systems, such as Ethernet, as well as fully interconnected multiprocessor systems. An optimal polynomial solution exists if sufficient homogeneous processors and communication capacity are available. This solution is generalized to obtain two faster heuristics, one for the case of homogeneous processors and the other for heterogeneous processors. The heuristics were tested extensively with 60,900 systematically generated random TIGs and shown to be stable independent of the size of the TIG. A performance model is also proposed to predict the performance of the heuristic algorithms, and it is successful in explaining the experimental results qualitatively     

Statistical measures for quantifying task and machine heterogeneities

We study heterogeneous computing (HC) systems that consist of a set of different machines that have varying capabilities. These machines are used to execute a set of heterogeneous tasks that vary in their computational complexity. Finding the optimal mapping of tasks to machines in an HC system has been shown to be, in general, an NP-complete problem. Therefore, heuristics have been used to find near-optimal mappings. The performance of allocation heuristics can be affected significantly by factors such as task and machine heterogeneities. In this paper, we identify different statistical measures used to quantify the heterogeneity of HC systems, and show the correlation between the performance of the heuristics and these measures through simple mapping examples and synthetic data analysis. In addition, we illustrate how regression trees can be used to predict the most appropriate heuristic for an HC system based on its heterogeneity.     

适用于异构集群的混合并行流线生成系统

流线是流场可视化的主要方法之一,而针对大规模流场的流线生成由于计算量大往往需要采用高性能计算机这样的并行计算环境结合并行化算法以实现计算加速.在当前异构计算系统越来越普遍的情况下,为了充分利用并行异构计算环境的计算能力,实现更高效的并行流线生成,本文采用了基于数据并行原语结合分布式消息通讯的技术架构,设计了一套适用于异构集群的混合并行流线生成系统,并在此基础上针对数据分块、数据冗余化及进程通讯策略等方面进行设计,提出并实现了一套并行粒子追踪算法.该系统被部署于国产超算平台上,并针对大规模CFD流场模拟结果数据可视化应用开展了实验.本文给出了相关实验结果,分析了核心并行算法的速度性能、可扩展性以及负载均衡等方面情况,说明了系统及算法的有效性和可扩展性.     

An efficient list-based task scheduling algorithm for heterogeneous distributed computing environment

The task scheduling in heterogeneous distributed computing systems plays a crucial role in reducing the makespan and maximizing resource utilization. The diverse nature of the devices in heterogeneous distributed computing systems intensifies the complexity of scheduling the tasks. To overcome this problem, a new list-based static task scheduling algorithm namely Deadline-Aware-Longest-Path-of-all-Predecessors (DA-LPP) is being proposed in this article. In the prioritization phase of the DA-LPP algorithm, the path length of the current task from all its predecessors at each level is computed and among them, the longest path length value is assigned as the rank of the task. This strategy emphasizes the tasks in the critical path. This well-optimized prioritization phase leads to an observable minimization in the makespan of the applications. In the processor selection phase, the DA-LPP algorithm implements the improved insertion-based policy which effectively utilizes the unoccupied leftover free time slots of the processors which improve resource utilization, further least computation cost allocation approach is followed to minimize the overall computation cost of the processors and parental prioritization policy is incorporated to further reduce the scheduling length. To demonstrate the robustness of the proposed algorithm, a synthetic graph generator is used in this experiment to generate a huge variety of graphs. Apart from the synthetic graphs, real-world application graphs like Montage, LIGO, Cybershake, and Epigenomic are also considered to grade the performance of the DA-LPP algorithm. Experimental results of the DA-LPP algorithm show improvement in performance in terms of scheduling length ratio, makespan reduction rate , and resource reduction rate when compared with other algorithms like DQWS, DUCO, DCO and EPRD. The results reveal that for 1000 task set with deadline equals to two times of the critical path, the scheduling length ratio of the DA-LPP algorithm is better than DQWS by 35%, DUCO by 23%, DCO by 26 %, and EPRD by 17%.     

HPC‐GAP: engineering a 21st‐century high‐performance computer algebra system

Symbolic computation has underpinned a number of key advances in Mathematics and Computer Science. Applications are typically large and potentially highly parallel, making them good candidates for parallel execution at a variety of scales from multi‐core to high‐performance computing systems. However, much existing work on parallel computing is based around numeric rather than symbolic computations. In particular, symbolic computing presents particular problems in terms of varying granularity and irregular task sizes that do not match conventional approaches to parallelisation. It also presents problems in terms of the structure of the algorithms and data. This paper describes a new implementation of the free open‐source GAP computational algebra system that places parallelism at the heart of the design, dealing with the key scalability and cross‐platform portability problems. We provide three system layers that deal with the three most important classes of hardware: individual shared memory multi‐core nodes, mid‐scale distributed clusters of (multi‐core) nodes and full‐blown high‐performance computing systems, comprising large‐scale tightly connected networks of multi‐core nodes. This requires us to develop new cross‐layer programming abstractions in the form of new domain‐specific skeletons that allow us to seamlessly target different hardware levels. Our results show that, using our approach, we can achieve good scalability and speedups for two realistic exemplars, on high‐performance systems comprising up to 32000 cores, as well as on ubiquitous multi‐core systems and distributed clusters. The work reported here paves the way towards full‐scale exploitation of symbolic computation by high‐performance computing systems, and we demonstrate the potential with two major case studies. © 2016 The Authors. Concurrency and Computation: Practice and Experience Published by John Wiley & Sons Ltd.     

A Load Balanced Task Scheduling Heuristic for Large-Scale Computing Systems

Optimal task allocation in Large-Scale Computing Systems (LSCSs) that endeavors to balance the load across limited computing resources is considered an NP-hard problem. MinMin algorithm is one of the most widely used heuristic for scheduling tasks on limited computing resources. The MinMin minimizes makespan compared to other algorithms, such as Heterogeneous Earliest Finish Time (HEFT), duplication based algorithms, and clustering algorithms. However, MinMin results in unbalanced utilization of resources especially when majority of tasks have lower computational requirements. In this work we consider a computational model where each machine has certain bounded capacity to execute a predefined number of tasks simultaneously. Based on aforementioned model, a task scheduling heuristic Extended High to Low Load (ExH2LL) is proposed that attempts to balance the workload across the available computing resources while improving the resource utilization and reducing the makespan. ExH2LL dynamically identifies task-to-machine assignment considering the existing load on all machines. We compare ExH2LL with MinMin, H2LL, Improved MinMin Task Scheduling (IMMTS), Load Balanced MaxMin (LBM), and M-Level Suffrage-Based Scheduling Algorithm (MSSA). Simulation results show that ExH2LL outperforms the compared heuristics with respect to makespan and resource utilization. Moreover, we formally model and verify the working of ExH2LL using High Level Petri Nets, Satisfiability Modulo Theories Library, and Z3 Solver.     

High performance real-time scheduling of multiple mixed-criticality functions in heterogeneous distributed embedded systems

The architectures of high-end embedded system have evolved into heterogeneous distributed integrated architectures. The scheduling of multiple distributed mixed-criticality functions in heterogeneous distributed embedded systems is a considerable challenge because of the different requirements of systems and functions. Overall scheduling length (i.e., makespan) is the main concern in system performance, whereas deadlines represent the major timing constraints of functions. Most algorithms use the fairness policies to reduce the makespan in heterogeneous distributed systems. However, these fairness policies cannot meet the deadlines of most functions. Each function has different criticality levels (e.g., severity), and missing the deadlines of certain high-criticality functions may cause fatal injuries to people under this situation. This study first constructs related models for heterogeneous distributed embedded systems. Thereafter, the criticality certification, scheduling framework, and fairness of multiple heterogeneous earliest finish time (F_MHEFT) algorithm for heterogeneous distributed embedded systems are presented. Finally, this study proposes a novel algorithm called the deadline-span of multiple heterogeneous earliest finish time (D_MHEFT), which is a scheduling algorithm for multiple mixed-criticality functions. The F_MHEFT algorithm aims at improving the performance of systems, while the D_MHEFT algorithm tries to meet the deadlines of more high-criticality functions by sacrificing a certain performance. The experimental results demonstrate that the D_MHEFT algorithm can significantly reduce the deadline miss ratio (DMR) and keep satisfactory performance over existing methods.     

Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem

This paper addresses a novel distributed assembly permutation flowshop scheduling problem that has important applications in modern supply chains and manufacturing systems. The problem considers a number of identical factories, each one consisting of a flowshop for part-processing plus an assembly line for product-processing. The objective is to minimize the makespan. To suit the needs of different CPU time and solution quality, we present a mixed integer linear model, three constructive heuristics, two variable neighborhood search methods, and an iterated greedy algorithm. Important problem-specific knowledge is obtained to enhance the effectiveness of the algorithms. Accelerations for evaluating solutions are proposed to save computational efforts. The parameters and operators of the algorithms are calibrated and analyzed using a design of experiments. To prove the algorithms, we present a total of 16 adaptations of other well-known and recent heuristics, variable neighborhood search algorithms, and meta-heuristics for the problem and carry out a comprehensive set of computational and statistical experiments with a total of 810 instances. The results show that the proposed algorithms are very effective and efficient to solve the problem under consideration as they outperform the existing methods by a significant margin.