Online variable-weight scheduling with preempting on jobs with linear and exponential penalties
share
We analyze the problem of job scheduling with preempting on weighted jobs that can have either linear or exponential penalties. We review relevant literature on the problem and create and describe a few online algorithms that perform competitively with the optimal scheduler. We first describe a naïve algorithm, which yields a high competitive ratio (Ω(M/s_min)) with the optimal, then provide an algorithm that yields a lower competitive ratio (4√(M/s_min) + nlogMn/s_min). Finally, we make a minor modification to our algorithm to yield an algorithm that has an even better competitive ratio (nlogMn/s_min).
READ FULL TEXT