# Example 897 — Each job went to the emptiest machine and the day ran long `each_job_went_to_the_emptiest_machine_and_the_day_ran_long.eml` - 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. ## EML ```eml # 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 ``` ## Python (deterministic transpilation) ```python 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.") ``` ## stdout (executed) ```text 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. ``` ## Round-trip `ok: true` — round-trip fixpoint reached (python1 == python2) ## Trace event types eml:run:start · eml:assign · eml:output · eml:run:done