Performance Analysis of Modified SRPT in Multiple-Processor Multitask Scheduling

In this paper we study the multiple-processor multitask scheduling problem in both deterministic and stochastic models. We consider and analyze Modified Shortest Remaining Processing Time (M-SRPT) scheduling algorithm, a simple modification of SRPT, which always schedules jobs according to SRPT whenever possible, while processes tasks in an arbitrary order. The M-SRPT algorithm is proved to achieve a competitive ratio of $\Theta(\log \alpha +\beta)$ for minimizing response time, where $\alpha$ denotes the ratio between maximum job workload and minimum job workload, $\beta$ represents the ratio between maximum non-preemptive task workload and minimum job workload. In addition, the competitive ratio achieved is shown to be optimal (up to a constant factor), when there are constant number of machines. We further consider the problem under Poisson arrival and general workload distribution (\ie, $M/GI/N$ system), and show that M-SRPT achieves asymptotic optimal mean response time when the traffic intensity $\rho$ approaches $1$, if job size distribution has finite support. Beyond finite job workload, the asymptotic optimality of M-SRPT also holds for infinite job size distributions with certain probabilistic assumptions, for example, $M/M/N$ system with finite task workload.