Optimize Job Routing in Parallel Machine Scheduling
Company: TikTok
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
In the Production Factory game, jobs with varying processing times arrive and must be routed through two parallel machines to minimize total completion time.
##### Question
Design an algorithm that decides on-the-fly which machine each incoming job should occupy to keep average flow-time minimal.
##### Hints
Think greedy (shortest-processing-time first) and priority queues; discuss time-complexity.
Quick Answer: This question evaluates understanding of online scheduling and algorithmic decision-making, specifically skills in minimizing average flow-time when routing jobs to parallel machines.
You are given n jobs with positive processing times. There are two identical, non-preemptive parallel machines. All jobs are available at time 0. The completion time of a job is when it finishes on its machine. Minimize average flow-time, which is equivalent to minimizing the sum of completion times. Compute the minimal total completion time by scheduling jobs greedily: always assign the next shortest job to the machine that becomes available earliest (break ties by choosing any). Return this minimal total completion time.
Constraints
- 1 <= n <= 2 * 10^5
- times[i] is an integer in [1, 10^9]
- Two identical, non-preemptive machines
- All jobs are available at time 0
- Return the minimal total completion time (sum over all jobs)
Hints
- Minimizing average flow-time equals minimizing total completion time.
- Sort processing times in nondecreasing order (SPT).
- Maintain a min-heap of machine availability times (start with [0,0]).
- For each job p in sorted times: pop earliest available time t, push back t+p, and add t+p to the answer.