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 bounded job workload, the asymptotic optimality of M-SRPT also holds for unbounded job size distributions with certain probabilistic assumptions, for example, M/M/N system with upper bounded task workload. An byproduct of our analysis is a tight characterization of the heavy traffic behavior of work-conserving algorithms in single-task job scheduling. We prove that the average response time in GI/GI/1 scales with 1/(1-\rho), if the job size distribution has finite support, which generalizes the growth rate in Lin, Wierman and Zwart, 2011%DIFDELCMD < ] %%% to general arrival processes and all work-conserving algorithms .
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 %DIFDELCMD < ] %%% finite task workload .
R
bounded
finite
R
unbounded
infinite
D
upper bounded task workload. An byproduct of our analysis is a tight characterization of the heavy traffic behavior of work-conserving algorithms in single-task job scheduling. We prove that the average response time in GI/GI/1 scales with 1/(1-\rho), if the job size distribution has finite support, which generalizes the growth rate in
D
Lin, Wierman and Zwart, 2011
R
to general arrival processes and all work-conserving algorithms
finite task workload