Narrow Results

This paper introduces a new graph theoretical concept called strong precedence which is used to address the problem of scheduling instability is non-preemptive static list scheduling. Scheduling instability occurs when a reduction in task duration of one or more tasks causes other tasks to miss their deadline. This problem has been addressed in the past by introducing additional precedence constraints into the precedence graph representing the workload, or by limiting the depth the dispatchers scan at run-time. We present an alternative stabilization approach based on the concept of strong and weak precedence. By defining a strong precedence relation on selected subgraphs, the workload becomes inherently stable without requiring the introduction of new edges into the graph.

In this paper, we study the problem of job dispatching and scheduling, where each job consists of a set of tasks. Each task is processed by a set of machines simultaneously. We consider two important performance metrics, the average job completion time (JCT), and the number of deadline-aware jobs that meet their deadlines. The goal is to minimize the former and maximize the latter. We first propose OneJ to minimize the job completion time (JCT) when there is exactly one single job in the system. Then, we propose an online algorithm called MultiJ, taking OneJ as a subroutine, to minimize the average JCT, and prove it has a good competitive ratio. We then derive another online algorithm QuickJ to maximize the number of jobs that can meet their deadlines. We show that QuickJ is competitive via a worst case analysis. We also conjecture that the competitive ratio of QuickJ is likely to be the best one that any deterministic algorithm can achieve. We also shed light on several important merits of MultiJ and QuickJ, such as no severe coordination overhead, scalability, work conservation, and no job starvation.