A general framework for handling commitment in online throughput maximization We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive singleserver schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least 1varepsilon times its processing time, for some varepsilonu003e0. We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of O(1varepsilon) is the best possible (deterministic) for this problem. For commitment models, we give the first nontrivial performance bounds. If the commitment decisions must be made before a jobu0027s slack becomes less than a deltafraction of its size, we prove a competitive ratio of O(varepsilon((varepsilondelta)delta2)), for 0u003cdeltau003cvarepsilon. When a provider must commit upon starting a job, our bound is O(1varepsilon2). Finally, we observe that for scheduling with commitment the restriction to the unweightedu0027 throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.

Simple NearOptimal Scheduling for the MG1. We consider the problem of preemptively scheduling jobs to minimize mean response time of an MG1 queue. When the scheduler knows each jobu0027s size, the shortest remaining processing time (SRPT) policy is optimal. Unfortunately, in many settings we do not have access to each jobu0027s size. Instead, we know only the job size distribution. In this setting, the Gittins policy is known to minimize mean response time, but its complex priority structure can be computationally intractable. A much simpler alternative to Gittins is the shortest expected remaining processing time (SERPT) policy. While SERPT is a natural extension of SRPT to unknown job sizes, it is unknown how close SERPT is to optimal.  :112,present a new variant of SERPT called monotonic SERPT (MSERPT) which is as simple as SERPT but has provably nearoptimal mean response time at all loads for any job size distribution. Specifically, we prove the mean response time ratio between MSERPT and Gittins is at most 3 for load rho leq 89 and at most 5 for any load. This makes MSERPT the only scheduling policy known to be a constantfactor approximation of Gittins.