A performance study of multiprocessor task scheduling algorithms

Multiprocessor task scheduling is an important and computationally difficult problem. A large number of algorithms were proposed which represent various tradeoffs between the quality of the solution and the computational complexity and scalability of the algorithm. Previous comparison studies have frequently operated with simplifying assumptions, such as independent tasks, artificially generated problems or the assumption of zero communication delay. In this paper, we propose a comparison study with realistic assumptions. Our target problems are two well known problems of linear algebra: LU decomposition and Gauss–Jordan elimination. Both algorithms are naturally parallelizable but have heavy data dependencies. The communication delay will be explicitly considered in the comparisons. In our study, we consider nine scheduling algorithms which are frequently used to the best of our knowledge: min–min, chaining, A^*, genetic algorithms, simulated annealing, tabu search, HLFET, ISH, and DSH with task duplication. Based on experimental results, we present a detailed analysis of the scalability, advantages and disadvantages of each algorithm.

Optimal robot task scheduling based on genetic algorithms

Industrial robots should perform complex tasks in the minimum possible cycle time in order to obtain high productivity. The problem of determining the optimum route of a manipulator's end effector visiting a number of task points is similar but not identical to the well-known travelling salesman problem (TSP). Adapting TSP to Robotics, the measure to be optimized is the time instead of the distance. In addition, the travel time between any two points is significantly affected by the choice of the manipulator's configuration. Therefore, the multiple solutions of the inverse kinematics problem should be taken into consideration.In this paper, a method is introduced to determine the optimum sequence of task points visited by the tip of the end effector of an articulated robot and it can be applied to any non-redundant manipulator. This method is based on genetic algorithms and an innovative encoding is introduced to take into account the multiple solutions of the inverse kinematic problem. The results show that the method can determine the optimum sequence of a considerable number of task points for robots up to six-degrees of freedom.     

Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system

We present a multi-heuristic evolutionary task allocation algorithm to dynamically map tasks to processors in a heterogeneous distributed system. It utilizes a genetic algorithm, combined with eight common heuristics, in an effort to minimize the total execution time. It operates on batches of unmapped tasks and can preemptively remap tasks to processors. The algorithm has been implemented on a Java distributed system and evaluated with a set of six problems from the areas of bioinformatics, biomedical engineering, computer science and cryptography. Experiments using up to 150 heterogeneous processors show that the algorithm achieves better efficiency than other state-of-the-art heuristic algorithms.     

Approximation algorithms for general parallel task scheduling

A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for both preemptive and nonpreemptive cases in the general setting. Next we focus on linear array network of m processors. We give an approximation algorithm of ratio O(logm) for nonpreemptive scheduling, and another algorithm of ratio 2 for preemptive scheduling. Finally, we give a nonpreemptive scheduling algorithm of ratio O(log²m) for m×m two-dimensional meshes.     

Hybrid real-coded genetic algorithm for data partitioning in multi-round load distribution and scheduling in heterogeneous systems

Data partitioning and scheduling is one the important issues in minimizing the processing time for parallel and distributed computing system. We consider a single-level tree architecture of the system and the case of affine communication model, for a general m processor system with n rounds of load distribution. For this case, there exists an optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. This is a difficult optimization problem because for a given activation order, we have to first identify the processors that are participating (in the computation process) in every round of load distribution and then obtain the load fractions assigned to them, and the processing time. Hence, in this paper, we propose a real-coded genetic algorithm (RCGA) to solve the optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. RCGA employs a modified crossover and mutation operators such that the operators always produce a valid solution. Also, we propose different population initialization schemes to improve the convergence. Finally, we present a comparative study with simple real-coded genetic algorithm and particle swarm optimization to highlight the advantage of the proposed algorithm. The results clearly indicate the effectiveness of the proposed real-coded genetic algorithm.     

A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks

