Bandit Learning for Online Scheduling with Immediate Decision

摘要

Motivated by latency-critical streaming domains such as IoT data processing and cloud resource allocation, we investigate the problem of Online Scheduling with Immediate Decision, where a scheduler must instantly decide whether to accept an incoming task without buffering. We consider a system with M identical machines handling tasks with fixed processing lengths and stochastic, initially unknown rewards. A distinct feature of our model is preemption with abandonment: while a machine can interrupt a running task to accept a more valuable new arrival, the preempted task is permanently discarded, yielding no reward and no feedback, which is crucial for learning. We first analyze the setting with known rewards, deriving a worst-case competitive ratio lower bound and proposing the near-optimal Maximum Remaining Density First (MRDF) algorithm. For the challenging case of unknown rewards with censored feedback, we design an efficient bandit algorithm, Scheduling Upper Confidence Bound (S-UCB), which balances exploration and exploitation to achieve an O(log T) regret over time horizon T. Experimental results demonstrate the efficacy of the proposed algorithms against standard baselines.