Scheduling with gaps: New models and algorithms

We initiate the study of scheduling problems where the number or size of the gaps in the schedule is taken into consideration. We focus on the model with unit jobs. First we examine scheduling problems with release times and deadlines, where we consider variants of minimum gap scheduling, including maximizing throughput with a budget for gaps or minimizing the number of gaps with a throughput requirement. We then turn to other objective functions. For example, in some scenarios, gaps in a schedule may be actually desirable, leading to the problem of maximizing the number of gaps. The second part of the paper examines the model without deadlines, where we focus on the tradeoff between the number of gaps and flow time. For all these problems we provide polynomial algorithms. The solutions involve a spectrum of algorithmic techniques, including different dynamic programming formulations, speed-up techniques based on searching Monge arrays, searching X + Y matrices, or implicit binary search. Throughout the paper, we also draw a connection between our scheduling problems and their continuous analogues, namely hitting set problems for intervals of real numbers.