0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Nov 12, 2023 at 18:45

1 Answer 1

0
$\begingroup$

You should be able to do this in exponential time, but much faster than n^3 operations.

Get a quick upper bound by sorting the tasks in descending length, then scheduling each task in turn to the processor that has the least work. That’s 17, 11+6, 9+7+5. So you can do it in 22 units, and you only look for solutions where each processor uses at most 21 units; if you don’t find any solution than you have the next best already. Since the sum of tasks is 55, you can’t do it in less than 19 units.

For processor 1, it must do at most 21 units, and at least 13 because 13 >= 55-21-21. So you let it do the longest task (17) and any subset of the remaining tasks that takes at most 4 units, for a total of x units of tasks. The other two processors do tasks of total length y and z. You have the sum y+z = 55-x, and y, z <= 21. So y ranges from 55-x-21 to 21. You give the second processor the second longest task, and any subset of the remaining tasks so that 55-x-21 <= y <= 21.

And when you find a solution you strengthen the requirements. Say you find a solution with maximum length 21, then you only look for solutions where the longest task has length 20.

You save most time because for the first processor you only select subsets that make the sum close to the total task length divided by 3.

$\endgroup$
2
  • $\begingroup$ in the worst case the time complexity is still exponential right? $\endgroup$
    – Sachin
    Nov 13, 2023 at 4:42
  • $\begingroup$ Yes, it would be. But I can run an algorithm taking 2^n nanoseconds in one second for n=30, and in over two days if it takes 3^n nanoseconds. $\endgroup$
    – gnasher729
    Nov 13, 2023 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.