Efficient task scheduling on heterogeneous distributed computing systems (HeDCSs) requires the consideration of the heterogeneity of processors and the inter-processor communication. This paper presents a two-phase algorithm, called H2GS, for task scheduling on HeDCSs. The first phase implements a heuristic list-based algorithm, called LDCP, to generate a high quality schedule. In the second phase, the LDCP-generated schedule is injected into the initial population of a customized genetic algorithm, called GAS, which proceeds to evolve shorter schedules. GAS employs a simple genome composed of a two-dimensional chromosome. A mapping procedure is developed which maps every possible genome to a valid schedule. Moreover, GAS uses customized operators that are designed for the scheduling problem to enable an efficient stochastic search. The performance of each phase of H2GS is compared to two leading scheduling algorithms, and H2GS outperforms both algorithms. The improvement in performance obtained by H2GS increases as the inter-task communication cost increases.     

Greedy partitioned algorithms for the shortest-path problem

A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Finding single-source paths for sparse graphs is notable because of its definitelack of parallelism-no known algorithms are scalable. Qualitatively, we discuss the close relationships between our algorithm and previous work by Quinn, Chikayama, and others. Performance measurements of variations of the algorithm, implemented both in concurrent and imperative programming languages on a shared-memory multiprocessor, are presented. This quantitative analysis of the algorithms provides insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.Presently at Intel-PCED.     

Genetic programming for prediction and control

The relatively new field of genetic programming has received a lot of attention during the last few years. This is because of its potential for generating functions which are able to solve specific problems. This paper begins with an extensive overview of the field, highlighting its power and limitations and providing practical tips and techniques for the successful application of genetic programming in general domains. Following this, emphasis is placed on the application of genetic programming to prediction and control. These two domains are of extreme importance in many disciplines. Results are presented for an oral cancer prediction task and a satellite attitude control problem. Finally, the paper discusses how the convergence of genetic programming can be significantly speeded up through bulk synchronous model parallelisation.     

A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling

This work presents a novel parallel micro evolutionary algorithm for scheduling tasks in distributed heterogeneous computing and grid environments. The scheduling problem in heterogeneous environments is NP-hard, so a significant effort has been made in order to develop an efficient method to provide good schedules in reduced execution times. The parallel micro evolutionary algorithm is implemented using MALLBA, a general-purpose library for combinatorial optimization. Efficient numerical results are reported in the experimental analysis performed on both well-known problem instances and large instances that model medium-sized grid environments. The comparative study of traditional methods and evolutionary algorithms shows that the parallel micro evolutionary algorithm achieves a high problem solving efficacy, outperforming previous results already reported in the related literature, and also showing a good scalability behavior when facing high dimension problem instances.     

Towards hybrid evolutionary algorithms

Metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. However, the choice of a particular algorithm to optimize a certain problem is still mainly driven by some sort of devotion of its author to a certain technique rather than by a rationalistic choice driven by reason. Hybrid algorithms have shown their ability to provide local optima of high quality. Hybridization of algorithms is still in its infancy: certain combinations of algorithms have experimentally shown their performance, though the reasons of their success is not always really clear. In order to add some rational to these issues, we study the structure of search spaces and attempt to relate it to the performance of algorithms. We wish to explain the behavior of search algorithms with this knowledge and provide guidelines in the design of hybrid algorithms. This paper briefly reviews the current knowledge we have on search spaces of combinatorial optimization problems. Then, we discuss hybridization and present a general classification of the way hybridization can be conducted in the light of our knowledge of the structure of search spaces.     

Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems

The ongoing increase of energy consumption by IT infrastructures forces data center managers to find innovative ways to improve energy efficiency. The latter is also a focal point for different branches of computer science due to its financial, ecological, political, and technical consequences. One of the answers is given by scheduling combined with dynamic voltage scaling technique to optimize the energy consumption. The way of reasoning is based on the link between current semiconductor technologies and energy state management of processors, where sacrificing the performance can save energy.This paper is devoted to investigate and solve the multi-objective precedence constrained application scheduling problem on a distributed computing system, and it has two main aims: the creation of general algorithms to solve the problem and the examination of the problem by means of the thorough analysis of the results returned by the algorithms.The first aim was achieved in two steps: adaptation of state-of-the-art multi-objective evolutionary algorithms by designing new operators and their validation in terms of performance and energy. The second aim was accomplished by performing an extensive number of algorithms executions on a large and diverse benchmark and the further analysis of performance among the proposed algorithms. Finally, the study proves the validity of the proposed method, points out the best-compared multi-objective algorithm schema, and the most important factors for the algorithms performance.     

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.     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

