As time-triggered communication protocols [e.g., time-triggered controller area network (TTCAN), time-triggered protocol (TTP), and FlexRay] are widely used on vehicles, the scheduling of tasks and messages on in-vehicle networks becomes a critical issue for offering quality-of-service (QoS) guarantees to time-critical applications on vehicles. This paper studies a holistic scheduling problem for handling real-time applications in time-triggered in-vehicle networks where practical aspects in system design and integration are captured. The contributions of this paper are multifold. First, it designs a novel scheduling algorithm, referred to as Unfixed Start Time (UST) algorithm, which schedules tasks and messages in a flexible way to enhance schedulability. In addition, to tolerate assignment conflicts and further improve schedulability, it proposes two rescheduling and backtracking methods, namely, Rescheduling with Offset Modification (ROM) and Backtracking and Priority Promotion (BPP) procedures. Extensive performance evaluation studies are conducted to quantify the performance of the proposed algorithm under a variety of scenarios.