In Distributed Real-Time Systems (DRTSs), computation and communication are the main operations contained in activities. The timeliness of activities depends on that of computations and communications. Furthermore, the timeliness of computations relies on that of communications, and vice versa. Hence, the interplay between computation and communication is inherently a key factor in determining the timeliness of activities. This paper proposes a class of general utility functions under the utility accrual model UAM+to capture and characterize this interplay. Accordingly, a technique called Dynamic Deadline Adjustment (DDA) is proposed to fully explore such interplay and help resource managers proceed toward utility accrual. An online algorithm called IDRSA, which integrates the DDA technique, is developed to perform resource scheduling for DRTSs. IDRSA adopts a two-level scheduling framework to decompose resource scheduling into subprocesses and distribute them to processing nodes so as to reduce the cost of resource scheduling through parallel processing. In addition, IDRSA incorporates a new data structure called testing interval tree to effectively reduce the costs of schedulability tests for tasks and messages. Simulation results reveal the effectiveness of IDRSA, especially when the load of computation is heavy and/or the interplay between computation and communication is tight.

In distributed real-time systems, both computation and communication are critical factors. The timeliness of activities relies on both the computation and the communication involved in them. Moreover, the timeliness of computation relies on that of communication, and vice versa. This property requires that both computation and communication be integrated into the resource allocation model and that the model be able to capture the interplay between them. Unfortunately, the utility/benefit/value accrual models employed in current distributed real-time systems are constructed solely on computation. They are inadequate for capturing the interplay between computation and communication. This paper extends previous research on utility-based model by proposing a new utility accrual model, which integrates both computation and communication. Most importantly, the interplay between computation and communication is fully characterized in the model. Under the new model, resource managers are guided towards maximizing system-wide utility by exploring the interplay between computation and communication instead of traditional meeting the timing constraint on computation and the deadline of communication separately. To validate the effectiveness of this model, a resource allocation algorithm called CAUASA is developed under it. The performance of CAUASA is compared to that of another resource allocation algorithm that is developed according to existing utility accrual models. Simulation results reveal that CAUASA is far superior to its counterpart. Therefore, the new utility accrual model provides a more effective framework for the resource allocation in distributed real-time systems.

In real-time systems, the efficiency of scheduling modules (SM) is of critical importance. While efficient algorithms result in efficient SMs, this will not occur without appropriate implementations of the algorithms. Moreover, an algorithm with good implementation could further improve the efficiency of the SM. Therefore, creative implementations of algorithms are well worthy of exploring. In this paper, we propose novel data structures (i.e., testing interval trees (TIT)) to help build efficient algorithms for schedulability test and admission control in some real-time SMs. With the testing interval tree for vacancy analysis (TIT-V), the complexities of the schedulability tests in a class of parallel/distributed real-time systems can be effectively reduced from O(m2nlogn) to O(mlogn+mlogm) (where m is the number of processors, and n is the number of tasks). Similarly, with the testing interval tree for release time and laxity analysis (TIT-RL), the complexity of the online admission control in a uni-processor based real-time system can be reduced from O(n2) to O(nlogn) (where n is the number of tasks). Furthermore, the TIT-RL tree can also be applied to a class of parallel/distributed real-time systems. Therefore, the TIT trees are effective approaches to building efficient real-time SMs.

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Σ C j . In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt , d¯ j | Σ C j . It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

We consider the problem of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m ≥ 1 parallel and identical processors so as to minimize the mean flow time. For two processors, the Coffman--Graham algorithm gives a schedule that simultaneously minimizes the mean flow time and the makespan. The problem becomes strongly NP-hard for an arbitrary number of processors, although the complexity is not known for each fixed m ≥ 3. For arbitrary precedence constraints, we show that the Coffman--Graham algorithm gives a schedule with a worst-case bound no more than 2, and we give examples showing that the bound is tight. For intrees, the problem can be solved in polynomial time for each fixed m ≥ 1, although the complexity is not known for an arbitrary number of processors. We show that Hu's algorithm (which is optimal for the makespan objective) yields a schedule with a worst-case bound no more than 1.5, and we give examples showing that the ratio can approach 1.308999.

We consider scheduling problems in the master-slave model. In this model, each job has to be processed sequentially in three stages. In the first stage, a preprocessing task runs on a master machine, in the second stage, a slave task runs on a dedicated slave machine, and, in the last stage, a postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. It has been shown that the problem of minimizing the makespan or the sum of completion times is NP-hard in the strong sense even if preemption is allowed. In this paper, we design efficient approximation algorithms to minimize the sum of completion times in various settings. These are the first general results for the minsum problem in the master-slave model. We also show that these algorithms generate schedules with small makespan as well

A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on $m \ge 1$ identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focused on the setting whereby all tasks are available for processing at the beginning (i.e., at time t = 0). In this article we consider the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. In other words, the scheduler has to schedule tasks in an online fashion. We consider both preemptive and nonpreemptive schedules. We show that optimal online algorithms exist for some cases, while for others it is impossible to have one. Our results give a sharp boundary delineating the possible and the impossible cases.

