Online weighted throughput maximization scheduling with a busy-time budget

Abstract

In this paper, we consider an online scheduling problem, weighted throughput maximization scheduling with a busy-time budget. In this problem, jobs are released with released times rj , processing times pj , and deadlines dj = rj + pj . Moreover, jobs have weights wj depending on the setting. In the proportional setting, the weight of a job equals to the length of this job. While in the categorized setting, a job has weight 1 if the length of this job is less than the given threshold ω, otherwise it has weight 2. We are also given machines, and each machine can run g jobs simultaneously. A busy-time budget T is also given. The objective is to gain as much weight as possible by scheduling jobs on machines using busy-time at most T. For infeasible instances of proportional setting, we consider general, clique, and one-sided clique instances, and prove that there is no deterministic online algorithm with a constant competitive ratio, and the greedy algorithm is an optimal online algorithm. For infeasible instances of categorized setting, we consider general, clique, and one-sided clique instances, and prove that no deterministic online algorithm has a constant competitive ratio unless it is a one-sided clique instance, and T is 2. For feasible one-sided clique instances of categorized setting, we design an adversary and prove that no deterministic online algorithm has a competitive ratio lower than 9/7.