Techniques for computing a multimedia stream schedule in a resource-constrained environment. In one aspect of the invention, a technique for processing multiple media streams in accordance with a resource-constrained environment includes the following steps/operations. An optimization associated with a composite representation of the multiple media streams is computed based on timing constraints associated with the multiple media streams and one or more constraints associated with at least one device in the resource-constrained environment useable to present at least one of the multiple media streams. Scheduling transmission and/or storage of the multiple media streams, based on the optimization, is then performed. The multiple media streams may be encoded, based on the optimization, prior to the scheduling step/operation. Advantageously, the present invention may provide a scheduling strategy to multiplex multiple objects in a resource-constrained data path, while respecting all the presentation deadlines, and minimizing the required playback delay and decoding buffer.