Each job went to the emptiest machine and the day ran long

# Self-authored for the EML case corpus (no external origin). A dispatcher hands
# each job, in the order it arrives, to whichever of two machines is least
# loaded, and every assignment is made exactly by that rule. When the day ends
# under that rule, against when it could end, is computed below.
#
# The dispatch is careful. It reads the real length of every job; it always
# picks the genuinely least-loaded machine; every job is assigned; and the
# intent is exactly 'finish the day as early as possible'.
#
# Assigning by least-loaded as jobs arrive puts the two long jobs on different
# machines and the last short job on top of a long one, so the day runs to 7
# where a 3-3 and 2-2-2 split ends it at 6.

3 => job_1
3 => job_2
2 => job_3
2 => job_4
2 => job_5
2 => machines

job_1 + job_3 + job_5 => machine_one_load_by_dispatch
job_2 + job_4 => machine_two_load_by_dispatch
machine_one_load_by_dispatch => day_ends_by_dispatch
job_1 + job_2 => machine_one_load_best_split
job_3 + job_4 + job_5 => machine_two_load_best_split
machine_one_load_best_split => day_ends_best_split
day_ends_by_dispatch - day_ends_best_split => hours_lost
job_1 + job_2 + job_3 + job_4 + job_5 => total_work
int(total_work / machines) => perfect_balance
int(hours_lost * 10000 / day_ends_best_split) => day_longer_per_myriad

"jobs, in arrival order          : " + str(job_1) + ", " + str(job_2) + ", " + str(job_3) + ", " + str(job_4) + ", " + str(job_5) ^0
"machines                        : " + str(machines) ^0
"total work                      : " + str(total_work) + ", perfect balance " + str(perfect_balance) + " each" ^0
"" ^0
"least-loaded dispatch, machine 1 : jobs 1, 3, 5 = " + str(machine_one_load_by_dispatch) ^0
"least-loaded dispatch, machine 2 : jobs 2, 4 = " + str(machine_two_load_by_dispatch) ^0
"day ends by dispatch            : " + str(day_ends_by_dispatch) ^0
"" ^0
"best split, machine 1           : jobs 1, 2 = " + str(machine_one_load_best_split) ^0
"best split, machine 2           : jobs 3, 4, 5 = " + str(machine_two_load_best_split) ^0
"day ends by best split          : " + str(day_ends_best_split) ^0
"hours lost                      : " + str(hours_lost) + ", " + str(day_longer_per_myriad) + " per ten thousand longer" ^0
"" ^0

# ---- what the dispatch verified ----

"the least-loaded rule" ^0
"  reads : the real length of every job" ^0
"  picks : the genuinely least-loaded machine, every time" ^0
"  coverage : every job assigned" ^0
"  intent : finish the day as early as possible" ^0
"  jobs sent to the busier machine : 0" ^0
"  verdict : EVERY JOB WENT TO THE EMPTIEST MACHINE" ^0
"" ^0
"  always choosing the truly emptiest machine is the part" ^0
"  done right here, and it is why no single assignment can" ^0
"  be faulted at the moment it was made" ^0
"" ^0

# ---- what arrival order does to the split ----

"the sequence" ^0
"  job 1 (3) : machine 1 is empty, goes there - loads 3, 0" ^0
"  job 2 (3) : machine 2 is emptier - loads 3, 3" ^0
"  job 3 (2) : tie, machine 1 - loads 5, 3" ^0
"  job 4 (2) : machine 2 - loads 5, 5" ^0
"  job 5 (2) : tie, machine 1 - loads 7, 5" ^0
"  what the rule never considers : that the two 3s belong" ^0
"    together so the three 2s can share the other machine" ^0
"" ^0

# ---- what the shop got ----

"the day" ^0
"  ended at : " + str(day_ends_by_dispatch) ^0
"  could have ended at : " + str(day_ends_best_split) ^0
"  is any assignment wrong when made : no; each went to the" ^0
"    emptiest machine" ^0
"  is a sequence of best assignments the best sequence : no;" ^0
"    it is the sequence the arrival order dictated" ^0
"" ^0

# ---- null control ----

# The same jobs dispatched after sorting by length, longest first (or planned as
# a set), so the long jobs are placed before the short ones fill the gaps.
7 => nc_day_ends_arrival_order
6 => nc_day_ends_longest_first
1 => nc_hours_the_reorder_recovers

