On multiprocessor task scheduling using efficient state space search approaches

Obtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A^* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable.     

Branch-and-bound task allocation with task clustering-based pruning

We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state–space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state–space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state–space searching approach feasible for practical use.     

Enhancing CLP branch and bound techniques for scheduling problems

In this paper, we propose a constraint logic programming (CLP) approach to the solution of a job shop scheduling problem in the field of production planning in orthopaedic hospital departments. A pure CLP on finite domain (CLP(FD)) approach to the problem has been developed, leading to disappointing results. In fact, although CLP(FD) has been recognized as a suitable tool for solving combinatorial problems, it presents some drawbacks for optimization problems. The main reason concerns the fact that CLP(FD) solvers do not effectively handle the objective function and cost‐based reasoning through the simple branch and bound scheme they embed. Therefore, we have proposed an improvement of the standard CLP branch and bound algorithm by exploiting some well‐known operations research results. The branch and bound we integrate in a CLP environment is based on the optimal solution of a relaxation of the original problem. In particular, the relaxation used for the job shop scheduling problem considered is the well‐known shifted bottleneck procedure considering single machine problems. The idea is to decompose the original problem into subproblems and solve each of them independently. Clearly, the solutions of each subproblem may violate constraints among different subproblems which are not taken into account. However, these solutions can be exploited in order to improve the pruning of the search space and to guide the search by defining cost‐based heuristics. The resulting algorithm achieves a significant improvement with respect to the pure CLP(FD) approach that enables the solution of problems which are one order of magnitude greater than those solved by a pure CLP(FD) algorithm. In addition, the resulting code is less dependent on the input data configuration. Copyright © 2001 John Wiley & Sons, Ltd.     

A genetic algorithm for the design space exploration of datapaths during high-level synthesis

High-level synthesis is comprised of interdependent tasks such as scheduling, allocation, and module selection. For today's very large-scale integration (VLSI) designs, the cost of solving the combined scheduling, allocation, and module selection problem by exhaustive search is prohibitive. However, to meet design objectives, an extensive design space exploration is often critical to obtaining superior designs. We present a framework for efficient design space exploration during high-level synthesis of datapaths for data-dominated applications. The framework uses a genetic algorithm (GA) to concurrently perform scheduling and allocation with the aim of finding schedules and module combinations that lead to superior designs while considering user-specified latency and area constraints. The GA uses a multichromosome representation to encode datapath schedules and module allocations and efficient heuristics to minimize functional and storage area costs, while minimizing circuit latencies. The framework provides the flexibility to perform resource-constrained scheduling, time-constrained scheduling, or a combination of the two, using a simple and fast list-scheduling technique. A graded penalty function is used as an objective function in evaluating the quality of designs to enable the GA to quickly reach areas of the search space where designs meeting user specified criteria are most likely to be found. Since GAs are population-based search heuristics, a unique feature of our framework is its ability to offer a large number of alternative datapath designs, all of which meet design specifications but differ in module, register, and interconnect configurations. Many experiments on well-known benchmarks show the effectiveness of our approach.     

On parallelizing the multiprocessor scheduling problem

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size     

An Integrated Technique for Task Matching and Scheduling onto Distributed Heterogeneous Computing Systems

This paper presents a problem-space genetic algorithm (PSGA)-based technique for efficient matching and scheduling of an application program that can be represented by a directed acyclic graph, onto a mixed-machine distributed heterogeneous computing (DHC) system. PSGA is an evolutionary technique that combines the search capability of genetic algorithms with a known fast problem-specific heuristic to provide the best-possible solution to a problem in an efficient manner as compared to other probabilistic techniques. The goal of the algorithm is to reduce the overall completion time through proper task matching, task scheduling, and inter-machine data transfer scheduling in an integrated fashion. The algorithm is based on a new evolutionary technique that embeds a known problem-specific fast heuristic into genetic algorithms (GAs). The algorithm is robust in the sense that it explores a large and complex solution space in smaller CPU time and uses less memory space as compared to traditional GAs. Consequently, the proposed technique schedules an application program with a comparable schedule length in a very short CPU time, as compared to GA-based heuristics. The paper includes a performance comparison showing the viability and effectiveness of the proposed technique through comparison with existing GA-based techniques.     

Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems

