We study a flexible job scheduling problem. A set of jobs is released over time, each with a starting deadline and a processing length. The jobs are to be started by an online scheduler no later than their starting deadlines and will run nonpreemptively. The objective is to minimize the span -- the time duration for which at least one job is running. We present a new lower bound of 4 on the competitiveness of any online algorithm. We also establish tight competitiveness bounds in the learning-augmented setting of the problem.

MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies the MinUsageTime DBP problem with predictions about item durations. We establish tight competitiveness bounds over the entire spectrum of prediction errors.

We study a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs into machines to minimize the total cost of all the machines used. We develop an$O(1)$-approximation algorithm in the offline setting and an$O(\mu)$-competitive algorithm in the online setting (where$\mu$is the max/min job length ratio), both of which are asymptotically optimal. This article significantly improves the analysis of the algorithms over our preliminary work.

This paper studies a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs onto machines to minimize the total cost of all the machines used. We develop an O(1)-approximation algorithm in the offline setting and an O(μ)-competitive algorithm in the online setting (where μ is the max/min job length ratio), both of which are asymptotically optimal.