Maximizing Throughput for Parallel Jobs with Speed-Up Curves
摘要
We consider the problem of scheduling a set of n preemptive jobs with deadlines arriving online on m identical machines with the goal of maximizing weighted throughput. The jobs being scheduled are parallelizable and their parallelism is modelled with the standard speed-up curves model. Each job \(J_i\) arrives at time \(r_i\) with an associated deadline \(d_i\) and profit \(p_i\) which is acquired if the job is completed by its deadline. Jobs also have corresponding speed-up functions \(\varGamma _i : \Re ^+ \rightarrow \Re ^+\) . The speed-up function \(\varGamma _i(y)\) describes the rate at which the job is processed when scheduled on y machines and jobs are allowed to have distinct speed-up functions. We give the first result for the throughput scheduling problem for jobs with speed-up curves using resource augmentation, by showing a \(O(1+\epsilon )\) speed, \(O(\frac{1}{\epsilon ^2})\) competitive algorithm.