Consider directed acyclic graph (DAG) scheduling for a large heterogeneous system, which consists of processors with varying processing capabilities and network links with varying bandwidths. The search space of possible task schedules for this problem is immense. One possible approach for this optimization problem, which is NP-hard, is to start with the best task schedule found by a fast deterministic task scheduling algorithm and then iteratively attempt to improve the task schedule by employing a general random guided search method. However, such an approach can lead to extremely long search times, and the solutions found are sometimes not significantly better than those found by the original deterministic task scheduling algorithm. In this paper, we propose an alternative strategy, termed Push-Pull, which starts with the best task schedule found by a fast deterministic task scheduling algorithm and then iteratively attempts to improve the current best solution using a deterministic guided search method. Our simulation results show that given similar runtimes, the Push-Pull algorithm performs well, achieving results similar to or better than all of the other algorithms being compared.     

A knowledge-based approach for task allocation in heterogeneous distributed computer systems

Abstract: This paper presents a knowledge-based system for task allocation in a network of processors. Since the problem is NP-complete, optimisation techniques are computationally prohibitive and impractical. Our approach reduces computational burden by using (1) a two-level hierarchical scheduling model to alleviate the problem complexity, and (2) a search strategy that uses knowledge from the knowledge base to limit the search space to a manageable size. The major goal of our approach is to generate good but not necessarily optimal solutions quickly. The system is implemented on a Sun SPARCstation 1 + using Common Lisp. Our computational experience in using this system for task allocation indicates that the two-level hierarchical approach generates better schedules in shorter computational time than a non-hierarchical approach.     

Optimal Compile-Time Multiprocessor Scheduling Based on the O–1 Linear Programming Algorithm with the Branch and Bound Technique

The problem of exploiting the effective utilization of a multiprocessor system essentially depends on optimal scheduling of parallel tasks onto the processors in the system. A recently proposed compile-time scheduling algorithm based on the 0–1 linear programming algorithm with the branch and bound technique, to produce optimal schedules, has the problems of communication link contention, nonoptimality, and modeling incompletely connected processor systems. In this paper, we present a modified version of this algorithm for producing contention-free optimal schedules for any arbitrary multiprocessor topology. To alleviate the impediments of large requirements of CPU time for the optimal scheduling algorithm, we have developed three new effective techniques, namely,processor isomorphism, look ahead pruning, andlower bound on the completion time of tasks. The performance of our algorithm is analyzed using DFT and LU decomposition methods as benchmarks.     

A two-phase scheduling method with the consideration of task clustering for earth observing satellites

Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems. Although extensive scheduling algorithms have been proposed for the satellite observation scheduling problem (SOSP), the task clustering strategy has not been taken into account up to now. This paper presents a novel two-phase based scheduling method with the consideration of task clustering for solving SOSP. This method comprises two phases: a task clustering phase and a task scheduling phase. In the task clustering phase, we construct a task clustering graph model and use an improved minimum clique partition algorithm to obtain cluster-tasks. In the task scheduling phase, based on overall tasks and obtained cluster-tasks, we construct an acyclic directed graph model and utilize a hybrid ant colony optimization coming with a mechanism of local search, called ACO–LS, to produce optimal or near optimal schedules. Extensive experimental simulations demonstrate the efficiency of the proposed scheduling method.     

Pruning by dominance in best-first search for the job shop Scheduling problem with total flow time

