Whenever I read stories with multiple timelines before, I always assumed the way it worked was this: if you start out in timeline A and you get sent back to some date, say 1066, you'll create a new timeline B that was identical to timeline A right up until the
exact moment you appeared in 1066, and which only begins to diverge after that moment. But this assumption doesn't actually work so well in a scenario where you have more than one time traveler sent back to the same time period. If you're starting from a timeline A where there were no time travelers in 1984, and then Skynet sends back the terminator and Kyle Reese goes back after him, then if the terminator arrived a few hours before Kyle, Kyle would be appearing in a timeline that had actually diverged from his own past a few hours before he arrived. This may not seem like a big deal, but if you allow that then you could have crazy situations like Kyle and the terminator going back to 1984 all serious and determined about killing/protecting Sarah Connor, but instead finding themselves in a 1984 ruled by intelligent dinosaurs because some time traveler in 4328 A.D. had decided to take a trip back to the Cretaceous era.
If you stick to the principle that each time traveler finds himself in a timeline that only diverged from his own past after the moment he arrived, then when the terminator and Kyle jumped back from timeline A, I think that'd have to result in two separate timelines: timeline B, where the terminator is the only one to arrive in 1984, he kills Sarah Connor, years later Skynet wins; and timeline C, where Kyle arrives alone and has no one to protect Sarah from. If you take this to extreme, then even if there's a 10^-30 second difference between the moment Kyle's feet appear in 1984 and the moment atoms from his head appear, his atoms would end up scattered between different timelines (and given the
relativity of simultaneity in relativity, it's hard to see how to avoid this unless the theory of relativity is wrong).
An alternative to having each time traveler create a new timeline would just be to allow time travelers to appear in versions of the past that had already diverged from their own history before they arrived thanks to other time travelers; in this case, you might imagine taking a God's-eye-view of timeline A from the Big Bang to the end of the universe, taking into account
all the time travelers ever sent into the past in timeline A, and then creating a single new timeline B in which all these time travelers appear at the appointed moment, in chronological order. So if the furthest trip into the past anyone made from timeline A was a condemned prisoner who was sentenced to death by being sent back to 30 seconds after the Big Bang, then timeline B would begin to diverge from timeline A 30 seconds after the Big Bang when that prisoner appeared, and all time travelers sent back from timeline A would find themselves in a history that had been influenced by that event.
One other solution to the problem of multiple time travelers heading for the same period would be to have something like a wormhole gate that offers a permanent connection between two timelines as long as it's held open, so if in the 2029 of timeline A you open a gate to 1984 it'll lead to a timeline B which diverges from A at the moment the other end of the gate appears in 1984, and everyone who subsequently steps through the gate in timeline A will find themselves in the same timeline B (and maybe can even return through the gate back to timeline A whose own history hasn't been changed), but then if this gate is shut down in and someone opens a new gate to 1984 in timeline A, this gate will lead to a different timeline C rather than back to timeline B.