Recently, global navigation satellite systems (GNSSs) have started offering additional services to improve the precision of positioning, authenticate the GNSS signal, and broadcast messages (e.g., almanacs or information needed for search and rescue purposes). In all these scenarios, possibly long messages must be broadcast over the low-rate satellite-ground communication link.

By splitting the message into sub-messages, each transmitted by a different satellite, the receiver can decode them simultaneously, achieving a higher equivalent data rate. In this paper we address the problem of scheduling sub-message transmissions on a constellation of satellites for transmission over error-free and erasure channels. For the error-free case we aim at maximizing the area over the earth, where the entire message can be decoded. Both optimal (by binary linear programming) and sub-optimal low-complexity solutions are  investigated. For erasure channels we consider two possible targets: either the minimization of the maximum packet error rate (PER) on the earth surface, or, in a dual fashion, the maximization of the area where all sub-messages are received with PER below a given threshold. Both problems are framed as integer linear programming problems, and again suboptimal, less computationally demanding solutions are  also developed.