1 00:00:02,600 --> 00:00:06,259 For our next case study of how to use greedy algorithms, we're going to turn to 2 00:00:06,259 --> 00:00:09,641 the application domain of scheduling. That is how do you schedule jobs on 3 00:00:09,641 --> 00:00:12,189 shared resources in order to accomplish some objective. 4 00:00:12,189 --> 00:00:15,895 So, the domain of scheduling there's lots of different applications of greedy 5 00:00:15,895 --> 00:00:17,748 algorithms. We'll see two in this course. 6 00:00:17,748 --> 00:00:20,760 we'll start for today just with the following simple scenario. 7 00:00:20,760 --> 00:00:23,718 So, we'll assume, for today, that there's just one shared resource. 8 00:00:23,718 --> 00:00:26,076 This resource could represent any number of things. 9 00:00:26,076 --> 00:00:28,895 For concreteness, you can think of it as a computer processor. 10 00:00:28,895 --> 00:00:31,808 And then, there's a lot of different things that got to get done. 11 00:00:31,808 --> 00:00:35,367 So, for example, there's a lot of processes that have to be handled by this 12 00:00:35,367 --> 00:00:37,629 processor. In the algprithmic question, we are going 13 00:00:37,629 --> 00:00:40,280 to study, is, in what order should we sequence these jobs? 14 00:00:40,280 --> 00:00:43,926 Which one should we do first, which one should we do second, and so on, all the 15 00:00:43,926 --> 00:00:47,619 way up to which one should we do last. So, obviously to answer this question, we 16 00:00:47,619 --> 00:00:50,839 need to pin down the mathematical model a little bit more precisely. 17 00:00:50,839 --> 00:00:54,343 And lets start with just, you know, what is the characteristics of jobs, what 18 00:00:54,343 --> 00:00:57,800 information do we have that might lead us to prefer one job over another. 19 00:00:57,800 --> 00:01:02,486 But for this problem, we're going to assume that each job comes with two known 20 00:01:02,486 --> 00:01:05,485 parameters. So, first of all, job j has what we're 21 00:01:05,485 --> 00:01:09,360 going to call a weight w sub j. That's a non-negative real number. 22 00:01:09,360 --> 00:01:13,588 And you should think of the weight of a job as quantifying its importance. 23 00:01:13,588 --> 00:01:17,701 That is, jobs with a higher weight, in some sense, deserve to be processed 24 00:01:17,701 --> 00:01:21,970 earlier than those with a lower weight. And secondly, each job j is going to come 25 00:01:21,970 --> 00:01:25,801 with a non negative length l sub j. Depending on the application, you may or 26 00:01:25,801 --> 00:01:30,131 may not have a good estimate of how long jobs are going to take, but for today to 27 00:01:30,131 --> 00:01:33,913 keep things simple, let's assume we know what the length of every job is, and 28 00:01:33,913 --> 00:01:36,650 that's l sub j, it's part of the input to are problem. 29 00:01:36,650 --> 00:01:38,798 So. we have now defined the input to this 30 00:01:38,798 --> 00:01:42,100 computational problem. We get n jobs each specified by a weight 31 00:01:42,100 --> 00:01:44,878 and a length. And we know that the output is going to 32 00:01:44,878 --> 00:01:47,184 be a sequence of these n jobs in some order. 33 00:01:47,184 --> 00:01:51,115 So, what we have to understand now is what criterion do we want to optimize? 34 00:01:51,115 --> 00:01:53,840 What are we trying to accomplish with this sequence? 35 00:01:53,840 --> 00:01:57,300 To explain that, I need to tell you about completion times of jobs. 36 00:01:57,300 --> 00:02:01,001 So, the completion time of a job is defined hopefully in exactly the way 37 00:02:01,001 --> 00:02:03,674 you'd think. So, for the job which is scheduled first, 38 00:02:03,674 --> 00:02:07,838 it's just the length of the job because that's how long it takes to process that 39 00:02:07,838 --> 00:02:10,048 job. For whatever job gets scheduled second, 40 00:02:10,048 --> 00:02:14,109 its completion time is the length of the first job and then, the length of that 41 00:02:14,109 --> 00:02:16,628 job itself. So, in other words, it's just the total 42 00:02:16,628 --> 00:02:19,199 time which elapses before that job gets completed, 43 00:02:19,199 --> 00:02:21,460 okay? So, in general, the completion time of a 44 00:02:21,460 --> 00:02:25,573 job is just the sum of the lengths of the jobs scheduled to before that job plus 45 00:02:25,573 --> 00:02:28,966 the length of that job itself. To make sure this is clear, let's go 46 00:02:28,966 --> 00:02:32,034 through a quick example. So, suppose there are three jobs with 47 00:02:32,034 --> 00:02:35,256 lengths one, two, and three. I'm not going to tell you the job weights 48 00:02:35,256 --> 00:02:38,726 because they're irrelevant for the purposes of computing the completion 49 00:02:38,726 --> 00:02:40,808 time. And let's suppose we do the schedule 50 00:02:40,808 --> 00:02:44,180 where we just schedule job one first, the job two, then job three. 51 00:02:44,180 --> 00:02:48,760 So, pictorially, I'm going to represent that schedule just by stacking the jobs 52 00:02:48,760 --> 00:02:53,157 on top of each other with the interpretation that time starts at the 53 00:02:53,157 --> 00:02:56,088 bottom. So, time zero is where we schedule job 54 00:02:56,088 --> 00:02:59,020 one. And then, time increases as we go from 55 00:02:59,020 --> 00:03:03,600 the bottom to the top of the diagram. And the question then is, what are the 56 00:03:03,600 --> 00:03:09,335 completion times of these three jobs? Okay. 57 00:03:09,335 --> 00:03:14,690 So, the correct answer is answer C. So, for the first job, it gets scheduled 58 00:03:14,690 --> 00:03:18,556 first so it's very happy and it just takes one unit of time to complete, so 59 00:03:18,556 --> 00:03:21,958 its completion time is one. The second job, well, it has to wait for 60 00:03:21,958 --> 00:03:25,557 the first job to complete so one unit of time elapses and then, it itself has to 61 00:03:25,557 --> 00:03:28,495 complete so that's two more units so it gets to the completion time of three. 62 00:03:28,495 --> 00:03:32,542 For the third job, it has to wait for the first two to complete, so that adds three 63 00:03:32,542 --> 00:03:36,243 to the clock, and then plus it takes three units of time for a total of six. 64 00:03:36,243 --> 00:03:39,500 So, that's the definition of job completion times. In some sense, we 65 00:03:39,500 --> 00:03:42,411 obviously want completion times to be as small as possible. 66 00:03:42,411 --> 00:03:45,520 But it's not so simple. In any given schedule, the jobs that are 67 00:03:45,520 --> 00:03:49,468 give early on are going to have small completion times and the jobs towards the 68 00:03:49,468 --> 00:03:53,268 end are going to have big completion times. So inevitably, we're going be have 69 00:03:53,268 --> 00:03:56,179 to trading off the completion times between different jobs. 70 00:03:56,179 --> 00:03:59,518 So, what is the optimal way to so that? Well, that depends on our objective 71 00:03:59,518 --> 00:04:03,061 function, and in scheduling, there's many different objective functions you might 72 00:04:03,061 --> 00:04:05,395 want to use. today, I'm just going to tell you about 73 00:04:05,395 --> 00:04:07,123 one. It's not the only natural objective 74 00:04:07,123 --> 00:04:10,353 function, but it's one of several most natural objective functions. 75 00:04:10,353 --> 00:04:13,310 It's called minimizing the weighted sum of completion times. 76 00:04:13,310 --> 00:04:17,532 You translate this English phrase into mathematics in the obvious way. 77 00:04:17,532 --> 00:04:22,238 What you want to do is you want to minimize the sum over all n jobs of their 78 00:04:22,238 --> 00:04:25,496 completion time, but then multiplied by their weight of [UNKNOWN] j. 79 00:04:25,496 --> 00:04:27,849 Okay. So, the sum over j of w j times c j. 80 00:04:27,849 --> 00:04:32,011 The w j is the weight and c j is the completion time as defined on the 81 00:04:32,011 --> 00:04:34,967 previous slot. If you think about it for a second, 82 00:04:34,967 --> 00:04:39,492 you'll realize this is equivalent to minimizing the weighted average of the 83 00:04:39,492 --> 00:04:42,750 completion times with the weights given as in the input. 84 00:04:42,750 --> 00:04:46,547 So, just to make sure this makes sense, let's go back to the example that we saw. 85 00:04:46,547 --> 00:04:50,297 In that example, we had jobs with lengths one, two, and three, and we thought about 86 00:04:50,297 --> 00:04:52,604 to schedule or we scheduled them in that order. 87 00:04:52,604 --> 00:04:56,450 To evaluate the subjective function, I'd have to tell you their weights, so let's 88 00:04:56,450 --> 00:04:59,190 suppose their weights are three, two, and one, respectively. 89 00:04:59,190 --> 00:05:03,064 In this case, the weighted sum of completion times in the schedule, 90 00:05:03,064 --> 00:05:06,760 in the previous slide, well first, we begin with a, the first 91 00:05:06,760 --> 00:05:10,510 job, which has weight three. Its completion time, remember, was one. 92 00:05:10,510 --> 00:05:14,623 Then, we have the second job with weight two, its completion time is three. 93 00:05:14,623 --> 00:05:18,566 Then, we have the third job with weight one, its completion time was six. 94 00:05:18,566 --> 00:05:22,534 So, we sum up the weighted completion times and we get a total of fifteen. 95 00:05:22,534 --> 00:05:26,822 And I'll let you verify that, in fact, all of the three factorial or six 96 00:05:26,822 --> 00:05:31,052 schedules in that example, this is, in fact, the schedule that minimizes the 97 00:05:31,052 --> 00:05:35,282 weighted sum of completion times. And the algorithmic question we're going 98 00:05:35,282 --> 00:05:37,911 to study next, is how do we do this in general? 99 00:05:37,911 --> 00:05:42,255 Given arbitrary input in jobs, weights, and lengths, what is the sequence that 100 00:05:42,255 --> 00:05:46,200 minimizes this sum over all n factorial sequences you might consider?