scheduling tasks

Monday, May 9, 2016 - 9:00am - 10:00am
Pravin Varaiya (University of California, Berkeley)
Time is slotted, t= 1,…,T. p(t) kW of power is available in slot t. There are n = 1,… ,N tasks. Task n needs 1kW for a duration h(n) slots: it is flexible in that any h(n) out of T slots will work, i.e. the task is pre-emptible.

Let d(t) be the number of tasks that require at least t slots, so d(1) ≥d(2) … ≥d(T). Order the time slots so that p(1) ≥p(2) … ≥p(T). The available power can execute all tasks if and only if p(s) + … +p(T) ≥ d(s) + … +d(T), for every s.
Subscribe to RSS - scheduling tasks