# 3 Processor Scheduling

A set of n independent tasks, each having integer execution times, are to be executed using three identical processors. A task can be executed in any of the three processors. Develop a sequential algorithm to find minimal total execution time for scheduling all the tasks. For this develop an initial recursive definition, indicate the properties of the unfolded recursion tree and develop a final algorithm. Show the working of your algorithm on a task set having the following execution times = {5, 7, 6, 9, 11, 17} using processors P1, P2 and P3. Analyze the time and space complexity of your initial and final algorithms.

I tried to use a DP based approach but still the time complexity is O(3^N). Is there a polynomial time algorithm for this problem?

Note: 2 processor scheduling is NP-Complete problem.

• Just for fun: You would likely run the scheduling algorithm on the same processors. So you’d want to minimise the sum of execution time plus the time needed for the scheduling. Commented Nov 12, 2023 at 18:45
• First of all, Subset Sum trivially reduces to this problem (add one element with execution time equal to half the sum of all other tasks, which now eats up all of P3). Commented Apr 10 at 21:18
• Since it is related to Subset Sum, you should consider whether pseudo-polynomial algorithms are ok, e.g. you can easily solve it in time $O(2^n \cdot n \cdot W)$ where $W$ is the sum of all execution times. Commented Apr 10 at 21:20