No-wait scheduling in single-hop multi-channel LANs

An extended version of the multiprocessor machine scheduling problem with makespan objective, which arises from single-hop multi-channel LANs, is presented in this paper. In this scheduling model, each job consists of two operations, and each operation may be processed by anyone of a given set of machines, while in the job shop scheduling problem, such a set contains only one machine. For this NP-complete problem, we first analyze the performance ratios of two simple strategies, List Scheduling and Longest Processing Time First, for the off-line cases, which have performance ratios (5/2−1/2m) and (2+1/2(m+1)), respectively, with (m+1) being the number of the machines. We also show that the competitive ratio of the List Scheduling strategy for the on-line cases is (7/2−1/2m).     

Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization

An efficient method based on particle swarm optimization (PSO) is developed to solve the Multiprocessor Task Scheduling Problem (MPTSP). To efficiently execute parallelized programs on a multiprocessor environment, a scheduling problem must be solved to determine the assignment of tasks to the processors, the execution order of the tasks, and the starting time of each task, such that some optimality criteria are met. The scheduling problem is known as an NP-complete problem even when the target processors are fully connected and no communication delay is considered among the tasks in the task graph. The complexity of the scheduling problem depends on the number of tasks (N), the number of processors (M), the task processing time and the precedence constraints. The Directed Acyclic Graph (DAG) was exploited to represent the tasks and their precedence constraints. The proposed algorithm was compared with the Genetic Algorithm (GA) and the Duplication Scheduling Heuristic (DSH). We also provide a systematic investigation on the effect of varying problem settings. The results show that the proposed algorithm could not outperform the DSH while it could outperform the GA in some cases.     

Optimal Time-Critical Scheduling via Resource Augmentation

Abstract. We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

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 new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria

We consider the multiprocessor scheduling problem in which independent jobs are scheduled on identical parallel machines, with the objective of minimizing the normalized sum of square for workload deviations (NSSWD) criterion in order to obtain workload balancing. NSSWD and other criteria for the related problem of number partitioning are presented from a statistical viewpoint, which allows to derive some insightful connections with statistical measures of dispersion. A new local search algorithm is also developed. The algorithm at first generates and merges a set of partial solutions in order to obtain a feasible solution for the multiprocessor scheduling problem. Then a set of interchange procedures are utilized in order to improve the solution. The effectiveness of this approach is evaluated by solving a large number of benchmark instances.     

Controlling the data space of tree structured computations

We study the problem of scheduling a parallel computation so as to minimize the maximum number of data items extant at any point in the execution. Computations are expressed as directed graphs, where nodes represent primitive operations and arcs represent data dependences. The result of an operation is extant after the operation executes and until all immediate successors have begun execution. Our goal is to schedule computations so as to minimize both the maximum space required for extant data and the overall completion time.The classical problem of multiprocessor scheduling with precedence constraints is a special case of our problem, obtained by disregarding the data-space constraint. This special case is NP-complete for general graphs; a time-optimal multiprocessor scheduling algorithm is known only for the class of arbitrary trees. For this same class of arbitrary trees we present a multiprocesssor scheduling algorithm where the completion time is optimal within a constant factor, while the data-space size exceeds the optimal by a factor not greater than the number of processors.For an arbitrary n-node precedence tree T of in-degree Δ, we present:

(1)an algorithm for evaluating the lower bound on the size of data space required for executing T, regardless of the completion time or number of processors;

(2)a proof that the lower bound of Part 1 may be as large as (Δ−1)lgn but not larger;

(3)a single-processor schedule that executes T in time that equals the optimal, while creating the data space of size equal to the lower bound of Part 1;

(4)an ω-processor schedule that executes T in time not exceeding three times the optimal, while creating the data space of size that exceeds the lower bound of Part 1 by a factor not greater than ω.

(5)a proof that for every number of processors ω and for every 0<ε1, there exist infinitely many trees such that every ω-processor schedule that executes any of these trees in time not exceeding (2−ε) times the optimal requires a token space as large as that created by the schedule of Part 4, while the schedule of Part 4 executes every such tree in optimal time.

The family of complete binary trees provides an example where our schedule achieves an exponential improvement in the size of the data space, compared to that of the classical time-optimal schedule.     

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints

