Optimal scheduling of contract algorithms with soft deadlines

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time \(w(t)\le c \cdot t\), for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.     

Improved on-line broadcast scheduling with deadlines

We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of (Kim, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479–488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). In the case that pages may have different lengths, we give a ( )-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). We also prove an almost matching lower bound of Ω(Δ/log Δ). Furthermore, for small values of Δ we give better lower bounds. The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK [NAL/01004/G].     

Preemptive scheduling with release times and deadlines

We consider the problem of deciding if there is a feasible preemptive schedule for a set of n independent tasks with release times and deadlines on m identical processors. The general problem is known to be solvable in O(n ³) time. In this paper, we study special cases for which faster algorithms exist. We introduce the notion of monotone schedules and study their properties. These properties are then exploited to devise fast algorithms for two special cases—the nested task systems and the non-overlapping task systems. We give an O(n log mn) time algorithm and an O(n log n+mn) time algorithm for nested task systems and non-overlapping task systems, respectively. Our algorithms generate at most O(n) and O(mn) preemptions for nested task systems and nonoverlapping task systems, respectively.Research supported in part by the ONR grant N00014-87-K-0833.     

Wireless real-time on-demand data broadcast scheduling with dual deadlines

In this paper, issues involved in the design of real-time on-demand broadcast system which maintains data temporal constraints are discussed. We propose a new online scheduling algorithm, called RDDS that incorporates access frequency, data size, request-deadline and data-deadline of pending requests for real-time on-demand broadcast system with dual deadlines. Furthermore, the concepts of deferrable requests and non-deferrable requests are introduced, cases of non-deferrable requests are analyzed, and Non-deferrable Request First policy is proposed and integrated into RDDS to form another new algorithm, called RDDS-W. We have performed a series of simulation experiments to evaluate the performance of our algorithms as compared with other previously proposed methods. The experimental results show that our algorithms can substantially outperform other algorithms under a wide range of scenarios, especially when combining with Non-deferrable Request First policy, which improves the performance significantly.     

Improved response-time bounds in fixed priority scheduling with arbitrary deadlines

We consider fixed priority sporadic tasks with arbitrary deadlines to be executed upon a uni-processor platform. Efficient schedulability tests for this task model are required for both online task admission in dynamic systems and interactive design of complex embedded real-time systems. The paper derives novel continuous upper bounds on the worst-case response times which runs in linear complexity. These bounds are not comparable to the tightest existing continuous upper bound of Bini et al. (in: Proceedings of the IEEE international conference on real-time systems symposium (RTSS’15), San Antonio, 2015) and strictly tighter under some parameters configurations. Moreover, the proposed approach allows to combine various existing methods to produce the tightest known continuous response time bounds. These results are extended to be applicable to a wide range of processor and network scheduling problems, including: release jitters, blocking times and cache related preemption delay (CRPD). Response time upper bounds are also given for tasks that are scheduled pre-emptively, co-operatively with intervals where pre-emption is deferred, and non-preemptively. Lastly, the quality of the method is analyzed and various recommendations are provided by means of numerical experiments.     

Algorithms for scheduling real-time tasks with input error andend-to-end deadlines

This paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task     

Real-time task scheduling with fuzzy uncertainty in processing times and deadlines

In real-time systems, scheduling algorithms play the vital role of devising a feasible schedule of the tasks. The scheduling algorithm designer faces uncertainty associated with the timing constrains of the real-time tasks. This paper considers fuzzy timing constraints by modeling the real-time tasks with fuzzy deadlines and fuzzy processing times with different membership functions. Comparative studies and some interesting findings based on simulation experiments are reported.     

Job shop scheduling with setup times, deadlines and precedence constraints

In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art. Paper presented in New York at MISTA 2005. E. Balas supported by the National Science Foundation through grant DMI-9802773 and by the Office of Naval Research through contract #N00014-97-1-0133.     

Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

We consider the problem of scheduling a maximum profit selection of equal length jobs on m   identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p>0$p>0$. For each job j_i, i=1,…,n we are given a release time r_i (at which the job becomes known) and a deadline _ri+p+_δi$r_i+p+{\delta }_i$. If the job is scheduled and completed before the deadline, a profit of w_i is earned.     

Modified rate-monotonic algorithm for scheduling periodic jobs withdeferred deadlines

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, γ-1) periods or more, where γ is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than [1+n(2¹n/-1)]/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity     

Load adaptive dynamic scheduling of tasks with hard deadlines useful for industrial applications

All intrinsic properties of the earliest deadline taks scheduling discipline are compiled and discussed in order to show that this is the most advantageous scheme at hand, characterised by efficiency and allowing predictable system behaviour. It is then pointed out how the method naturally extends to the scheduling of tasks having non-pre-emptable regions due to resource access constraints. A sufficient condition is derived, which allows, at any arbitrary point in time and under observation of resource constraints, to check the feasible schedulability of the tasks competing for processor allocation. This condition applies to entirely non-pre-emptable tasks as well. Taking the corresponding overhead into consideration, the circumstances are characterised under which the task context-switches imposed by the scheduling algorithm can be avoided. Favourable consequences of deadline scheduling for virtual storage management are mentioned. Finally, application oriented schemes for coping with transient overloads and thus allowing load adaptive dynamic scheduling are introduced. Such overloads can be easily detected at an early stage utilising the here established schedulability criterion.     