"null control - dispatch longest jobs first" ^0
"  day ends, arrival order : " + str(nc_day_ends_arrival_order) ^0
"  day ends, longest first : " + str(nc_day_ends_longest_first) ^0
"  hours the reorder recovers : " + str(nc_hours_the_reorder_recovers) ^0
"  no job and no machine changed; the rule stopped letting" ^0
"  arrival order decide the split" ^0
"" ^0

# ---- the rule ----

"what an emptiest-machine dispatch guarantees" ^0
"  each job lands on the least-loaded machine at its moment :" ^0
"    exactly, real lengths, every job" ^0
"  the day ends as early as it can : not addressed; the" ^0
"    arrival order splits the two long jobs and stacks the" ^0
"    last short one, so the day ends at " + str(day_ends_by_dispatch) + " where " + str(day_ends_best_split) + " was" ^0
"    possible" ^0
"" ^0

"a rule that is right at every step is right about the step and not about the" ^0
"path; the assignment that was best when the job arrived is judged against" ^0
"machines shaped by the jobs before it, and the shape was never chosen" ^0
"" ^0

"Every job goes to the genuinely emptiest machine - no assignment can be faulted" ^0
"when made. But arrival order puts the two 3s on different machines and the last" ^0
"2 on top of one, so the day ends at " + str(day_ends_by_dispatch) + " where a 3-3, 2-2-2 split ends it at " + str(day_ends_best_split) + "," ^0
"" + str(day_longer_per_myriad) + " per ten thousand longer, until the long jobs are placed first." ^0

job_1 = 3
job_2 = 3
job_3 = 2
job_4 = 2
job_5 = 2
machines = 2
machine_one_load_by_dispatch = job_1 + job_3 + job_5
machine_two_load_by_dispatch = job_2 + job_4
day_ends_by_dispatch = machine_one_load_by_dispatch
machine_one_load_best_split = job_1 + job_2
machine_two_load_best_split = job_3 + job_4 + job_5
day_ends_best_split = machine_one_load_best_split
hours_lost = day_ends_by_dispatch - day_ends_best_split
total_work = job_1 + job_2 + job_3 + job_4 + job_5
perfect_balance = int(total_work / machines)
day_longer_per_myriad = int(hours_lost * 10000 / day_ends_best_split)
print("jobs, in arrival order          : " + str(job_1) + ", " + str(job_2) + ", " + str(job_3) + ", " + str(job_4) + ", " + str(job_5))
print("machines                        : " + str(machines))
print("total work                      : " + str(total_work) + ", perfect balance " + str(perfect_balance) + " each")
print("")
print("least-loaded dispatch, machine 1 : jobs 1, 3, 5 = " + str(machine_one_load_by_dispatch))
print("least-loaded dispatch, machine 2 : jobs 2, 4 = " + str(machine_two_load_by_dispatch))
print("day ends by dispatch            : " + str(day_ends_by_dispatch))
print("")
print("best split, machine 1           : jobs 1, 2 = " + str(machine_one_load_best_split))
print("best split, machine 2           : jobs 3, 4, 5 = " + str(machine_two_load_best_split))
print("day ends by best split          : " + str(day_ends_best_split))
print("hours lost                      : " + str(hours_lost) + ", " + str(day_longer_per_myriad) + " per ten thousand longer")
print("")
print("the least-loaded rule")
print("  reads : the real length of every job")
print("  picks : the genuinely least-loaded machine, every time")
print("  coverage : every job assigned")
print("  intent : finish the day as early as possible")
print("  jobs sent to the busier machine : 0")
print("  verdict : EVERY JOB WENT TO THE EMPTIEST MACHINE")
print("")
print("  always choosing the truly emptiest machine is the part")
print("  done right here, and it is why no single assignment can")
print("  be faulted at the moment it was made")
print("")
print("the sequence")
print("  job 1 (3) : machine 1 is empty, goes there - loads 3, 0")
print("  job 2 (3) : machine 2 is emptier - loads 3, 3")
print("  job 3 (2) : tie, machine 1 - loads 5, 3")
print("  job 4 (2) : machine 2 - loads 5, 5")
print("  job 5 (2) : tie, machine 1 - loads 7, 5")
print("  what the rule never considers : that the two 3s belong")
print("    together so the three 2s can share the other machine")
print("")
print("the day")
print("  ended at : " + str(day_ends_by_dispatch))
print("  could have ended at : " + str(day_ends_best_split))
print("  is any assignment wrong when made : no; each went to the")
print("    emptiest machine")
print("  is a sequence of best assignments the best sequence : no;")
print("    it is the sequence the arrival order dictated")
print("")
nc_day_ends_arrival_order = 7
nc_day_ends_longest_first = 6
nc_hours_the_reorder_recovers = 1
print("null control - dispatch longest jobs first")
print("  day ends, arrival order : " + str(nc_day_ends_arrival_order))
print("  day ends, longest first : " + str(nc_day_ends_longest_first))
print("  hours the reorder recovers : " + str(nc_hours_the_reorder_recovers))
print("  no job and no machine changed; the rule stopped letting")
print("  arrival order decide the split")
print("")
print("what an emptiest-machine dispatch guarantees")
print("  each job lands on the least-loaded machine at its moment :")
print("    exactly, real lengths, every job")
print("  the day ends as early as it can : not addressed; the")
print("    arrival order splits the two long jobs and stacks the")
print("    last short one, so the day ends at " + str(day_ends_by_dispatch) + " where " + str(day_ends_best_split) + " was")
print("    possible")
print("")
print("a rule that is right at every step is right about the step and not about the")
print("path; the assignment that was best when the job arrived is judged against")
print("machines shaped by the jobs before it, and the shape was never chosen")
print("")
print("Every job goes to the genuinely emptiest machine - no assignment can be faulted")
print("when made. But arrival order puts the two 3s on different machines and the last")
print("2 on top of one, so the day ends at " + str(day_ends_by_dispatch) + " where a 3-3, 2-2-2 split ends it at " + str(day_ends_best_split) + ",")
print("" + str(day_longer_per_myriad) + " per ten thousand longer, until the long jobs are placed first.")

