This paper addresses interleaved pulse scheduling in multitarget tracking with a pulse Doppler phased array radar that can process multiple simultaneous receive beams (MSRB), using element or sub-array level digital beamforming (DBF) architectures. Key constraints in this pulse scheduling such as consistent selection of pulse repetition frequency in an interleaved group of pulses are identified; the scheduling problems of both DBF levels are then formulated as an integer program that minimizes the total tracking time under these constraints. The formulation particularly takes into account the relief of nonoverlapping constraints on received beams by the MSRB processing, which facilitates pulse interleaving with reduced overall track occupancy. While the integer program formulation applies to both levels of beamforming architectures, an additional selection problem, termed disk selection, is presented for the subarray level beamforming case in order to consider a geometric limitation on the directions of received beams in digital postprocessing, called resteering. Heuristic algorithms for the interleaved pulse scheduling problems, which are shown to be NP-hard, are presented to produce feasible solutions in a computationally tractable manner. The practicality of the algorithms, in terms of performance and computation time, is validated by a complexity analysis and numerical simulations.