A method and system thereof for reducing the energy consumed when decoding an encoded and synchronized multimedia data stream, wherein the data stream is non-preemptable and subject to precedence constraints. In a client-server environment, the server delivers to the client the stream for decoding. The client has a processor operating on a discrete variable-voltage power supply. Prior to transmitting the stream to the client, the server produces an execution schedule according to the precedence constraints. The server also assigns a voltage setting for each task in the schedule, wherein each task decodes a frame in the stream without preemption. The server transmits the execution schedule and voltage settings to the client with the encoded data stream. The schedule and voltage settings reduce energy consumption by the client while satisfying multimedia timing constraints.