# 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. Nov 12, 2023 at 18:45