Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs simultaneously, and the objective is an assignment that minimizes the time-averaged number of open or active bins over the horizon; this problem is known to be NP-Hard. We demonstrate that a well-known “static” lower bound may have a significant gap even in relatively simple instances, which motivates us to introduce a novel combinatorial lower bound and an integer programming (IP) formulation, both based on an interpretation of the model as a series of connected matching problems. We theoretically compare the static bound, the new matching-based bounds, and various linear programming bounds. We perform a computational study using both synthetic and application-based instances, and show that our bounds offer significant improvement over existing methods, particularly for sparse instances.