Priority Queues
Hi there i need help on implementing this algorithm. Its called the LPT algorithm(Longest Processing Time), not sure if many of you have heard of it?
We use two priority queues. The first priority queue stores all the tasks in which the processing time of a task is the priority value. Each time a maximum processing time task is scheduled. We also maintain another priority queue of N elements, corresponding to N processors, where the priority value is the sum of all the processing times of the tasks allocated to that processor so far. At each step, we delete the processor with the minimum priority value, allocate the next task to the processor, and re-insert that processor into the priority queue until all the tasks are scheduled.
For this we are restricted to only PriorityQueues, ArrayLists, and Arrays.
[834 byte] By [
meth0da] at [2007-10-2 3:13:04]
Sorry also forgot to add that the first argument is the number of processors and the second argument is a txt file which contains jobs,i.e: 623510714
Well i've created two queues the first queue has descending values, ie: 14 --> 2, and the second queue has negative values, ie: -2 --> -14. Now how can i set 3 processors and get output like this:
The time at which the last task completes is: 16
Processor 1 tasks: 14 2
Processor 2 tasks: 10 5
Processor 3 tasks: 7 6 3
I am unsure of how to get the values to print out like that. I know that here i have to use an array or arrayList but not sure how to do this?
You are a long way from printing the result. If I were you I would create some pseudo code wich describes exactly what is to be done. This will break the problem into a set of smaller manageable problems.
Ok, so far im getting this as the output:
Processor 1 tasks: 14
Processor 2 tasks: 10
Processor 3 tasks: 7
Almost there, just gota figure out how to get the rest of the times in there. I used 3 PQ's, im not sure if that is the best way but it seems to be working so far. Any hints will be well received.
Cheers
>
> Almost there, just gota figure out how to get the
> rest of the times in there. I used 3 PQ's, im not
> sure if that is the best way but it seems to be
> working so far.
Well done.
Being an idiot with no life I implemented the algorithm. I have only used 2 PQ's for this (but it does not mean that my solution is better than yours). I have one PQ holding the Task objects to be processed and one holding the Process objects. Each Process object contains a list if the Tasks allocated to it.
Rather than read the data from a file (I hate reading data from files) I generated it using java.util.Random.
Each Task object has a toString() method that provides the information about a Task and each Process object has a toString() method that provides information about the Process and the allocated tasks. Printing the results it then just a matter of printing the list of Process objects.
can you please post your solution so i can see what you have done?
> can you please post your solution so i can see what> you have done?I know it is a clich but - I'll show you mine if you first show me yours!
public class Task implements Comparable<Task> {
public final int runTime;
public final String description;
// etc.
public int compareTo(Task obj) {
return runTime - obj.runTime;
}
}
public class Processor implements Comparable<Processor> {
private ArrayList<Task> tasks = new ArrayList<Task>();
private int time = 0;
public int compareTo(Processor obj) {
return time - obj.time;
}
public int getTime() {
return time;
}
public boolean add(Task obj) {
time += obj.runTime;
return tasks.add(obj);
}
public boolean remove(Task obj) {
if(tasks.remove(obj)) {
time -= obj.runTime;
return true;
}
return false;
}
}
public void assignTasks(Task[] tasks, Processor[] processors) {
PriorityQueue<Processor> queue = new PriorityQueue<Processor>();
for(Processor processor : processors)
queue.offer(processor);
Arrays.sort(tasks);
Processor p;
for(Task task : tasks) {
p = queue.poll();
p.add(task);
queue.offer(p);
}
}
public int findLPT(Task[] tasks, Processor[] processors) {
assignTasks(tasks, processors);
int maxTime = 0;
for(Processor p : processors)
if(maxTime < p.getTime())
maxTime = p.getTime();
return maxTime;
}