Consider n independent jobs and m identical machines in parallel. Job j has a processing time p j and a deadline $\bar{d}_j$. It must complete its processing before or at its deadline. All jobs are available for processing at time t=0 and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines; such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time $\sum C_j$. In the classical $\alpha \mid \beta \mid \gamma$ scheduling notation this problem is referred to as $P \mid prmt, \bar{d}_j \mid \sum C_j$. Lawler (Recent Results in the Theory of Machine Scheduling, in Mathematical Programming: The State of the Art, A. Bachem, M. Grötschel, and B. Korte, eds., Springer, Berlin, 1982, pp. 202-234) raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every $m \ge 2$, and we show that the more general problem with m unrelated machines, i.e., $R \mid prmt, \bar{d}_j \mid \sum C_j$, is strongly NP-hard.

The asymptotic performance of heuristic algorithms for the multiprocessor scheduling problem is considered. Let rLS denote the ratio of the makespan of any list schedule to the optimal makespan. Let m denote the number of processors and n the number of jobs. We show that the mean and variance of rLS have upper bounds which approach 1 and 0, respectively, at a rate of O(m log n/n), under the assumption that job processing times are independent, identically distributed according to any distribution F over (0, ∞) with ∫(0,∞) eαtdF(t) < ∞ for some α > 0. If the processing times are distributed over (0, 1], a slightly faster convergence rate of O(m/n) is obtained. Furthermore, we show that almost surely, rLS approaches 1 at a rate faster than O(m/n1−β) for any 0 < β < 1. Similar results are also obtained for the Multifit algorithm due to Coffman, Garey and Johnson. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

In 1972, Liu claimed that for any task systems to be scheduled on $m\geqq 1$ identical processors, the ratio of the optimal nonpreemptive schedule length versus the optimal preemptive schedule length is bounded above by $2m/( m + 1 )$. Furthermore, Liu showed that the bound is the best possible by giving a task system achieving the ratio. His upper bound proof was later found to be incorrect, and his claim has since remained a conjecture. In this paper, it is shown that Liu’s bound is valid for the unit execution time (UET) and tree-structured task systems. For two processors, it is shown that some other classes of task systems satisfy the 4/3 bound. Other results comparing the lengths of optimal list, nonpreemptive schedules, and preemptive schedules are also given.

An optimal on-line scheduler is given for a set of real-time tasks with one common deadline on m processors. It is shown that no optimal scheduler can exist for tasks with two distinct deadlines. Finally, an optimal on-line scheduler is given for situations where processors can go down unexpectedly.>

Whether it is possible to have an optimal online algorithm for unidirectional ring, out-tree, in-tree, bidirectional tree, and bidirectional ring networks is discussed. The problem is considered under various restrictions of four parameters-origin node, destination node, release time and deadline. For unidirectional ring, it is shown that no such algorithm can exist unless one of the four parameters is fixed. For out-tree, it is shown that no such algorithm can exist unless one of three parameters-origin node, destination node and release time-is fixed. For in-tree, it is shown that no such algorithm can exist unless one of three parameters-origin node, destination node and deadline-is fixed. For bidirectional tree, it is shown that no such algorithm can exist unless the origin node or the destination node is fixed. For bidirectional ring, it is shown that no such algorithm can exist unless the origin node and either the destination node or the release time are fixed.>

The problem of minimizing the number of late tasks in the imprecise computation model is considered. Each task consists of two subtasks, mandatory and optional. A task is said to be on-time if its mandatory part is completed by its deadline; otherwise, it is said to be late. An on-time task incurs an error if its optional part is not computed by the deadline, and the error is simply the execution time of the unfinished portion. The authors consider the problem of finding a preemptive schedule for a set of tasks on p >or= 1 identical processors, such that the number of on-time tasks is maximized, (or equivalently, the number of late task is minimized), and the total error of the on-time tasks is no more than a given threshold K. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each fixed p>or=1, even if all tasks have the same ready time and the same deadline.>

The problem of minimizing the total tardiness for a set of unit-processing-time jobs on a single machine is considered. J. K. Lenstra and A. H. G. Rinnooy Kan have shown that the problem is NP-hard if the jobs have arbitrary precedence constraints. They asked whether the problem remains NP-hard for tree-structured precedence constraints. In this paper we show that the problem is NP-hard even for a set of chains. Our result gives a sharp boundary for the complexity of this problem, since there is a simple, polynomial-time algorithm for a set of independent jobs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

In a new model of task systems studied by J.W.S. Liu et al. (1987) each task is logically decomposed into two subtasks, mandatory and optional. The authors discuss preemptively scheduling this kind of task system on p>or=1 identical processors so as to minimize the mean flow time. Given a task system and an error threshold K, the goal is to find a preemptive schedule such that each task is executed in the interval of its release time and deadline, the average error is no more than K, and the mean flow time of the schedule is minimized. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each p>or=1, even if all tasks have the same ready time and deadline. For a single processor, a pseudo-polynomial time algorithm and polynomial time algorithms for various special cases of the problem are given.>

