Non-preemptive Throughput Maximization under Time-varying Capacity

We study the problem of scheduling jobs on a machine with time-varying capacity. The capacity at each time slot represents the maximum number of jobs that can be scheduled in parallel at that time slot. Each job is associated with a release time, processing time, deadline, and a profit. The objective is to find a non-preemptive schedule that respects all capacity constraints and maximizes the throughput, defined as the total profit of jobs that complete within their deadline. We consider different variants of the problem depending on job profits (identical / arbitrary), capacities (small / large) and environment (offline / online).