Abstract. Modern computer systems distribute computation among several machines to speed up the execution of programs. Yet, setup and communication costs, as well as parallelism constraints, bound the number of machines that can share the execution of a given application, and the number of machines by which it can be processed simultaneously . We study the resulting scheduling problem, stated as follows. Given a set of n jobs and m uniform machines, assign the jobs to the machines subject to parallelism and machine allotment constraints, such that the overall completion time of the schedule (or makespan ) is minimized. Indeed, the multiprocessor scheduling problem (where each job can be processed by a single machine) is a special case of our problem; thus, our problem is strongly NP-hard. We present a (1+ α) -approximation algorithm for this problem, where α ∈ (0,1] depends on the minimal number of machine allotments and the minimal parallelism allowed for any job. Also, we show that when the maximal number of machines that can share the execution of a job is some fixed constant, our problem has a polynomial time approximation scheme ; for other special cases we give optimal polynomial time algorithms. Finally, through the relation of our problem to the classic preemptive scheduling problem on multiple machines, we shed some fresh light on what is known in scheduling folklore as the power of preemption.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

Multiprocessor scheduling by generalized extremal optimization

We propose a solution of the multiprocessor scheduling problem based on applying a relatively new metaheuristic technique, called Generalized Extremal Optimization (GEO). GEO is inspired by a simple coevolutionary model known as the Bak–Sneppen model. The model describes an ecosystem consisting of N species. Evolution in this model is driven by a process in which the weakest species in the ecosystem, together with its nearest neighbors, is always forced to mutate. This process shows the characteristics of a phenomenon called punctuated equilibrium, which is observed in evolutionary biology. We interpret the multiprocessor scheduling problem in terms of the Bak–Sneppen model and apply the GEO algorithm to solve the problem. We show that the proposed optimization technique is simple and yet outperforms genetic algorithm-based and swarm algorithm-based approaches to the multiprocessor scheduling problem.     

Scheduling in and out forests in the presence of communicationdelays

We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961; however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m-2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum     

Scheduling Independent Multiprocessor Tasks

Abstract. We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.     

Scheduling tasks of multi-join queries in a multiprocessor

This paper deals with the problem of scheduling spawned tasks when a query is issued to a database which resides on a MIMD multiprocessor. These tasks have the property that their associated dependency scheme can be presented as a directed tree. We present a theoretical framework with extensive experimental simulations which increase the throughput of database applications. We derive a family of algorithms for scheduling tasks. Their performance is tested on several common multiprocessor configurations. For better performance the adaptation of the scheduling algorithm to the multiprocessor configuration is examined and analyzed. The scheduling algorithms are divided into two cases: (a) permitted changes in the resources connection scheme of the multiprocessor, and (b) no changes allowed. The algorithms are scalable and their complexity is computed. In particular, we present an algorithm for scheduling tasks in the case where the construction of a central storage location is permitted. One of the main tools for the construction of the above algorithms is the notion of (t, 1)-domination and k-domination sets. Copyright © 1999 John Wiley & Sons, Ltd.     

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p _ij of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected time at which all of the jobs are completed.     

最小化提前和延误惩罚的批处理问题

考虑机器容量有限的同时加工排序问题, 为享有公共交货期窗口[e; d]的n个工件分批并排序以最小化总的赋权提前/延误惩罚. 本文把窗时排序与同时加工排序结合起来研究, 假设每个批的容量是b(< n, 其中n为工件的个数), 而且最早交货期e 和最晚交货期d已知. 但该问题是NP–完备的, 首先给出最优排序的几条性质, 进而解决了两类特殊情况.     

Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems

Scheduling program tasks on processors is at the core of the efficient use of multiprocessor systems. Most task-scheduling problems are known to be NP-Hard and, thus, heuristics are the method of choice in all but the simplest cases. The utilization of acknowledged sets of benchmark-problem instances is essential for the correct comparison and analysis of heuristics. Yet, such sets are not available for several important classes of scheduling problems, including multiprocessor scheduling problem with communication delays (MSPCD) where one is interested in scheduling dependent tasks onto homogeneous multiprocessor systems, with processors connected in an arbitrary way, while explicitly accounting for the time required to transfer data between tasks allocated to different processors. We propose test-problem instances for the MSPCD that are representative in terms of number of processors, type of multiprocessor architecture, number of tasks to be scheduled, and task graph characteristics (task execution times, communication costs, and density of dependencies between tasks). Moreover, we define our task-graph generators in a way appropriate to ensure that the corresponding problem instances obey the theoretical principles recently proposed in the literature.     

Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor Assignment