The problem of scheduling n independent tasks on $m \geqq 1$ identical processors, with the objective of minimizing the schedule length under the constraint that it must have minimum flow time, is considered. For nonpreemptive scheduling, it is known that the problem is NP-hard. This paper shows that the problem is a lot easier for preemptive scheduling. Specifically, an $O(n\log n)$ time algorithm to find an optimal preemptive schedule is given. This algorithm generates schedules with at most $m - 1$ preemptions. It is also shown that an optimal nonpreemptive schedule can be almost twice as long as an optimal preemptive schedule. The results suggest that preemption is extremely beneficial in simultaneously minimizing the flow time and the schedule length.

Consider a set of n tasks with a tree-structured precedence relation and execution time of 1 or 3 units. We give an $O(n^2 \log n)$-time algorithm to find a minimum length schedule for these tasks on two identical processors. Possible generalization to the case of 1 or k units is also given.

One of the assumptions made in classical scheduling theory is that a task is always executed by one processor at a time. With the advances in parallel algorithms, this assumption may not be valid for future task systems. In this paper, a new model of task systems is studied, the so-called Parallel Task System, in which a task can be executed by one or more processors at the same time. The complexity of scheduling Parallel Task Systems to minimize the schedule length is examined. For nonpreemptive scheduling, it is shown that the problem is strongly NP-hard even for two processors when the precedence constraints consist of a set of chains. For independent tasks, the problem is strongly NP-hard for five processors, but solvable in pseudo-polynomial time for two and three processors. For preemptive scheduling, it is shown that the problem is strongly NP-hard for arbitrary number of processors for a set of independent tasks. Furthermore, it is shown that it is NP-hard, but solvable in pseudo-polynomial time, for a fixed number of processors.

The problem of preemptively scheduling a task system consisting of a set of n independent tasks on one processor so as to minimize the mean flow time is considered. The goal is to find a preemptive schedule such that the mean flow time is minimized subject to the constraint that task T/sub i/ is executed within the interval between its release time and its deadline. Such a schedule, if it exists, is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard. A greedy algorithm is given to find an optimal schedule for a large class of task systems.>

The problem of online scheduling of a set of n independent, real-time tasks on m>or=1 identical processors is addressed. An online scheduler is said to be optimal if it performs as well as the best offline scheduler. It is shown that no optimal online scheduler can exist if the tasks have more than one distinct deadline. An optimal online scheduler for tasks with one common deadline is given. An optimal online scheduler is also given for environments in which processors can go down unexpectedly.>

We consider the following variants of the bandwidth minimization problem: (1) the cycle-bandwidth problem which for a given graph G and positive integer k, asks if there is a circular layout such that every pair of adjacent vertexes have a distance at most k, (2) the separation problem which asks if there is a linear layout such that every pair of adjacent vertexes have a distance greater than k, and (3) the cycle-separation problem which asks if there is a circular layout such that every pair of adjacent vertexes have a distance greater than k. We show that the cycle-bandwidth problem is NP-complete for each fixed $k \geqslant 2$ the separation and cycle-separation problems are both NP-complete for each fixed $k \geqslant 1$, and the directed separation problem is NP-complete for arbitrary k. We give polynomial time algorithms for several special cases of the directed separation problem. Finally, we show the relationships of the directed separation problem with several scheduling problems by giving reductions among them.

We consider the 2-dimensional channel assignment problem: given a set S of iso-oriented rectangles (whose sides are parallel to the coordinate axes), find a minimum number of planes (channels) to which only nonoverlapping rectangles are assigned. This problem is equivalent to the coloring problem of the rectangle intersection graph G = (V, E), in which each vertex in V corresponds to a rectangle and two vertices are adjacent iff their corresponding rectangles overlap, and we ask for an assignment of a minimum number of colors to the vertices such that no adjacent vertices are assigned the same color. We show that the problem is NP-hard.

Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.

An $NP$-complete bin-packing problem is studied in which the objective is to maximize the number of pieces packed into a fixed set of equal capacity bins. Applications to processor and storage allocation in computer systems are discussed, and an efficient approximation algorithm is defined and studied. The main results are bounds on the complexity of the algorithm and on its performance.

Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a Θ(N log N) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling.

In this paper we consider the problem of finding a minimum cost deadlock recovery. We show that the problem is NP-complete and hence an efficient algorithm is unlikely to exist for this problem. We propose three fast heuristics and analyze their worst case performance relative to optimal solutions. Finally, we perform some simulation tests to get a feel for the average performance of these heuristics.

A combinatorial problem related to storage allocation is analyzed. The problem falls into a class of NP-complete, one-dimensional bin-packing problems. We propose an iterative approximation algorithm and show that it is superior to an earlier heuristic presented for this problem. The bulk of the paper is devoted to the proof of a worst-case performance bound.