![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Errata
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 –
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.
no subject
L = LA+LB
S = min(SA,SB-LA)
That *feels* like throwing information away, but if so that would to recapture the simplicity, and the deadlines have obviously been abstracted into the start times.
My reasoning was to guess to try to work out what S would be from scratch, and reason that you must be able to consider A and B as two separate blocks of time, each of which can be slid about as a unit. But block B must start no later than SB, and you know examining the internals can't help, as all block A must be finished by then, and any block C is less urgent, so it's at least as good to do all B as fast as you can first. So the only keys for S are (a) must start A by SA and (b) must start B by SB, ie. finish A by SB.
And a little munging makes me think that's equivalent to what you wrote.
S = min(SA, EDA-LA)
S = min(SA, min(DA,SB)-LA)
S = min(SA, min(DA-LA, SB-LA) )
S = min(SA, DA-LA, SB-LA)
But SA<=DA-LA, so
S = min(SA, SB-lA)
I had a different (wrong) simplification earlier which involved two scalars and one "you shipment of fail has arrived" bit, with successive logical ANDs, which was funny but didn't work. (Of course, if your log(N) is large, you may be able to escape early if any S is less than now if you like. But I don't know if that's ever worth it.)
no subject
S = min(SA,SB-LA)
Yes, I agree; I think that does work. It isn't actually throwing information away: since the tree is sorted by deadline, you can always retrieve D for a sublist of your choice by simply finding the last element in the sublist and looking up its deadline. It is slightly surprising to me that you don't directly need those deadlines when computing S, but it does appear to be true.
no subject
Exactly.
Although come to think of it, a thought experiment makes it seem plausible that everything is abstracted into S (which is what you *really* want to know, at least for this application, you just can't believe the deadlines aren't important). Imagine A as a block of time allocated from SA with all the tasks running successively in order of deadline. In terms of combining A with other tasks it's just like one task with SA and LA. Does it make a difference if any of the deadlines are moved? If it's a tight deadline (ie. if you start at SA then the task is done exactly by the deadline) then moving it forward is reflected in SA moving forward. If it's the only tight deadline then moving it back is reflected in SA moving back. If not, then it doesn't make any difference to SA, but doesn't make any difference to S either, since you might as well do all the tasks as quickly as you can regardless if any of them have slack or not.
no subject
Ah yes, I think I believe that too. Nice reanalysis!