A scheduling algorithm for scheduling messages on a time-triggered bus in a distributed real-time embedded system. The algorithm first determines an initial message schedule for assigning the messages to time slots on the bus so that predetermined precedent relationships are enforced. In one embodiment, the algorithm uses an earliest-deadline-first schedule to determine the initial message schedule. The algorithm then reallocates the messages in the time slots to provide unused time slots between the messages. In one embodiment, the reallocating the messages includes solving a quadratic optimization problem. Also, the messages are reallocated in the time slots so that they are substantially evenly spaced.