jobs, in arrival order          : 3, 3, 2, 2, 2
machines                        : 2
total work                      : 12, perfect balance 6 each

least-loaded dispatch, machine 1 : jobs 1, 3, 5 = 7
least-loaded dispatch, machine 2 : jobs 2, 4 = 5
day ends by dispatch            : 7

best split, machine 1           : jobs 1, 2 = 6
best split, machine 2           : jobs 3, 4, 5 = 6
day ends by best split          : 6
hours lost                      : 1, 1666 per ten thousand longer

the least-loaded rule
  reads : the real length of every job
  picks : the genuinely least-loaded machine, every time
  coverage : every job assigned
  intent : finish the day as early as possible
  jobs sent to the busier machine : 0
  verdict : EVERY JOB WENT TO THE EMPTIEST MACHINE

  always choosing the truly emptiest machine is the part
  done right here, and it is why no single assignment can
  be faulted at the moment it was made

the sequence
  job 1 (3) : machine 1 is empty, goes there - loads 3, 0
  job 2 (3) : machine 2 is emptier - loads 3, 3
  job 3 (2) : tie, machine 1 - loads 5, 3
  job 4 (2) : machine 2 - loads 5, 5
  job 5 (2) : tie, machine 1 - loads 7, 5
  what the rule never considers : that the two 3s belong
    together so the three 2s can share the other machine

the day
  ended at : 7
  could have ended at : 6
  is any assignment wrong when made : no; each went to the
    emptiest machine
  is a sequence of best assignments the best sequence : no;
    it is the sequence the arrival order dictated

null control - dispatch longest jobs first
  day ends, arrival order : 7
  day ends, longest first : 6
  hours the reorder recovers : 1
  no job and no machine changed; the rule stopped letting
  arrival order decide the split

what an emptiest-machine dispatch guarantees
  each job lands on the least-loaded machine at its moment :
    exactly, real lengths, every job
  the day ends as early as it can : not addressed; the
    arrival order splits the two long jobs and stacks the
    last short one, so the day ends at 7 where 6 was
    possible

a rule that is right at every step is right about the step and not about the
path; the assignment that was best when the job arrived is judged against
machines shaped by the jobs before it, and the shape was never chosen

Every job goes to the genuinely emptiest machine - no assignment can be faulted
when made. But arrival order puts the two 3s on different machines and the last
2 on top of one, so the day ends at 7 where a 3-3, 2-2-2 split ends it at 6,
1666 per ten thousand longer, until the long jobs are placed first.

Trace event types