A print shop has one press and a queue of n jobs. Job i takes jobs[i]["time"] minutes,
uses ink jobs[i]["ink"] (one of 4 inks), is due at minute jobs[i]["due"], and every minute it
finishes late costs jobs[i]["weight"]. Switching the press from ink a to ink b takes
change[a][b] extra minutes (0 when the ink stays the same). The press starts at minute 0 and the
first job needs no switch.
Write plan_prints(inst) that returns the order in which to print the jobs (every index from 0
to n - 1 exactly once) with a total weighted lateness, the sum of
weight * max(0, finish - due) over all jobs, as small as you can make it. inst is a dict with
the keys "jobs" and "change".
The tests build their queues with print_jobs(n, seed), and lateness_cost(inst, order) computes
the cost of an order. Both are available in your code, so you can try them with Run.
How this problem is scored
An order passes if its cost is no higher than that of the rule "next, print the job whose due time plus the ink change needed to reach it is smallest" (ties go to the smaller index). Its quality (0 to 100) is the share of the gap between that rule and the best order we know that you close.
Examples
Input: inst = {"change": [[0, 10], [10, 0]],
"jobs": [{"time": 5, "ink": 0, "weight": 1, "due": 5},
{"time": 5, "ink": 1, "weight": 1, "due": 6},
{"time": 5, "ink": 0, "weight": 3, "due": 12}]}
Output: [0, 2, 1] (finishes at 5, 10 and 25: cost 0 + 0 + 19 = 19)
Explanation: the rule picks job 0, then job 2 (due 12 + change 0 beats due 6 + change 10), then
job 1; here that is also the best order. Printing 0, 1, 2 costs 0 + 14 + 3 * 23 = 83.
Input: inst = print_jobs(20, 1)
Output: any order of 0..19; lower costs score higher
Constraints
20 <= n <= 80, job times 3 to 20 minutes, weights 1 to 5, ink changes 6 to 24 minutes- Each test must finish in well under a second in your browser. Limit your loops by a number of generations or rounds, not by the clock, so the result is the same on every run.
Goals
- Search over orderings with a population of permutations
- Cross two orderings without losing or duplicating jobs
- Trade off due dates against costly changeovers