Modern cloud platforms and serverless computing frameworks must balance two competing objectives: maintaining low request latency while minimizing the cost of provisioning computational resources. In many practical systems, these trade-offs are further complicated by startup overheads such as container cold starts, runtime initialization, or switching between classes of workloads that require shared setup. These effects arise across multiple layers of computing infrastructure, from serverless function provisioning to processor scheduling with setup-dependent tasks. This thesis studies two online scheduling problems motivated by these challenges. The first problem considers dynamic container provisioning where additional containers can be launched on demand but incur a fixed startup delay. The objective is to characterize and approximate the trade-off between operational cost, measured by the total time containers remain active, and system performance, measured by queueing delay. We develop online algorithms that achieve cost within (1+ϵ) of the optimal offline solution while guaranteeing worst-case response times bounded by O(1/ϵ) times the optimal delay. Empirical evaluation using synthetic and production-inspired workloads demonstrates that the proposed algorithms closely approximate the Pareto frontier between cost and latency while exhibiting favorable average-case behavior. The second problem examines uniprocessor scheduling of unit-length jobs that belong to families, where processing a family requires incurring a family-specific setup time. Jobs arrive online and have deadlines, and the objective is to minimize the number of missed deadlines. We show that classical policies such as Earliest Deadline First fail in this setting and that the offline version of the problem is NP-hard even under restricted assumptions. We introduce a new online policy, Interval Buffer EDF, which approaches 1-competitiveness as job slack increases, along with additional heuristic policies that provide provable competitive guarantees and strong empirical performance. Together, these results provide theoretical foundations and practical algorithms for scheduling and resource allocation in systems with startup overheads. By establishing provable competitive guarantees and empirically validating algorithmic behavior, this work contributes toward the design of predictable, cost-efficient computing platforms that must operate under uncertainty in dynamic environments.
Grady Thompson (Thu,) studied this question.