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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Nov 12, 2023 at 18:45
  • $\begingroup$ 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). $\endgroup$
    – John K.
    Commented Apr 10 at 21:18
  • $\begingroup$ 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. $\endgroup$
    – John K.
    Commented Apr 10 at 21:20

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ in the worst case the time complexity is still exponential right? $\endgroup$
    – Sachin
    Commented 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
    Commented 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.