A machine shop has n_machines machines and a night's worth of jobs. Job j is a list of steps,
each (machine, minutes), and the steps must be done one after another in that order. A machine
works on one step at a time, and a step, once started, runs without a break. Job j's material
arrives at minute release[j], so its first step cannot start earlier. Each machine m also has a
maintenance window maintenance[m] = (a, b): no step may be running on it at any minute from
a up to (not including) b.
Write schedule_shop(shop) that returns the start minute of every step: starts[j][k] is when step
k of job j starts (a whole number). The shop wants the last step of all to finish as early as
possible.
shop is a dict with the keys "jobs", "release" and "maintenance". The tests build their
shops with shop_orders(n_jobs, n_machines, seed), and finish_time(shop, starts) gives the minute
the last step ends (it does not check the rules). Both are available in your code.
How this problem is scored
The checker makes its own schedule with a dispatch rule: over and over, it looks at the next step of every unfinished job, works out when that step could start if it went after everything already booked on its machine (pushed past the maintenance window if it would overlap it), and books the one that could start earliest (smaller job index on a tie). A schedule passes if it breaks no rule and finishes no later than the dispatch rule's. Its quality (0 to 100) is the share of the gap between the dispatch rule and the optimum (proved by an exact solver) that you close.
Examples
Input: shop = {"jobs": [[(0, 2), (1, 6)], [(1, 1), (0, 1)], [(1, 5), (0, 4)]],
"release": [0, 0, 0], "maintenance": [(4, 6), (5, 7)]}
Output: [[0, 8], [7, 8], [0, 9]] (finishes at 14, the optimum)
Explanation: machine 1 runs job 2's first step at 0-5, is serviced at 5-7, then does
job 1 at 7-8 and job 0 at 8-14. Machine 0 does job 0 at 0-2 and, after its
own maintenance at 4-6, job 1 at 8-9 and job 2 at 9-13.
The dispatch rule books job 0 at 0-2 and job 1 at 0-1 and 2-3 first; job 0's
second step then has to wait for machine 1's maintenance (7-13), job 2
follows it (13-18 and 18-22), and everything is done at minute 22.
Input: shop = shop_orders(15, 10, 4)
Output: any valid schedule finishing no later than the dispatch rule (422 here)
Constraints
- Up to 25 jobs and 15 machines; a job uses each of its machines once, steps take 2 to 30 minutes
- Material arrives between minute 0 and 60, maintenance windows are 15 to 40 minutes long
- Each test must finish in well under a second in your browser. Limit your loops by a number of
steps, not by the clock, and use
random(the tests seed it) so the result is the same every run.
Goals
- Turn an ordering of steps into a valid schedule that respects every precedence and machine limit
- Search over orderings instead of over start times
- Work around fixed maintenance windows and late material without breaking a constraint