In this paper we study the multiple-processor multitask scheduling problem in  deterministic and stochastic models. We consider and analyze  M-SRPT  , a simple modification of the shortest remaining processing time algorithm , which always schedules jobs according to SRPT whenever possible, while processes tasks in an arbitrary order. The modified SRPT algorithm is shown to achieve a competitive ratio of \Theta(\log \alpha +\beta) for minimizing the flow time, where \alpha denotes the ratio of maximum job workload and minimum job workload, \beta represents the ratio between maximum non-preemptive task workload and minimum job workload. The algorithm 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 and show that M-SRPT is asymptotic optimal when the traffic intensity \rho approaches 1, if the job size distribution has bounded support. In addition, we also present a characterization of the heavy traffic behavior of work-conserving algorithms in single-task job scheduling , and prove that the average flow time in GI/GI/1 system scales with \frac{1{1-\rho}}  , if the job size distribution has bounded support, which generalizes the result in [Lin, Wierman and Zwart, 2011] to  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 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 {1-\rho}} scales with 1/(1-\rho) , if the job size distribution has finite support, which generalizes the growth rate in [Lin, Wierman and Zwart, 2011] to general arrival processes and all work-conserving algorithms.
A
both
A
Modified Shortest Remaining Processing Time (
A
) scheduling algorithm
R
the shortest remaining processing time algorithm
SRPT
R
modified SRPT algorithm is shown
M-SRPT algorithm is proved
R
the flow
response
R
of
between
R
The algorithm
In addition, the competitive ratio achieved
A
,
R
,
(
A
, M/GI/N system),
R
is asymptotic optimal
achieves asymptotic optimal mean response time
D
the
R
bounded support. In addition, we also present a
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
R
, and
. We
R
flow
response
D
system scales with \frac{1
A
scales with 1/(1-\rho)
R
bounded
finite
R
result
growth rate
A
general arrival processes and