Best-First search is a problem solving paradigm that allows to design exact or admissible algorithms. In this paper, we confront the Job Shop Scheduling problem with total flow time minimization by means of the A ^* algorithm. We devised a heuristic from a problem relaxation that relies on computing Jackson’s preemptive schedules. In order to reduce the effective search space, we formalized a method for pruning nodes based on dominance relations and established a rule to apply this method efficiently during the search. By means of experimental study, we show that the proposed method is more efficient than a genetic algorithm in solving instances with 10 jobs and 5 machines and that pruning by dominance allows A ^* to reach optimal schedules, while these instances are not solved by A ^* otherwise. These experiments have also made it clear that the Job Shop Scheduling problem with total flow time minimization is harder to solve than the same problem with makespan minimization.     

Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networks

We develop an optimal task allocation and scheduling algorithm which minimizes the computing period for multiprocessor systems with general network structures considering task execution time and communication contentions and routing delays explicitly. We presented new ideas of scheduling: (i) individual start allowing overlapping two different iterations, (ii) the scheduling space and the scheduling graph representing feasible schedules, and (iii) the check-and-diffusion algorithm utilizing property of the start-time difference vs. the computing period. With concrete examples of scheduling spaces, segments, and schedules for various multiprocessor network architectures, we showed that individual start reduces the computing period, and our algorithm can find the optimal computing period without exhaustive search.     

Expert system for scheduling in an airline gate allocation

Scheduling is an important technique encompassing a wide application area. Because of the complex interrelations among the resources, knowledge, and various other constraints, scheduling has many difficulties. Artificial Intelligence technology has been applied to solve the scheduling problem. As AI techniques are efficient in representing knowledge and dealing with heuristics, it is an adequate approach to model and to solve scheduling problems. We have implemented the ramp scheduling system, called RACES (Ramp Activity Coordination Expert System), to solve complex and dynamic aircraft parking problems. RACES was developed from the domain knowledge and experience which were acquired from the domain experts. Domain knowledge and experience are important factors in controlling the scheduling procedure. RACES divides the problem into sub-problems and experimental heuristics in the knowledge acquisition process. The system independently processes scheduling for the divided sub-problems and shares variables and domains. During the scheduling, the system selects or confines the search space with domain filtering techniques by exploiting the characteristics of various constraints and knowledge. RACES produces a user-driven near-optimal solution by means of a trade-off scheduling method using heuristics between the size of aircraft and the best-fit time. For 400 daily flights, RACES made parking schedules for aircraft in about 20 s compared with 4–5 h by human experts.     

Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops

We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules.     

The Machine Duplication Problem in a Job Shop with Two Jobs

This paper addresses a problem related to the classical job shop scheduling problem with two jobs. The problem consists in concurrently determining the best subset of machines to be duplicated and the optimal scheduling of the operations in order to minimize completion time. Such a problem arises in the tool management for a class of flexible manufacturing cells. The job shop with two jobs is first reviewed, the application of the classical search algorithm A* to this problem is discussed and its performance compared with a previous approach. The complexity of the machine duplication problem is then analysed. The problem is proved to be in general NP-hard in the strong sense, but in a class of special cases, relevant from the applications viewpoint, it can be solved in polynomial time by a dynamic programming algorithm. A heuristic based on such an algorithm and on A* is proposed for the general problem; the results are satisfactory in terms of both efficiency and quality of the solution.     

Task clustering and scheduling for distributed memory parallelarchitectures

This paper addresses the problem of scheduling parallel programs represented as directed acyclic task graphs for execution on distributed memory parallel architectures. Because of the high communication overhead in existing parallel machines, a crucial step in scheduling is task clustering, the process of coalescing fine grain tasks into single coarser ones so that the overall execution time is minimized. The task clustering problem is NP-hard, even when the number of processors is unbounded and task duplication is allowed. A simple greedy algorithm is presented for this problem which, for a task graph with arbitrary granularity, produces a schedule whose makespan is at most twice optimal. Indeed, the quality of the schedule improves as the granularity of the task graph becomes larger. For example, if the granularity is at least 1/2, the makespan of the schedule is at most 5/3 times optimal. For a task graph with n tasks and e inter-task communication constraints, the algorithm runs in O(n(n lg n+e)) time, which is n times faster than the currently best known algorithm for this problem. Similar algorithms are developed that produce: (1) optimal schedules for coarse grain graphs; (2) 2-optimal schedules for trees with no task duplication; and (3) optimal schedules for coarse grain trees with no task duplication     

