Greedy Schedule Algorithm

Question

There is a proof that states that sorting a list of Tasks by their start times will make use of the least amount of machines needed to perform the tasks. I found a case where sorting by their total time makes use of less machines.

Scheduling method: This algorithm makes use of this post to see if times overlap. If they do overlap we make a new machine. If not then we reassign the machine

private static void schedule(ArrayList<Task> tasks, ArrayList<Machine> machines) {
    for (Task t : tasks){
        boolean canProcess = false;
        for(Machine m : machines){
            if(t.startTime < m.task.endTime && t.endTime > m.task.startTime) 
                continue;//this machine is running during this time; look at next machine
            canProcess = true;
            m.task = t;
            break; //go on to the next task
        }
        if(canProcess == false){
            //create a new machine
            Machine m = new Machine();
            m.task = t;
            machines.add(m);
        }
    }
}

Here is an example of sorting by start time

Start Time: 4 End Time: 7 Total Time: 3
Start Time: 5 End Time: 9 Total Time: 4
Start Time: 6 End Time: 20 Total Time: 14
Start Time: 12 End Time: 21 Total Time: 9
Start Time: 19 End Time: 22 Total Time: 3
Sorting by start time: 3 machines

And here is sorting by Total Time:

Start Time: 4 End Time: 7 Total Time: 3
Start Time: 19 End Time: 22 Total Time: 3
Start Time: 5 End Time: 9 Total Time: 4
Start Time: 12 End Time: 21 Total Time: 9
Start Time: 6 End Time: 20 Total Time: 14
Sorting by total time: 2 machines

Is the theorem broken then or am I not implementing Greedy Scheduling correctly?

You need to be more specific about what theorem you are talking about. — allyourcode, Nov 21 '15 at 04:53

score 0 · Answer 1 · answered Nov 21 '15 at 05:45

If I understand your code correctly, you assign the task from 4-7 to machine 1; then you assign the task from 19-22 to machine 1, since that interval doesn't overlap with the previous interval (4-7); then you assign the task from 5-9 to machine 1, since that interval doesn't overlap with the previous interval (19-22). And already you've got a problem. You're telling machine 1 to perform a task from time 4-7 and a task from time 5-9, and it can't do that. So your "2 machines" result is bogus.

If you want to get the number of machines without sorting by start time first, then you'll need to keep a list of all intervals of the tasks that you've assigned to each machine. Thus, after the second task, your data will say that machine 1 is scheduled for 4-7 and 19-22. Then, when you look at the third task, at interval 5-9, you have to check it against both intervals assigned to machine 1. You'll find that it overlaps with 4-7 and that you can't schedule it, so you assign it to machine 2. I think that if you sort by start time first, then you don't have to keep a list of tasks for each machine. Maybe that's what the theorem is really saying? I don't know; I'd have to see the theorem (if you can provide a reference to it, that would be good).

Greedy Schedule Algorithm

1 Answers1