Schedule Tasks With Ready Times on Limited Resources to Finish the Last One Earliest

You have limited compute resources and a set of tasks to run. For every task you know its execution time and its ready time, the earliest moment it may start (for example, when its input data becomes available). Decide when and where each task runs so that the time at which the last task finishes is as early as possible. At the end of the discussion the interviewer pointed to genetic algorithms as one way to optimize such a schedule; Part 2 asks for that approach. ### Clarifying Questions - What are the resources: a number of identical slots, or machines with different speeds or capacities? Does each task occupy exactly one slot while it runs? - Are there dependencies between tasks beyond their ready times? - Once a task starts, must it run to completion, or can it be paused and resumed? - Are execution times known exactly in advance or only estimated, and is the whole set of tasks known up front? - How many tasks are there, and how much time is available to compute the schedule? ### Part 1 — Formulate the problem and build a baseline schedule State the problem precisely, then give a schedule you can compute quickly and explain how good it is. ```hint Start with one slot With a single slot, ask in which order the tasks should run and when the slot is forced to sit idle; then ask what changes when there are several slots. ``` ```hint Measure the gap Look for a value that no schedule can beat, so that you can say how far any schedule you produce might be from the best one. ``` #### What This Part Should Cover - A precise formulation: decisions, constraints and the objective - The single-slot case, and why several slots make the problem hard - A fast greedy schedule, and a lower bound that limits its distance from the optimum ### Part 2 — Improve the schedule with a genetic algorithm Design a genetic algorithm that searches for schedules better than the baseline. ```hint What one candidate looks like Choose a representation in which every candidate, including every child produced by crossover or mutation, can be turned into a valid schedule and scored. ``` #### What This Part Should Cover - The encoding of a candidate, and how it is decoded into a schedule and scored - Selection, crossover and mutation that keep candidates valid, and how the population is seeded - Stopping criteria, cost per generation, and comparison of the result with the baseline and the lower bound ### What a Strong Answer Covers - Clarifies resources, dependencies and preemption before choosing a method - A correct baseline with a quality guarantee or a measured gap to a lower bound - A genetic algorithm with an explicit encoding, decoder, fitness and operators - Alternatives such as exact solvers for small instances and other local-search methods, and when each fits - How the schedule stays useful when execution times are only estimates ### Follow-up Questions - The tasks also depend on each other as a directed acyclic graph. How do the baseline and the encoding change? - Execution times are estimates and some tasks run much longer than expected. How do you keep the schedule robust? - How would you decide whether the genetic algorithm is worth its compute compared with the greedy schedule? - New tasks keep arriving while the schedule runs. How do you re-plan?