Errata

[simont]

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.

Comments

[fanf]

What can cause slack between SA and DA?

[cartesiandaemon.livejournal.com]

Bugger, apparently I was too hasty after all.

[cartesiandaemon.livejournal.com]

Does it work if you just store S and L, and say:

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.)