you're reading...

SACT Seminar: New Results on Online Resource Minimization

Time: 1:00pm Tuesday 21th October.

Location: SIT 459

Speaker: Dr. Lin Chen, TU Berlin

Title: New Results on Online Resource Minimization


We consider the online resource minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule on a minimum number of machines.

We rigorously study this problem and derive various algorithms with small constant competitive ratios for interesting restricted problem variants. As the most important special case, we consider scheduling jobs with agreeable deadlines. We provide the first constant ratio competitive algorithm for the non-preemptive setting, which is of particular interest with regard to the known strong lower bound of n for the general problem. For the preemptive setting, we show that the natural algorithm LLF achieves a constant ratio for agreeable jobs, while for general jobs
it has a lower bound of  Omega(n^{1/3}).

We also give an O(log n)-competitive algorithm for the general preemptive problem, which improves upon the known O(log(pmax/pmin))-competitive algorithm. Our algorithm maintains a dynamic partition of the job set into loose and tight jobs and schedules each (temporal) subset individually on separate sets of machines. The key is a characterization of how the decrease in the relative laxity of jobs influences the optimum number of machines. To achieve this we derive a compact expression of the optimum value, which might be of independent interest. We complement the general algorithmic result by showing lower bounds that rule out that other known algorithms may yield a similar performance guarantee.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: