Understanding Machine Scheduling

Question

I'm currently learning about priority queues and heaps in my Data Structures class and all that stuff and in the class power points there is a little section that introduces machine scheduling, and I'm having difficulty understanding what is going on.

It begins by giving an example:

m identical machines

n jobs/tasks to be performed

assign jobs to machines so that the time at which the last job completes is minimum. -->The wording of this last part sort of throws me of...what exactly does the italicized portion mean? Can somebody word it differently?

Continuing with the example it says: 3 machines and 7 jobs

job times are [6, 2, 3, 5, 10, 7, 14]

possible schedule, followed by this picture:

(Example schedule is constructed by scheduling the jobs in the order they appear in the given job list (left to right); each job is scheduled on the machine on which it will complete earliest. )

Finish time = 21

Objective: find schedules with minimum finish time

And I don't really understand what is going on. I don't understand what is being accomplished, or how they came up with that little picture with the jobs and the different times...Can somebody help me out?

Answer 1

"The time at which the last job completes is minimum" = "the time at which the all jobs are finished", if that helps.

In your example, that happens at time = 21. Clearly there's no jobs still running after that time, and all jobs have been scheduled (i.e. you can't schedule no jobs and say the minimum time is time = 0).

To explain the example:

The given jobs are the duration of the jobs. The job with duration 6 is scheduled first - since scheduling it on machines A, B or C will all end up with it finishing at time 6, which one doesn't really matter, so we just schedule it on machine A. Then the job with duration 2 is scheduled. Similarly it can go on B or C (if it were to go on A, it would finish at time 8, so that's not in line with our algorithm), and we schedule it on B. Then the job with duration 3 is scheduled. The respective end times for machines A, B and C would be 9, 5 and 3, so we schedule it on machine C. And so on.

Although the given algorithm is not the best we can do (but perhaps there is something enforcing the order, although that won't make too much sense). One better assignment:

                14 16
A |      14      |2|
             10    16
B |    10    |  6  |
          7  10   15
C |   7   | 3|  5 |

Here all jobs are finished at time = 16.

I've listed the actual job chosen for each slot in the slot itself to hopefully explain it better to possibly clear up any remaining confusion (for example, on machine A, you can see that the jobs with duration 14 and 2 were scheduled, ending at time 16).

I'm sure the given algorithm was just an introduction to the problem and you'll get to always producing the best result soon.

What's being accomplished with trying to get all jobs to finish as soon as possible: think of a computer with multiple cores for example. There are many reasons you'd want tasks to finish as soon as possible. Perhaps you're playing a game and you have a bunch of tasks that work out what's happening (maybe there's a task assigned to each unit / a few units to determine what it does). You can only display after all tasks is finished, so if you don't try to finish as soon as possible, you'll unnecessarily make the game slow.