Oh, rats. I am in fact wrong. In my previous entry, I was mistaken in the precise form of the node annotations required.

If SB < DA, so that in the presence of the tasks in B the last task in A has to be finished some amount of time before its natural deadline, it does not follow that the first task in A must be started the same amount earlier. It might be that there was spare time during the list of tasks in A, so that the deadline for the last one can be moved forward a bit without affecting the safe start time.

I think we fix this by adding a third annotation per node, giving the total duration of all the tasks in the sublist. So if list A has total length LA, then the amount by which DA−SA exceeds LA is the amount of spare time during the performance of the tasks in A – equivalently, if you did all of the tasks in A starting at time SA, it's how much time you'd have in hand before the deadline DA arrived. So we compute EDA as before; then if EDA is at or after SA+LA, we don't need to move the start time of A forward at all, and the start time for the concatenated list is still just SA. Only if EDA < SA+LA do we really have to move the schedule up.

So the revised annotation scheme is:

• for each sublist, we store its deadline D, its latest safe start time S, and its total length L.
• for a single job, D and L are provided for us, and S = D − L.
• given two adjacent sublists A and B, with annotations (DA,SA,LA) and (DB,SB,LB), we compute L = LA + LB and D = DB, obviously. Then we compute EDA = min(DA,SB), and set S = min(SA,EDA−LA).

I think that works properly this time. Ahem.