Oberseminar
Christoph Damerius, University of Hamburg
March 12, 2021, 11:00, zoom: https://uni-hamburg.zoom.us/j/94889228942
Title: Approaching Online Shared Resource Job Scheduling with List Scheduling Techniques
List Scheduling (LS) is among the most simple and well-studied Job Scheduling
problems. A set of n jobs with processing times p_j need to be scheduled on m
machines while minimizing the makespan. While near-optimal solutions for the
offline version of the problem are easy to come up with, the online version
has sprout a large number of papers during past decades, tightening lower
and upper bounds on the competitive ratio to ~1.88 and ~1.92, respectively.
We consider a novel extension called Online Shared Resource Job Scheduling
(OSRJB). The machines commonly share a resource and jobs additionally have
a resource requirement r_j. The scheduler must assign each job a portion of
the resource (at most r_j), while not overusing the resource. A smaller
assigned resource will cause a proportional decrease in execution speed of
that job. One can easily show that a natural Greedy algorithm is
3-competitive for OSRJB, while the above lower bound from LS transfers to
OSRJB as well. Aside from these trivial bounds, nothing is known about OSRJB.
This talk first gives insight about common LS Techniques and Ideas. We
discuss what difficulties are introduced by addition of the resource, and how
LS techniques could possibly be extended to OSRJB in order to improve the
bounds.