For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are delivered. In this paper, we address the accrued utility value maximization problem for narrow parallel and time-sensitive applications. We first consider the problem in the context of a discrete time domain and present the Spatial-Temporal Interference Based (STIB) scheduling algorithm. We formally prove that the STIB algorithm is a 2-approximation algorithm. Second, we extend our work to a continuous time domain and present a heuristic scheduling algorithm, i.e., the Continuous Spatial-Temporal Interference Based (STIB-C) algorithm to maximize the system's total accrued utility value when the system operates in a continuous time domain. The extensive empirical evaluations reveal that: (1) in a discrete time domain, the systems' total accrued utility values obtained through the STIB algorithm are consistent with the theoretic bound, i.e., they never go below 50 percent of the optimal value. In fact, on average, the STIB algorithm can achieve over 92.5 percent of the optimal value; (2) compared to other scheduling policies listed in the literature, the developed STIB and STIB-C algorithms have clear advantages in terms of the system's total accrued utility value and the profitable application ratio. In particular, in terms of the system's total accrued utility value, both the STIB and the STIB-C algorithms achieve as much as six times for both the First Come First Come Serve(FCFS) with backfilling algorithm and the Gang Earliest Deadline First (EDF) algorithm, and 4.5 times for the 0-1 Knapsack based scheduling algorithm. In terms of the profitable application ratio, both the STIB and the STIB-C algorithms obtain as much as four times for both the FCFS with backfilling algorithm and the Gang EDF algorithm, and two times for the 0-1 Knapsack based scheduling algorithm.

Distributed soft real-time applications often involve multiple jobs that are executed on different processing units. Hence, resource competitions among these applications can be on any processing unit in the system. However, due to distributed nature of these applications, each processing unit may not have the knowledge about the workload on other processing units. Therefore, scheduling decisions made by individual processing units about their local job execution orders may not be optimal for the applications to which the jobs belong with respect to meeting the applications' end-to-end deadlines. In this paper, we first introduce a metric to measure, at a local processing unit, the risk of a distributed soft real-time application missing its end-to-end deadline. Second, based on the metric, we develop a local deadline assignment algorithm, i.e., the delay-impact-based (DIB) local deadline assignment algorithm. With the DIB algorithm, distributed processing units can independently schedule their local job sets based on the assigned job deadlines with maximized successful ratio of meeting distributed real-time applications' end-to-end deadlines. We empirically compare the DIB algorithm with three commonly used local deadline assignment algorithms, i.e., the OLDA, Pure, and Norm algorithms. The experimental results show that the DIB algorithm has clear advantage over the OLDA, Pure, and Norm approaches — it results in up to 50%, 35%, and 35% higher successful ratio than the OLDA, Pure, and Norm approaches with respect to meeting application's end-to-end deadlines, respectively. Furthermore, for those applications that do miss their end-to-end deadlines, the application execution delay ratio resulted by the DIB algorithm is also up to 300%, 50%, and 150% smaller comparing to the other three approaches.

For a time-sensitive application, the usefulness or the quality of the application's end result depends on the time when the result is delivered, or when the application is completed. A Time Utility Function (TUF) is often used to represent the dependency between an application's accrued value and its completion time. For parallel and time-sensitive applications, each application has multiple tasks that must be executed concurrently in order to produce a result. Therefore, their execution occupies resources in two dimensions: spatial, i.e., the number of processing units needed to support concurrent tasks, and temporal, i.e., time duration needed to complete the application. Because of the parallelism and time-sensitive features of the applications, the execution interference among parallel and time-sensitive applications can be both in spatial and temporal domains. In this paper, we first introduce a metric to measure the spatial-temporal interference on applications' accrued values. Second, based on the metric, we develop a scheduling algorithm, i.e., the Discounting Spatial-Temporal Interference (DSTI) scheduling algorithm, to maximize system's total accrued utility value for a given set of parallel and time-sensitive applications. Our simulation results show that the proposed DSTI algorithm results in close to optimal solutions and also has clear advantage over existing approaches in the literature in terms of system total accrued utility values and profitable application ratio. It accrues up to 164%, 150%, and 97% more system value, and up to 21%, 35%, and 18% higher profitable application ratio than the Gang EDF, the FCFS with backfilling, and the 0-1 Knapsack based scheduling algorithms, respectively.

In distributed real-time systems, when resource cannot meet workload demand, some jobs have to be removed from further execution. The decision as to which job to remove directly influences the system computation efficiency, i.e., the ratio between computation contributed to successful completions of real-time jobs and total computation contributed to the execution of jobs that may or may not be completed. The paper presents two job removal policies which aim at maximizing system's computation efficiency for distributed real-time applications where the applications' end-to-end deadlines must be guaranteed. Experiments based on benchmark applications generated by TGFF [1] are conducted and compared with recent work in the literature. The results show clear benefits of the developed approaches - they can achieve as much as 20% computation efficiency improvement.

As computers and Internet technology advance, many time-dependent applications, such as mobile navigation and online gaming, are emerging. Time-dependent applications are associated with a pair of time-dependent functions representing accrued gain at the time when tasks complete or accrued cost when tasks fail to complete, respectively. For systems that provide time-dependent services, the optimization goal is to maximize the system profit when both potential gain and potential cost exist for each request the system accepts. This paper presents two scheduling algorithms, prediction-based highest gain density first (PHGDF) and iterative PHGDF (iPHGDF) scheduling algorithms with the objective to maximize the system's total accrued profit. Simulation results provide clear evidence that, with respect to the system total accrued profit, the proposed PHGDF and iPHGDF algorithms have advantages over other commonly used scheduling algorithm, such as the Earliest Deadline First (EDF), the Generic Utility Scheduling (GUS) and the Profit and Penalty aware scheduling (PP-aware) algorithms.

As computer and Internet technology continue to advance, real-time online services are emerging. Different from traditional real-time applications for which the scheduling objective is to meet task deadlines, the optimization goal for online service systems is to maximize profit obtained through providing timely services. For this class of applications, there are two distinctive characteristics. First, tasks are associated with a pair of time dependent functions representing accrued profit when completed before their deadlines and accrued penalty otherwise, respectively. Second, the service requests or tasks arrive aperiodically with execution time varying in a wide range. This paper presents a novel scheduling method and related analysis for such applications. Two scheduling algorithms, i.e., the nonpreemptive and preemptive Profit and Penalty aware (PP-aware) scheduling algorithms, are proposed with an objective to maximize system's total accrued profit. Our simulation results clearly demonstrate the advantages of the proposed algorithms, with respect to the system total accrued profit, over other commonly used scheduling algorithms, such as Earliest Deadline First (EDF) and Utility Accrual (UA) algorithms.