Integrated production and outbound distribution scheduling problems with job release dates and deadlines

In this paper, we study an integrated production and outbound distribution scheduling model with one manufacturer and one customer. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to the customer. Each job has a release date and a delivery deadline. The objective of the problem is to issue a feasible integrated production and distribution schedule minimizing the transportation cost subject to the production release dates and delivery deadline constraints. We consider three problems with different ways how a job can be produced and delivered: non-splittable production and delivery (NSP–NSD) problem, splittable production and non-splittable delivery problem and splittable production and delivery problem. We provide polynomial-time algorithms that solve special cases of the problem. One of these algorithms allows us to compute a lower bound for the NP-hard problem NSP–NSD, which we use in a branch-and-bound (B&B) algorithm to solve problem NSP–NSD. The computational results show that the B&B algorithm outperforms a MILP formulation of the problem implemented on a commercial solver.     

The rejection rate for tasks with random arrivals, deadlines, andpreemptive scheduling

A means of approximating light-traffic performance of RAD (random-arrivals-with-deadlines) systems for four basic preemptive scheduling policies is presented. The design goal is to keep congestion low enough to make the probability of rejection acceptably small. These designs must have low processor utilization. The study analyzes rejection probabilities at utilizations up to 20% and rejection probabilities up to about 10% for various well-known preemptive scheduling disciplines (shortest job first, earliest due date, and least laxity first), as well as first-come, first-served. Good approximations for the rejection probability and for a number of other properties, such as the distribution of time-to-go at rejection, are found     

A load index and a transfer policy for global scheduling tasks with deadlines

Two important components of a global scheduling algorithm are its transfer policy and its location policy. While the transfer policy determines whether a task should be transferred, the location policy determines where it should be transferred. Many global scheduling algorithms have been proposed to schedule tasks with deadline constraints. These algorithms try to transfer tasks only when task's deadlines cannot be met locally or local load is high (i.e. they take only corrective measures). However, a scheduling algorithm that takes preventive measures in addition to corrective measures can reduce potential deadline misses substantially. In this paper we present: (a) a load index which characterizes the system state and is more conducive to preventive and corrective measures; (b) a new transfer policy which takes preventive measures by doing anticipatory task transfers in addition to corrective measures. The proposed transfer policy adapts better to the workload by availing of the accurate system state made available by the proposed load index. An algorithm making use of the new transfer policy and the new load index is shown to reduce the number of deadline misses significantly when compared to algorithms taking only corrective measures.     

Real-time scheduling of periodic tasks with processing times and deadlines as parametric fuzzy numbers

Task scheduling is very important in real-time systems as it accomplishes the crucial goal of devising a feasible schedule of the tasks. However, the uncertainty associated with the timing constrains of the real-time tasks makes the scheduling problem difficult to formulate. This motivates the use of fuzzy numbers to model task deadlines and completion times. In this paper a method for intuitively defining smooth membership functions (MFs) for deadlines and execution times has been proposed using mixed cubic-exponential Hermite interpolation parametric curves. The effect of changes in parameterized MFs on the task schedulability and task priorities are also reported. A new technique is proposed based on the concept of dynamic slack calculation to make the existing model more practical and realistic. Examples are given to demonstrate the more satisfactory performance of the new technique.     

Optimal anticipative scheduling with asynchronous transmissionopportunities

Service is provided to a set of parallel queues by a single server. The service of queue i may be initiated only at certain time instances {t_nⁱ}_n=1^∞ that constitute the connectivity instances for queue i. The service of different customers cannot overlap. Scheduling is required to resolve potential contention of services initiated at closely spaced, closer than the service time, connectivity instances. At any time t, the future connectivity instances are available for scheduling. An anticipative policy is given, which at time t schedules the transmissions until a certain future time t+h. The length of the scheduling horizon h is selected based on the backlog at t. The allocation of the server in the interval [t, t+h], is done in accordance to the backlogs of the individual queues at t. The throughput region of the system is characterized, and it is shown that the policy we propose achieves maximum throughput. The policy has a low implementation complexity which is bounded for all the achievable throughput vectors. The average delay and the scheduling complexity are studied by simulation, and the trade-off between the two is demonstrated. The above scheduling problem arises in the access layer of the cross-links of a satellite network     

A note on preemptive scheduling of multiclass jobs with geometric service times and hard deadlines

We consider the scheduling of multiclass jobs with deadlines to the completion of their service. Deadlines are deterministic and job arrivals in each class occur at the times of deadline expirations in the respective class. Assuming geometric service times with class dependent means, we derive structural properties of preemptive server allocation policies that maximize the expected number of job completions. Our work extends results that have appeared in the real-time wireless scheduling literature.     

Multiprocessor scheduling of processes with release times,deadlines, precedence, and exclusion relations

The author presents a scheduling algorithm that solves the problem of finding a feasible nonpreemptive schedule whenever one exists on M identical processors for a given set of processes such that each process starts executing after its release time and completes its computation before its deadline. A given set of precedence relations and a given set of exclusion relations defined on ordered pairs of process segments are satisfied. This algorithm can be applied to the important problem of automated pre-run-time scheduling of processes with arbitrary precedence and exclusion relations on multiprocessors in hard-real-time systems