一种面向在线查询的拼写纠错算法

搜索引擎中,在线拼写纠错根据用户查询输入补全用户查询,并给出正确的拼写建议。提出了一种面向查询补全的在线拼写纠错算法。基于真实查询的噪声信道转换方式,算法建立了用户查询输入的生成模型;利用拼写纠错对,算法采用期望最大化算法训练能捕获用户误拼行为的马尔科夫N语法转换模型;算法采用不同剪枝策略的启发式改进A*搜索算法以实现实时给出纠错补全建议。实验结果表明,提出的算法相比其他同类算法更有效。     

A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems

To handle scheduling of tasks on heterogeneous systems, an algorithm is proposed to reduce execution time while allowing for maximum parallelization. The algorithm is based on multi-objective scheduling cuckoo optimization algorithm (MOSCOA). In this algorithm, each cuckoo represents a scheduling solution in which the ordering of tasks and processors allocated to them are considered. In addition, the operators of cuckoo optimization algorithm means laying and immigration are defined so that it is usable for scheduling scenario of the directed acyclic graph of the problem. This algorithm adapts cuckoo optimization algorithm operators to create proper scheduling in each stage. This ensures avoiding local optima while allowing for global search within the problem space for accelerating the finding of a global optimum and delivering a relatively optimized scheduling with the least number of repetitions. Moving toward global optima is done through a target immigration operator in this algorithm and schedules in each repetition are pushed toward optimized schedules to secure global optima. The results of MOSCOA implementation on a large number of random graphs and real-world application graphs with a wide range characteristics show MOSCOA superiority over the previous task scheduling algorithms.     

Scheduling precedence constrained task graphs with non-negligibleintertask communication onto multiprocessors

The multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence constrained task graph (representing a parallel program) onto the processors of a multiprocessor in a way that minimizes the completion time. Since this problem is known to be NP-hard in the strong sense in all but a few very restricted eases, heuristic algorithms are being developed which obtain near optimal schedules in a reasonable amount of computation time. We present an efficient heuristic algorithm for scheduling precedence constrained task graphs with nonnegligible intertask communication onto multiprocessors taking contention in the communication channels into consideration. Our algorithm for obtaining satisfactory suboptimal schedules is based on the classical list scheduling strategy. It simultaneously exploits the schedule-holes generated in the processors and in the communication channels during the scheduling process in order to produce better schedules. We demonstrate the effectiveness of our algorithm by comparing with two competing heuristic algorithms available in the literature     

Evolutionary algorithms for scheduling m-machine flow shop with lot streaming

This paper addresses the problem of making sequencing and scheduling decisions for n jobs–m-machines flow shops under lot sizing environment. Lot streaming (Lot sizing) is the process of creating sub lots to move the completed portion of a production sub lots to down stream machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. Evolutionary algorithms that belong to search heuristics find more applications in recent research. Genetic algorithm (GA) and hybrid genetic algorithm (HEA) also known as hybrid evolutionary algorithm fall under evolutionary heuristics. On this concern this paper proposes two evolutionary algorithms namely, GA and HEA to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and set-up time. The following two algorithms are used to evaluate the performance of the proposed GA and HEA: (i) Baker's algorithm (BA), an optimal solution procedure for two-machine flow shop problem with lot streaming and makespan objective criterion and (ii) simulated annealing algorithm (SA) for m-machine flow shop problem with lot streaming and makespan and total flow time criteria.