Abstract Scheduling is essentially a decision-making process that enables resource sharing among a number of activities by determining their execution order on the set of available resources. The emergence of distributed systems brought new challenges on scheduling in computer systems, including clusters, grids, and more recently clouds. On the other hand, the plethora of research makes it hard for both newcomers researchers to understand the relationship among different scheduling problems and strategies proposed in the literature, which hampers the identification of new and relevant research avenues. In this paper we introduce a classification of the scheduling problem in distributed systems by presenting a taxonomy that incorporates recent developments, especially those in cloud computing. We review the scheduling literature to corroborate the taxonomy and analyze the interest in different branches of the proposed taxonomy. Finally, we identify relevant future directions in scheduling for distributed systems.
Kwok and Ahmad @cite_141 survey static scheduling algorithms for allocating tasks connected as directed task graphs (DAGs) into multiprocessors. The authors presented a simplified taxonomy for approaches to the problem, as well as the description and classification of @math scheduling algorithms. The DAG scheduling algorithms for multiprocessors have been adapted for scheduling in distributed systems, incorporating intrinsic characteristics of such systems for an enhanced performance. Therefore, Kwok and Ahmad presented static scheduling algorithms for multiprocessors, which are also applicable to distributed systems, and their classification. In this paper we review extensions of those algorithms as well as the their classification by including heterogeneous systems, dynamic scheduling algorithms, scheduling algorithms in modern distributed environments, and new scheduling techniques.
@cite_141
2040466547 2167931842 2087376002 1958965543
Static scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP-complete problem in general, researchers have resorted to devising efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graph-theory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling mapping functionalities. In a heterogeneous system, the efficient exploitation of parallelism requires scheduling strategies that account for heterogeneity among processors to achieve an effective mapping of computations to processors. The paper presents a scheduling heuristic specialized for heterogeneous multiprocessor systems which make use of several different types of processors. The new algorithm is based on the greedy strategy: no processor remains idle if there is some task available that it could process. A graph called the classified typed task graph is used to describe the current status of tasks of different types at each scheduling step. With the graph, the algorithm dynamically evaluates the priorities of tasks only when there are multiply executable candidates, and then schedules an appropriate one onto the currently available processors of the corresponding type. A preliminary evaluation shows that this algorithm has promising performance. > A scheduling policy strongly influences the performance of a manufacturing system. However, the design of an effective scheduling policy is complicated and time consuming due to the complexity of each scheduling decision, as well as the interactions among these decisions. This paper develops four new multi-objective genetic programming-based hyperheuristic (MO-GPHH) methods for automatic design of scheduling policies, including dispatching rules and due-date assignment rules in job shop environments. In addition to using three existing search strategies, nondominated sorting genetic algorithm II, strength Pareto evolutionary algorithm 2, and harmonic distance-based multi-objective evolutionary algorithm, to develop new MO-GPHH methods, a new approach called diversified multi-objective cooperative evolution (DMOCC) is also proposed. The novelty of these MO-GPHH methods is that they are able to handle multiple scheduling decisions simultaneously. The experimental results show that the evolved Pareto fronts represent effective scheduling policies that can dominate scheduling policies from combinations of existing dispatching rules with dynamic regression-based due-date assignment rules. The evolved scheduling policies also show dominating performance on unseen simulation scenarios with different shop settings. In addition, the uniformity of the scheduling policies obtained from the proposed method of DMOCC is better than those evolved by other evolutionary approaches. Scheduling computation tasks on processors is the key issue for high-performance computing. Although a large number of scheduling heuristics have been presented in the literature, most of them target only homogeneous resources. The existing algorithms for heterogeneous domains are not generally efficient because of their high complexity and or the quality of the results. We present two low-complexity efficient heuristics, the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm for scheduling directed acyclic weighted task graphs (DAGs) on a bounded number of heterogeneous processors. We compared the performances of these algorithms against three previously proposed heuristics. The comparison study showed that our algorithms outperform previous approaches in terms of performance (schedule length ratio and speedup) and cost (time-complexity).