Generating subproblems in branch and bound algorithms for parallel machines scheduling problem

A branch and bound algorithm (B&B) has been widely used in various discrete and combinatorial optimization fields. To obtain optimal solutions as soon as possible for scheduling problems, three tools, which are branching, bounding and dominance rules, have been developed in the B&B algorithm. One of these tools, a branching is a method for generating subproblems and directly determines size of solution to be searched in the B&B algorithm. Therefore, it is very important to devise effective branching scheme for the problem.In this note, a survey of branching schemes is performed for parallel machines scheduling (PMS) problems with n independent jobs and m machines and new branching schemes that can be used for identical and unrelated PMS problems, respectively, are suggested. The suggested branching methods show that numbers of generated subproblems are much smaller than that of other methods developed earlier and therefore, it is expected that they help to reduce a lot of CPU time required to obtain optimal solutions in the B&B algorithm.     

A survey of genetic algorithms for solving multi depot vehicle routing problem

This article presents a survey of genetic algorithms that are designed for solving multi depot vehicle routing problem. In this context, most of the articles focus on different genetic approaches, methods and operators, commonly used in practical applications to solve this well-known and researched problem. Besides providing an up-to-date overview of the research in the field, the results of a thorough experiment are presented and discussed, which evaluated the efficiency of different existing genetic methods on standard benchmark problems in detail. In this manner, the insights into strengths and weaknesses of specific methods, operators and settings are presented, which should help researchers and practitioners to optimize their solutions in further studies done with the similar type of the problem in mind. Finally, genetic algorithm based solutions are compared with other existing approaches, both exact and heuristic, for solving this same problem.     

A review of procedures to evolve quantum algorithms

There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attributed to the non-intuitive nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into evolving quantum algorithms has shown promise. This paper provides an introduction into quantum and evolutionary algorithms for the computer scientist not familiar with these fields. The exciting field of using evolutionary algorithms to evolve quantum algorithms is then reviewed.

Multiprocessor scheduling using mean-field annealing

This paper presents our work on the static task scheduling model using the mean-field annealing (MFA) technique. Meanfield annealing is a technique of thermostatic annealing that takes the statistical properties of particles as its learning paradigm. It combines good features from the Hopfield neural network and simulated annealing, to overcome their weaknesses and improve on their performances. Our MFA model for task scheduling is derived from its prototype, namely, the graph partitioning problem. MFA is deterministic in nature and this has the advantage of faster convergence to the equilibrium temperature, compared to simulated annealing. Our experimental work verifies this finding, besides making comparison on the effectiveness of the model on various network and task graph sizes. Our work also includes the simulation of the MFA model on several network topologies using varying parameters. The MFA simulation model is targeted on nonpreemptive and precedence-related tasks with communication costs.     

Flowshop scheduling problem with a batching machine and task compatibilities

This paper deals with the problem of task scheduling in a flowshop with two (discrete and batching) machines. Each task has to be processed by both machines. All tasks visit the machines in the same order. The first machine is a discrete machine that can process no more than one task at a time, and the second machine is a batching machine that can process several tasks per batch with the additional feature that the tasks of the same batch have to be compatible. A compatibility relation is defined between each pair of tasks, so that an undirected compatibility graph is obtained which turns out to be an interval graph. The batch processing time is equal to the maximal processing time of the tasks in this batch and all tasks of the same batch start and finish together. The aim is to make batching and sequencing decisions and minimize the makespan.