We consider the schedulability of a set of independent periodic tasks under fixed priority preemptive scheduling on homogeneous multiprocessor systems. Assuming there is no task migration between processors and each processor schedules tasks preemptively according to fixed priorities assigned by the Rate Monotonic policy, the scheduling problem reduces to assigning the set of tasks to disjoint processors in such a way that the Monotonic policy, the scheduling problem reduces to assigning the set of tasks to disjoint processors in such a way that the schedulability of the tasks on each processor can be guaranteed. In this paper we show that the worst case achievable utilization for such systems is between n(2^1/2-1) and (n+1)/(1+2^1/(n+1)), where n stands for the number of processors. The lower bound represents 41 percent of the total system capacity and the upper bound represents 50 to 66 percent depending on n. Practicality of the lower bound is demonstrated by proving it can be achieved using a First Fit scheduling algorithm.     

Bicriteria approximation algorithms for scheduling problems with communications delays

We study the problem of simultaneously minimizing the makespan and the average weighted completion time for the precedence multiprocessor constrained scheduling problem with unit execution times and unit communication delays, known as the UET–UCT problem (Munier and König, Operations Research, 45(1), 145–148 (1997)). We propose a simple (16/9, 16/9)-approximation algorithm for the problem with an unrestricted number of machines. We improve our algorithm by adapting a technique first introduced by Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999) and provide a (1.745, 1.745)-approximate solution. For the considered scheduling problem, we prove the existence of a (1.445, 1.445)-approximate solution, improving the generic existence result of Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999). Also notice that our results for the case of an unrestricted number of processors hold for the more general scheduling problem with small communication delays (SCT problem), and for two other classical optimality criteria: maximum lateness and weighted lateness. Finally, we propose an approximation algorithm for the UET–UCT problem with a restricted number of processors.Research partially supported by the thematic network APPOL II (IST 2001-32007) of the European Union, the ACI-GRID2 project of the French government, and the MULT-APPROX project of the France-Berkeley Fund.     

Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Technique

Most scheduling applications have been demonstrated as NP-complete problems. A variety of schemes are introduced in solving those scheduling applications, such as linear programming, neural networks, and fuzzy logic. In this paper, a new approach of first analogising a scheduling problem to a clustering problem and then using a fuzzy Hopfield neural network clustering technique to solve the scheduling problem is proposed. This fuzzy Hopfield neural network algorithm integrates fuzzy c-means clustering strategies into a Hopfield neural network. This investigation utilises this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration and constrained times (execution time and deadline). Each process is regarded as a data sample, and every processor is taken as a cluster. Simulation results illustrate that imposing the fuzzy Hopfield neural network onto the proposed energy function provides an appropriate approach to solving this class of scheduling problem.       

Three-partitioning containing kernels: Complexity and heuristic

LetG= $\{ g_1 ,g_2 , \cdots ,g_m \} \cup \{ t_1 ,t_2 , \cdots ,t_n \} $ be a list of items with nonnegative weights assigned andk≥2 be an integer. The objective is to find an assignment of the items to the bins such that allg _i (called kernels) are assigned to different bins, such that no bin contains more thank items, and such that the maximum weight assigned to any bin becomes minimum. In this paper, we first prove that the problem is NP-complete in the strong sense for anyk≥3. As heuristic for this problem, we use a modified version of the famous LPT-algorithm for multiprocessor scheduling, and we show a worst case bound of 3/2–1/2m fork=3.     

Theoretical aspects of multicriteria flight gate scheduling: deterministic and fuzzy models

This paper addresses the airport flight gate scheduling problem with multiple objectives. The objectives are to maximize the total flight gate preferences, to minimize the number of towing activities, and to minimize the absolute deviation of the new gate assignment from a so-called reference schedule. The problem examined is a multicriteria multi-mode resource-constrained project scheduling problem with generalized precedence constraints or time windows. While in previous approaches the problem has been simplified to a single objective counterpart, we tackle it directly by a multicriteria metaheuristic, namely Pareto Simulated Annealing, in order to get a representative approximation of the Pareto front. Possible uncertainty of input data is treated by means of fuzzy numbers.