Three Processor Task Scheduling
I'm having difficulty coming up with an algorithm to brute force through all possible combinations of scheduling n tasks on three processors. Scheduling is non-preemptive and there's no deadline for any task.
The approach I've taken is to add each task in a ternary tree with each level representing a task. Each level is created after the user inputs each triplet of running times (first being that task's running time on the processor 1, etc).
The problem I'm having is going back up the tree after it's done accepting input. The goal is to keep a minimum sequence (such as 1 3 2 1 [task 1 on processor 1, task 2 on processor 3, etc]) in an array and the minimum running time, comparing this with the running time of each leaf node, replacing the minimum sequence with the latest one if this one's running time is less than the minimum.
I'm asking for suggestions on ways to ensure that each leaf node is accounted for (remember, brute force) and then it's relatively simple to use getParent() to travel up the tree. For each node, getChild1(), getChild2(), getChild3(), and getRightSib() are available.
Any help would be greatly appreciated. Thank you.
[1195 byte] By [
satisfya] at [2007-11-26 20:15:34]
It's theoretical - there are no actual processors. The user inputs n sets of three values representing n tasks. The first value is the running time for the task on the first processor, the second value is the running time on the second processor, etc.
The goal is now to compare every single possible combination of which tasks "run" on which processors to achieve a minimum running time.
Here is the (faulty) code I have currently: http://www.whiskeyandcigarettes.com/bruteforce3.java
And its output:
Enter triplet (negative number to exit): 1 2 3
Enter triplet (negative number to exit): 4 5 6
Enter triplet (negative number to exit): 7 8 9
Enter triplet (negative number to exit): -2
Regular Sequence: 1 1 1 cost: 15
- Minimum Sequence: 1 1 1 cost: 15
Regular Sequence: 1 1 2 cost: 8
- Minimum Sequence: 1 1 2 cost: 8
Regular Sequence: 1 1 3 cost: 9
Regular Sequence: 2 2 1 cost: 10
Regular Sequence: 2 2 2 cost: 18
Regular Sequence: 2 2 3 cost: 10
Regular Sequence: 3 3 1 cost: 12
Regular Sequence: 3 3 2 cost: 12
Regular Sequence: 3 3 3 cost: 21
Regular Sequence: 2 2 1 cost: 4
- Minimum Sequence: 2 2 1 cost: 4
Regular Sequence: 2 2 2 cost: 9
Regular Sequence: 2 2 3 cost: 6
Regular Sequence: 3 3 1 cost: 6
Regular Sequence: 3 3 2 cost: 6
Regular Sequence: 3 3 3 cost: 12
Final Sequence:
2 2 1
Cost: 4
Optimal schedule of cost 4
Processor 1: 3
Processor 2: 1 2
Processor 3:
I hope the problem makes at least a little more sense now. Thanks.
