1 00:00:01,090 --> 00:00:03,180 Discrete Optimization, Constraint-based Scheduling. 2 00:00:03,180 --> 00:00:06,596 So what I'm going to do today is talk about one of the most fascinating areas, 3 00:00:06,596 --> 00:00:10,720 area, areas of Discrete Optimization, which is Scheduling. 4 00:00:10,720 --> 00:00:13,385 There are entire books on this, there are journals just on this topic, but what 5 00:00:13,385 --> 00:00:16,781 you're going to see, what I'm going to try to do is to make you curious. 6 00:00:16,781 --> 00:00:18,690 So that you can learn more about these things. 7 00:00:18,690 --> 00:00:21,714 There are beautiful algorithms, beautiful search techniques, and you'll see some of 8 00:00:21,714 --> 00:00:23,868 them. So I hope, you know, I'll get you excited 9 00:00:23,868 --> 00:00:26,598 about this area, because it's at the same time beautiful scientifically, and 10 00:00:26,598 --> 00:00:30,489 there's a lot of application in practice. So what I'm going to do is talk only 11 00:00:30,489 --> 00:00:33,290 about scheduling of you know, using Constraint Programming. 12 00:00:33,290 --> 00:00:36,171 There are also an entire branch of scheduling using, you know, mixed integer 13 00:00:36,171 --> 00:00:40,190 programming, local search and so on. But, you know, this is, this is one of 14 00:00:40,190 --> 00:00:43,226 the areas where lo, you know, constraint programming has been really, really very 15 00:00:43,226 --> 00:00:46,700 successful. I'm going to talk about, modeling a 16 00:00:46,700 --> 00:00:49,038 little bit. About global constraints and telling you, 17 00:00:49,038 --> 00:00:51,360 you know, you'll see some very interesting issue arising in this 18 00:00:51,360 --> 00:00:53,559 context. And you'll see a lot of very nice 19 00:00:53,559 --> 00:00:55,640 techniques behind the scene. Okay? 20 00:00:55,640 --> 00:00:58,873 So as I said, it's a very, successful application area for constraint 21 00:00:58,873 --> 00:01:01,756 programming. And one of the reason is that you can use 22 00:01:01,756 --> 00:01:03,940 all the flexibility of constraint programming. 23 00:01:03,940 --> 00:01:06,250 These problems are typically very complex. 24 00:01:06,250 --> 00:01:09,102 And you have a lot of different kind of, of constraints, and you can put them 25 00:01:09,102 --> 00:01:12,070 together using constraint programming, okay? 26 00:01:12,070 --> 00:01:14,680 So this is a typical example of what you can have in this area. 27 00:01:14,680 --> 00:01:18,264 So you are minimizing the duration of a big project, and that project has a lot 28 00:01:18,264 --> 00:01:22,126 of things to schedule, okay? So, and they are different precedence 29 00:01:22,126 --> 00:01:26,040 constraints between them, so some task has to come before others, and so on. 30 00:01:26,040 --> 00:01:29,659 And also you know, some of these tasks are going to use the same resources. 31 00:01:29,659 --> 00:01:33,210 And so sometimes the can overlap in time, or you know, several of them can overlap 32 00:01:33,210 --> 00:01:37,654 in time and things like this, okay? So this is the kind of problems that we 33 00:01:37,654 --> 00:01:40,760 are going to look at, okay? So this is an example, okay? 34 00:01:40,760 --> 00:01:42,930 So we want to build this bridge. [SOUND], okay? 35 00:01:42,930 --> 00:01:45,880 So typically we can't do it in one step, okay? 36 00:01:45,880 --> 00:01:49,475 So there variety of tasks, oops. No I, I want to do this again, because 37 00:01:49,475 --> 00:01:52,659 you, you missed the best part here. Okay, so we don't want to build that 38 00:01:52,659 --> 00:01:54,684 bridge like this. You see that little truck? 39 00:01:54,684 --> 00:01:57,444 Okay, anyway. so you have various tasks that you see 40 00:01:57,444 --> 00:01:59,773 here, okay? So obviously you have to build the 41 00:01:59,773 --> 00:02:02,797 bottom, you have to do the excavation before you can actually do the pillars 42 00:02:02,797 --> 00:02:05,780 and so on. And so, so you have precedence 43 00:02:05,780 --> 00:02:09,204 constraints between some of these tasks. You can build the top of the, of the 44 00:02:09,204 --> 00:02:12,437 bridge before the bottom and then obviously some of these tasks are going 45 00:02:12,437 --> 00:02:17,560 to use exactly the same resources. And they, they have to share that. 46 00:02:17,560 --> 00:02:20,536 And that's going to put some constraints on how you can actually schedule all 47 00:02:20,536 --> 00:02:23,990 these different activities for building this bridge, okay? 48 00:02:23,990 --> 00:02:26,540 So that's the kind of problems that we are looking at, okay? 49 00:02:26,540 --> 00:02:29,576 of course you have other problems in the steel industry and paper industry, all 50 00:02:29,576 --> 00:02:33,910 these things, you know, typically are scheduling problems like that. 51 00:02:33,910 --> 00:02:36,790 So typically when you model these problems, these days, what, you know, 52 00:02:36,790 --> 00:02:40,337 let's say, constraint programming languages or local search. 53 00:02:40,337 --> 00:02:43,313 You know, algorithm are doing is basically building abstraction just for 54 00:02:43,313 --> 00:02:46,695 that particular area. It's so big that you want this dedicated 55 00:02:46,695 --> 00:02:50,105 language that I'm going to talk about activities, and resources, and things 56 00:02:50,105 --> 00:02:53,150 like that. So we sometimes call this model-based 57 00:02:53,150 --> 00:02:55,854 computing, okay? It's going to make it easier to actually 58 00:02:55,854 --> 00:02:58,980 state the problem, okay? So you'll see, you know, concepts of 59 00:02:58,980 --> 00:03:02,052 activities, resources, and I'm going to give you, you know, a sense of what this 60 00:03:02,052 --> 00:03:05,734 looks like, although I won't go into the details, okay? 61 00:03:05,734 --> 00:03:08,470 Precedents, constraints and so on and so forth. 62 00:03:08,470 --> 00:03:12,435 Now behind the scene of use with these are going to be compiled into decision 63 00:03:12,435 --> 00:03:17,370 variables and global constraints, and things like this, okay? 64 00:03:17,370 --> 00:03:20,058 So, essentially that's a high level language which is compiling to you know, 65 00:03:20,058 --> 00:03:23,420 the typical language of constraint programming behind the scene. 66 00:03:23,420 --> 00:03:26,660 And then also you know, this concept are going to support dedicated search 67 00:03:26,660 --> 00:03:29,404 algorithm. Because we can exploit some of the 68 00:03:29,404 --> 00:03:32,322 structure that you have In these applications. 69 00:03:32,322 --> 00:03:35,804 And I will talk a little bit about that. But there is much more, you know, behind 70 00:03:35,804 --> 00:03:38,324 the scene, and I want to be able to talk about all the techniques that we can use 71 00:03:38,324 --> 00:03:41,939 here, okay? So, you know, one of the things that is, 72 00:03:41,939 --> 00:03:45,971 you know, the TSP, of, scheduling is called the Jobshop scheduling problem, 73 00:03:45,971 --> 00:03:49,752 okay? So it's probably the simplest, scheduling 74 00:03:49,752 --> 00:03:53,692 problem but it's also very hard, okay? But it's very simple to state, and people 75 00:03:53,692 --> 00:03:56,009 have been competing on this forever, okay? 76 00:03:56,009 --> 00:03:58,979 So there are a lot of standard, you know, benchmarks on this, and there are also a 77 00:03:58,979 --> 00:04:02,163 lot of open problems. It's not very difficult to actually 78 00:04:02,163 --> 00:04:05,071 generate instances that nobody can solve optimally, okay? 79 00:04:05,071 --> 00:04:08,666 So what I'm going to give you now is, you know, in two pages, it's in two slides. 80 00:04:08,666 --> 00:04:11,072 I'm going to give you the specification of the problem. 81 00:04:11,072 --> 00:04:14,272 I'm obstructing some of the fac, you know, some of the right information this 82 00:04:14,272 --> 00:04:16,954 slide. But essentially what we have is we have a 83 00:04:16,954 --> 00:04:19,683 set of tasks that we have to schedule, okay? 84 00:04:19,683 --> 00:04:21,822 And every one of them is a duration, okay? 85 00:04:21,822 --> 00:04:24,922 So we know, we're going to assume that we know the duration, it's fixed in this 86 00:04:24,922 --> 00:04:27,894 particular case. Now,w e also know that every task is 87 00:04:27,894 --> 00:04:31,643 actually usually one resources. This is a simplification right, in real 88 00:04:31,643 --> 00:04:35,003 life they typically use different resources, but here they only use one 89 00:04:35,003 --> 00:04:39,529 resource, one machine, okay? And we specify which machine that, you 90 00:04:39,529 --> 00:04:43,292 know, every task is using. And then we have a set of precedence 91 00:04:43,292 --> 00:04:46,586 constraints, okay, of the type (b,a), okay? 92 00:04:46,586 --> 00:04:51,491 Which basically means that a can only start after b has completed execution. 93 00:04:51,491 --> 00:04:54,689 So you have to finish b before you can start a, okay? 94 00:04:54,689 --> 00:04:58,349 So think about it in this, like, Excavating before you start building the 95 00:04:58,349 --> 00:05:01,650 bridge, right? And so, these are essentially the data 96 00:05:01,650 --> 00:05:05,133 and the various constraints. And what you want to do is schedule all 97 00:05:05,133 --> 00:05:09,072 these tasks so that you minimize the project completion time. 98 00:05:09,072 --> 00:05:12,842 The er, you know want this project to finish as early as possible. 99 00:05:12,842 --> 00:05:16,996 Now in the jargon of optimi, of, of scheduling, this is called a mixed time, 100 00:05:16,996 --> 00:05:20,038 okay? But this is one of the very famous 101 00:05:20,038 --> 00:05:24,804 objective, there are many others, okay? One of the most studied objective 102 00:05:24,804 --> 00:05:28,975 function for scheduling, okay? So let me give you a picture of that so 103 00:05:28,975 --> 00:05:34,702 can really what the jobshop is, okay? The constraints are coming form the job. 104 00:05:34,702 --> 00:05:38,262 So everyone of these a result of the lines you see on this slide, okay. 105 00:05:38,262 --> 00:05:41,597 So these are basically the jobs, okay? So you know, this is let's say the 106 00:05:41,597 --> 00:05:44,587 starting of the project. Then you see you know, this is the 107 00:05:44,587 --> 00:05:48,202 sequence of tasks inside a job. And the semantics here is that you know, 108 00:05:48,202 --> 00:05:51,587 this task is to be completed before the second one started. 109 00:05:51,587 --> 00:05:54,687 And after, the second one has to be completed before the third starts and so 110 00:05:54,687 --> 00:05:58,410 on and so forth. So this a way to you know, the precedence 111 00:05:58,410 --> 00:06:02,645 concerns are coming from, okay? So, they are coming from these jobs which 112 00:06:02,645 --> 00:06:07,034 are basically sequences of activities. And then what you see, the colors that 113 00:06:07,034 --> 00:06:10,151 you see in this, is, in this, in this pictures. 114 00:06:10,151 --> 00:06:14,037 In this picture are basically the machine that every one of these activity has to 115 00:06:14,037 --> 00:06:18,573 use, every task has to use, okay? So basically all the tasks which are 116 00:06:18,573 --> 00:06:22,133 color in yellow, I have to use the same machine, okay? 117 00:06:22,133 --> 00:06:25,543 So I am also showing you here you know, all the tasks of a particular machine 118 00:06:25,543 --> 00:06:28,824 that I basically call a machine kit, okay? 119 00:06:28,824 --> 00:06:32,594 So all these tasks use are, are using basically the same machine and therefore 120 00:06:32,594 --> 00:06:36,982 they cannot overlap in time, okay? You know, every two, every two of them. 121 00:06:36,982 --> 00:06:40,168 You know, we have to satisfy the fact that one is to be before or after the 122 00:06:40,168 --> 00:06:43,582 other, okay? So basically when you think about that, 123 00:06:43,582 --> 00:06:46,046 okay? So for solving these problems one of the 124 00:06:46,046 --> 00:06:50,745 things that you have to find out is in order for every one of these machines. 125 00:06:50,745 --> 00:06:54,100 And what I have shown you on this slide is basically all the possibly links 126 00:06:54,100 --> 00:06:57,712 between every two tasks using that machine, okay? 127 00:06:57,712 --> 00:07:02,152 And so what we have to do is to choose a subset of them, which are basically. 128 00:07:02,152 --> 00:07:05,422 You know, making a sequence, okay? And so is, so, so in a sense the way to 129 00:07:05,422 --> 00:07:10,002 think about this, is that a machine, has to handle all these tasks sequentially. 130 00:07:10,002 --> 00:07:12,262 They can be ordered in an arbitrary fashion. 131 00:07:12,262 --> 00:07:16,207 Of course, you know, you have to satisfy the present constraints on the jobs. 132 00:07:16,207 --> 00:07:19,567 But, but mostly what you're doing is trying to find for every one of these 133 00:07:19,567 --> 00:07:22,990 machine, an ordering of all these tasks, okay? 134 00:07:22,990 --> 00:07:25,412 So this is one of them, for instance, okay? 135 00:07:25,412 --> 00:07:30,428 So you start, you know, over there, and then you go over, ooh, where do we go? 136 00:07:30,428 --> 00:07:34,328 we go over, let me see. This is really difficult to see. 137 00:07:34,328 --> 00:07:38,048 We go here, and then [LAUGH] we go, we go down and then we go up, and so on and so 138 00:07:38,048 --> 00:07:42,081 forth, okay? So you basically have one ordering for 139 00:07:42,081 --> 00:07:46,038 that particular machine. All the Tasks here are basically ordered 140 00:07:46,038 --> 00:07:49,692 and, and the machine as, as very, you know, as a well defined order, ordering 141 00:07:49,692 --> 00:07:54,662 for every one of the task, okay? So this point, if you do that for all the 142 00:07:54,662 --> 00:07:58,302 machine, if you order all the machine, the only thing that you are left with are 143 00:07:58,302 --> 00:08:02,133 what? You are only left with these precedence 144 00:08:02,133 --> 00:08:05,337 constraints, okay? So you have this big graph know, we have 145 00:08:05,337 --> 00:08:08,967 all the original precedence constraints and every one of them which comes from 146 00:08:08,967 --> 00:08:13,784 the ordering of the machines, okay? And so this point, you know, I have a 147 00:08:13,784 --> 00:08:17,368 problem where the only thing I have to do, is to minimize the project duration 148 00:08:17,368 --> 00:08:22,423 subject to precedence constraints. And the beautiful thing is that this is a 149 00:08:22,423 --> 00:08:26,311 polynomial time problem, okay? We can solve this problem in polynomial 150 00:08:26,311 --> 00:08:29,047 time, okay? So we can use topological sorting which 151 00:08:29,047 --> 00:08:32,619 is called in that popular a literature of the PERT algorism. 152 00:08:32,619 --> 00:08:35,852 Or you know it, it the precedence contraints that are most sophisticated 153 00:08:35,852 --> 00:08:39,585 they have also distance. You would use transitive closure, but 154 00:08:39,585 --> 00:08:43,337 essentially this problem can be solved fast, you know, importing and obviously 155 00:08:43,337 --> 00:08:47,494 in polynomial time, okay? So in a sense the only thing we have to 156 00:08:47,494 --> 00:08:51,739 do in this particular problem is order the, you know, the machine. 157 00:08:51,739 --> 00:08:54,432 You don't have to choose a starting date, okay? 158 00:08:54,432 --> 00:08:58,155 So this step here at the end is going to do that automatically, okay? 159 00:08:58,155 --> 00:09:01,809 So you just have to find out the right ordering for all the task on everyone on 160 00:09:01,809 --> 00:09:05,612 the machine, okay? So let me show you an example of, you 161 00:09:05,612 --> 00:09:09,632 know, a constraint programming model for this particular, for this particular 162 00:09:09,632 --> 00:09:13,190 problem. So the, so, so once again, I don't want 163 00:09:13,190 --> 00:09:17,440 you to understand this in detail. What I want to show you here, and, and 164 00:09:17,440 --> 00:09:21,145 illustrate is the kind of languages that people have built for modeling these 165 00:09:21,145 --> 00:09:26,107 applications scheduling. These applications in a high level, okay? 166 00:09:26,107 --> 00:09:29,691 So the beginning here the first three line are boring basically here the data 167 00:09:29,691 --> 00:09:34,910 and description for every job and every task in that job you have a duration. 168 00:09:34,910 --> 00:09:39,270 Then you have the machine for which that particular task. 169 00:09:39,270 --> 00:09:42,122 On that particular job he's executing, we compute a time horizon, which is 170 00:09:42,122 --> 00:09:46,380 basically the longest time we can schedule all these activities. 171 00:09:46,380 --> 00:09:48,650 And so this is basically data, it's basically boring. 172 00:09:48,650 --> 00:09:51,560 What is a little bit more interesting here, okay? 173 00:09:51,560 --> 00:09:55,454 Is basically the description of, at a high-level, the decision variables, and 174 00:09:55,454 --> 00:09:58,935 some of the, the, the resources that, that are going to use for stating the 175 00:09:58,935 --> 00:10:02,360 constraints. So what you see there is that we are 176 00:10:02,360 --> 00:10:04,800 basically defining a schedule, and then we are basically defining these 177 00:10:04,800 --> 00:10:08,232 activities, okay? So for every job, and every task in the 178 00:10:08,232 --> 00:10:11,664 job, we are defining that activity and that activity is a particular duration, 179 00:10:11,664 --> 00:10:14,600 okay? So this is a concept, you know, this 180 00:10:14,600 --> 00:10:19,300 activity of the end of the date /g, will have a starting date and an ending date. 181 00:10:19,300 --> 00:10:22,300 And this isn't the level at which we want to rezone here, okay? 182 00:10:22,300 --> 00:10:25,180 So we want to be thinking about this activity, its starting date, the end 183 00:10:25,180 --> 00:10:28,410 date, possibly the duration if it's not fixed, okay? 184 00:10:28,410 --> 00:10:32,106 And we are basically expressing that as a high-level concept on which we want to 185 00:10:32,106 --> 00:10:35,451 express the model, okay? We also have an activity which is 186 00:10:35,451 --> 00:10:38,074 makespan, that's essentially the completion time of the project, it has 187 00:10:38,074 --> 00:10:40,834 duration zero. That is basically a dummy activity that 188 00:10:40,834 --> 00:10:44,336 we are putting at the end. And we put a precedence constraint of all 189 00:10:44,336 --> 00:10:48,350 the tasks, essentially, to that particular activity. 190 00:10:48,350 --> 00:10:51,758 Then we have here is a unary resource. We are, this is basically something that 191 00:10:51,758 --> 00:10:54,614 tells you that if there are various tasks which are actually using that resource, 192 00:10:54,614 --> 00:10:58,830 they won't be able to overlap in time. You will have to schedule one before the 193 00:10:58,830 --> 00:11:01,500 other, okay? So basically, you know, the description 194 00:11:01,500 --> 00:11:04,270 of your decision variables and the various. 195 00:11:04,270 --> 00:11:07,790 You know, act, you know, resources that you will use for stating the problem, 196 00:11:07,790 --> 00:11:10,304 okay? The rest is very much like the constraint 197 00:11:10,304 --> 00:11:13,872 programs that we have seen before. What we are doing is minimizing the end 198 00:11:13,872 --> 00:11:17,260 date of the makespan, okay? So it's the same as the starting date 199 00:11:17,260 --> 00:11:20,776 because the duration is zero, okay? So that's the, that, that's essentially 200 00:11:20,776 --> 00:11:23,900 modeling the end, you know, the duration of the project. 201 00:11:23,900 --> 00:11:26,860 And then what you see there are basically the various constraints, okay? 202 00:11:26,860 --> 00:11:31,069 So the first set of constraints I'm basically the precedent constraints 203 00:11:31,069 --> 00:11:35,347 inside this job okay and so you look at all the job and all the tasking in that 204 00:11:35,347 --> 00:11:39,820 job, okay? so you are setting that task t and job j 205 00:11:39,820 --> 00:11:43,604 as to precedes task t plus one in that same job j, okay? 206 00:11:43,604 --> 00:11:46,887 So, that's basically what you are seeing, you know of course, you know the system 207 00:11:46,887 --> 00:11:50,709 here understand, what it means to be a precedent constraints. 208 00:11:50,709 --> 00:11:53,925 And it will translate that into a simple inequality and I'll show you that in that 209 00:11:53,925 --> 00:11:57,230 next slide, okay? The last part that you see here, okay? 210 00:11:57,230 --> 00:11:59,834 So the, the next, you know, in between the two here you will, you know, these 211 00:11:59,834 --> 00:12:04,180 are the precedent constraints for saying that the makespan is after every one. 212 00:12:04,180 --> 00:12:07,300 But these are basically the resource constraints for every one of the task and 213 00:12:07,300 --> 00:12:10,506 every one of the job. You are basically specifying which 214 00:12:10,506 --> 00:12:13,888 resources they are using, okay? And therefore as you know that, you know, 215 00:12:13,888 --> 00:12:17,852 no task can overlap on these resources. You are basically specifying implicitly 216 00:12:17,852 --> 00:12:20,876 the, you know, the kind of disjunctive constraints that this problem has to 217 00:12:20,876 --> 00:12:23,978 satisfy, okay? So that's at the high-level, the kind of 218 00:12:23,978 --> 00:12:26,895 modeling that you have is this scheduling application. 219 00:12:26,895 --> 00:12:29,982 Of course, in practice, the resources are typically more complicated, the 220 00:12:29,982 --> 00:12:32,745 precedence constraints are more complicated. 221 00:12:32,745 --> 00:12:36,210 There may be additional side constraints, and things like this. 222 00:12:36,210 --> 00:12:39,785 But this is kind of the, you know, the simplest scheduling problem is the TSP of 223 00:12:39,785 --> 00:12:45,000 scheduling problems, okay? Now, behind the scene, this model, this 224 00:12:45,000 --> 00:12:49,200 high level model is compiled into a particular set of cons, decision 225 00:12:49,200 --> 00:12:54,292 variables and constraints, okay? So in a sense, you, you have to think 226 00:12:54,292 --> 00:12:56,950 about it, every activity has three variables. 227 00:12:56,950 --> 00:13:00,289 The starting date, okay, of that particular, of that particular activity, 228 00:13:00,289 --> 00:13:04,375 the duration of that activity, and the end date of that activity. 229 00:13:04,375 --> 00:13:08,980 Okay, so in a sense every variable can be thought of as three of, three variables. 230 00:13:08,980 --> 00:13:12,350 The starting date, the end date and the duration. 231 00:13:12,350 --> 00:13:16,504 Now, they have redundancy specially if the duration is fixed but, you know, they 232 00:13:16,504 --> 00:13:19,948 are basically... We typically use these three because it's 233 00:13:19,948 --> 00:13:23,310 really convenient for expressing some of the algorithms. 234 00:13:23,310 --> 00:13:25,100 Of course you have a constraint linking them. 235 00:13:25,100 --> 00:13:28,249 OK, the constraint is basically stating tha tyou know the starting date plus the 236 00:13:28,249 --> 00:13:34,018 duration is equal to the end date. OK, so in a sense an activity you have to 237 00:13:34,018 --> 00:13:38,434 think of it as giving you three you know interdependent decision variables linked 238 00:13:38,434 --> 00:13:44,079 that way by this constraint. Okay then the other things how to express 239 00:13:44,079 --> 00:13:48,567 the precedence constraints, if you have precedence constraints between b and a, 240 00:13:48,567 --> 00:13:52,383 okay? So simply it's become a very simple tiny 241 00:13:52,383 --> 00:13:56,797 inequality that Sa has to be greater or equal to a or b, okay? 242 00:13:56,797 --> 00:13:59,657 It's very simple, okay? The most interesting part here, and 243 00:13:59,657 --> 00:14:03,113 that's what I want to focus a little bit, you know, about in the la, the, the last 244 00:14:03,113 --> 00:14:06,990 part of the lecture, is the resource constraint. 245 00:14:06,990 --> 00:14:09,846 So these resource constraints are going to be compiled, into global constraints 246 00:14:09,846 --> 00:14:14,058 which are disjunctive, here, okay? And they are basically specifying that 247 00:14:14,058 --> 00:14:18,282 all the, all the activities there, t1 to tn basically cannot overlap in time, 248 00:14:18,282 --> 00:14:21,216 okay? So, this sys, this disjunctive 249 00:14:21,216 --> 00:14:23,460 constraints here which is really important. 250 00:14:23,460 --> 00:14:25,938 So, if you think in terms of the constraint programming model that I've 251 00:14:25,938 --> 00:14:29,573 presented in this class earlier, okay? Everyone of these precedence constraints 252 00:14:29,573 --> 00:14:31,968 is one of these guys, okay? And then you have also the global 253 00:14:31,968 --> 00:14:34,633 constraints, every disjunctive constraint for every one of the resources is 254 00:14:34,633 --> 00:14:38,069 going to be one of these constraints. And, of course, they are going to 255 00:14:38,069 --> 00:14:41,124 interact through the decision variable, which are the starting date, the end 256 00:14:41,124 --> 00:14:43,827 date. And not the duration because they are 257 00:14:43,827 --> 00:14:47,110 fixed, but, but essentially the starting and the end dates of every, end dates of 258 00:14:47,110 --> 00:14:51,260 every one of the activities, okay? So that's basically the, the, the, the 259 00:14:51,260 --> 00:14:53,520 overall model, what's happening behind the scene. 260 00:14:53,520 --> 00:14:56,488 What I want to focus on in the rest of the thing, because this is truly 261 00:14:56,488 --> 00:14:59,570 beautiful Is, the disjunctive constraints. 262 00:14:59,570 --> 00:15:03,200 And how you can actually, how you can actually implement algorithm that are 263 00:15:03,200 --> 00:15:07,072 pruning and, and, pruning effectively the search base. 264 00:15:07,072 --> 00:15:10,225 For this disjunctive constraints. So this is, so I'm going to illustrate 265 00:15:10,225 --> 00:15:13,791 that, all, you know some of this issue, on a very simple example, okay? 266 00:15:13,791 --> 00:15:16,750 So we have three activities that are requesting that resources. 267 00:15:16,750 --> 00:15:20,390 Okay so what is duration, six. The other one four the last one three. 268 00:15:20,390 --> 00:15:23,918 And what you see there is essentially the time window in which they have to be 269 00:15:23,918 --> 00:15:27,280 scheduled, okay? So, this is for instance for the, for 270 00:15:27,280 --> 00:15:30,608 the, for the ti, four times three, this is the earliest starting time at which 271 00:15:30,608 --> 00:15:35,000 that task can start, okay? So, let's say one, okay? 272 00:15:35,000 --> 00:15:39,090 And this is the latest finishing date for that particular task, okay? 273 00:15:39,090 --> 00:15:43,320 So in a sense, this is the minimum value in the domain of the starting date. 274 00:15:43,320 --> 00:15:47,478 This is the largest value in the domain of the ending, you know, variable, of the 275 00:15:47,478 --> 00:15:51,002 activity, okay? So every one of these guys can be 276 00:15:51,002 --> 00:15:54,040 scheduled anywhere in that time window, okay? 277 00:15:54,040 --> 00:15:57,264 So and what we have to do is to choose where to place them Such that they don't 278 00:15:57,264 --> 00:16:00,997 overlap in time, okay? And we have to find out, if this is 279 00:16:00,997 --> 00:16:04,340 feasible, okay? And how fast we can do that. 280 00:16:04,340 --> 00:16:06,385 Now there is one very interesting thing here. 281 00:16:06,385 --> 00:16:11,829 Is that, even the simple, one machine problem, is NP-hard, okay? 282 00:16:11,829 --> 00:16:15,514 Which is like, so I did, you know, this beautiful model with this disjunctive 283 00:16:15,514 --> 00:16:19,303 global constraints. And there is no way I can test this 284 00:16:19,303 --> 00:16:24,270 ability in polynomial time. So what are we going to do? 285 00:16:24,270 --> 00:16:29,028 Okay, so we could totally compose these thing into very tiny disjunctive 286 00:16:29,028 --> 00:16:35,783 constraints, okay, And you could verify this one in polynomial time, okay? 287 00:16:35,783 --> 00:16:40,900 But that basically looses. The, the entire globality of the problem. 288 00:16:40,900 --> 00:16:44,085 So, so you really don't want to do that because you will get nowhere in trying to 289 00:16:44,085 --> 00:16:48,330 solve practical problem. So what we going to do is that instead of 290 00:16:48,330 --> 00:16:52,590 solving this problem exactly, we will relax those tenders. 291 00:16:52,590 --> 00:16:56,718 And are we going to show you that. In a moment okay so there are a lot of 292 00:16:56,718 --> 00:17:00,115 algorithms to do that. I'm going to just make you curious here, 293 00:17:00,115 --> 00:17:02,576 okay? And give you basically the intuition 294 00:17:02,576 --> 00:17:05,869 behind some of them. And you know put them some connections 295 00:17:05,869 --> 00:17:09,082 and entire set of algorithms in this space, okay? 296 00:17:09,082 --> 00:17:11,300 And I'm going to use a little of notation. 297 00:17:11,300 --> 00:17:15,330 In think it's intuitive but I'm going to go slowly and because we are doing 298 00:17:15,330 --> 00:17:20,410 something which are a little bit fan, you know, fancy here, okay? 299 00:17:20,410 --> 00:17:23,650 So, I'm going to, I'm going to to, so, so, omega here in this, all, this formula 300 00:17:23,650 --> 00:17:28,166 in this subsequent slide, okay? Is a set of task, okay?? 301 00:17:28,166 --> 00:17:32,954 And so I'm going to denote s of omega.Think starting date of omega, okay 302 00:17:32,954 --> 00:17:40,960 So that's the earliest time at which one of the tasks inside omega can stop, okay. 303 00:17:40,960 --> 00:17:43,626 And the way I can compute that is that I look at all the task in omega and I take 304 00:17:43,626 --> 00:17:47,846 the one which is the strongest. Smallest possible value in the domain of 305 00:17:47,846 --> 00:17:49,890 its starting date. That's what I'm doing. 306 00:17:49,890 --> 00:17:53,001 So, when you see s omega, it's the earliest time at which any of these tasks 307 00:17:53,001 --> 00:17:57,346 in Omega can start, okay? Then e omega, okay? 308 00:17:57,346 --> 00:18:02,180 So, is just the opposite for the ending dates, okay? 309 00:18:02,180 --> 00:18:06,276 So, I'm basically look, e omega is the littlest finishing time of all the task 310 00:18:06,276 --> 00:18:10,134 in Omega. So, I taking a max overall of this of the 311 00:18:10,134 --> 00:18:15,770 maximum value the end value, okay? Of every one the activities, okay? 312 00:18:15,770 --> 00:18:20,126 And then the duration of these activities are a little bit interesting as well, 313 00:18:20,126 --> 00:18:23,443 okay? So the duration of omega is essentially 314 00:18:23,443 --> 00:18:27,413 the sum of all the duration of the tasks in omega, okay? 315 00:18:27,413 --> 00:18:30,513 So, you know, remember this notation because we are going to use it over and 316 00:18:30,513 --> 00:18:33,929 over and over again, okay? So s omega, earliest starting date of 317 00:18:33,929 --> 00:18:36,771 this set of tasks. E omega, that's basically the latest 318 00:18:36,771 --> 00:18:41,278 edition date of any of the tasking omega. And d omega is basically the long 319 00:18:41,278 --> 00:18:46,287 duration of all the tasking omega, okay? So, so what I'm at this point what we 320 00:18:46,287 --> 00:18:50,790 have is that we are trying to find if these constraints is feasible. 321 00:18:50,790 --> 00:18:53,084 That's one of the things that the constraints have to do, this disjunctive 322 00:18:53,084 --> 00:18:55,933 constraint, is it feasible? We know that this is a hard problem and 323 00:18:55,933 --> 00:18:58,860 we are not going to, we are not going to try to solve it. 324 00:18:58,860 --> 00:19:02,579 What we are going to do is now approximated efficiently, okay? 325 00:19:02,579 --> 00:19:05,444 Well, approximated somehow. And so this is the test, this is the 326 00:19:05,444 --> 00:19:08,815 first test that I'm proposing ,okay? To check if a set of tasks can be 327 00:19:08,815 --> 00:19:11,785 scheduled on this machine, what I'm going to do is check this little 328 00:19:11,785 --> 00:19:16,221 inequality. I'm going to, check that sT plus the 329 00:19:16,221 --> 00:19:21,241 duration of T, okay? Is more or equal to eT, okay? 330 00:19:21,241 --> 00:19:25,572 You know not eT right, e of T, okay? So, sT is basically the earliest starting 331 00:19:25,572 --> 00:19:28,657 date of T, okay? That's the total duration of all the 332 00:19:28,657 --> 00:19:32,122 task, and I will be sure that when I add these two things, I can fit them before 333 00:19:32,122 --> 00:19:36,459 the latest finishing date of all these tasks, okay? 334 00:19:36,459 --> 00:19:39,637 So in the sense, when you look at this picture here, okay? 335 00:19:39,637 --> 00:19:42,048 So this is the earliest starting time, okay? 336 00:19:42,048 --> 00:19:45,865 This is the latest finishing date, okay? And then you add all the duration of this 337 00:19:45,865 --> 00:19:50,052 task, that's basically the solid line inside every one of these tasks. 338 00:19:50,052 --> 00:19:53,090 And I want to be sure that when I sum the duration, you know and I add that to the 339 00:19:53,090 --> 00:19:56,134 starting date. I'm you know, terminating before I'm 340 00:19:56,134 --> 00:19:58,452 ending before the, the latest has ended, okay? 341 00:19:58,452 --> 00:20:01,540 That's basically what you're testing here, okay? 342 00:20:01,540 --> 00:20:05,200 So the question I have for you is that is this an effective test? 343 00:20:05,200 --> 00:20:08,464 Is this something that's going to detect feasibility or, you know, reasonably 344 00:20:08,464 --> 00:20:11,212 well, okay? And so one of the things that I told you 345 00:20:11,212 --> 00:20:14,374 in the first lecture of this class, right, is that, you know, when you have a 346 00:20:14,374 --> 00:20:18,060 question like this. What you have to do is to exaggerate, 347 00:20:18,060 --> 00:20:20,520 okay? So I'm going to exaggerate, okay? 348 00:20:20,520 --> 00:20:23,030 So this is a set of tasks. Here they have no duration. 349 00:20:23,030 --> 00:20:27,407 Well, the duration is fixed and the, the starting there is fixed, okay? 350 00:20:27,407 --> 00:20:31,250 And I have this guy this little guy who is all alone okay and seems to be really 351 00:20:31,250 --> 00:20:34,148 tight. They don't have much space to be 352 00:20:34,148 --> 00:20:36,971 scheduled okay so this is not feasible, okay? 353 00:20:36,971 --> 00:20:39,610 If you look at this task you can't schedule that. 354 00:20:39,610 --> 00:20:43,550 But because I added this very isolated guy notice that the. 355 00:20:43,550 --> 00:20:46,610 Notice that the earliest date is here, the latest finishing date is there. 356 00:20:46,610 --> 00:20:50,210 Obviously I have a lot of space here so I will be able to schedule. 357 00:20:50,210 --> 00:20:53,943 So essentially I have this I'm always going to say, yes it's feasible, okay? 358 00:20:53,943 --> 00:20:56,853 I believe it's feasible. Of course I don't, ever prove but, I, you 359 00:20:56,853 --> 00:21:01,231 know, my test is going to say yes, you know, I can prove in feasibility, okay? 360 00:21:01,231 --> 00:21:03,696 So, in a sense, this is a terrible test, okay? 361 00:21:03,696 --> 00:21:07,194 I can, I can make it arbitrarily bad by adding some task that are basically doing 362 00:21:07,194 --> 00:21:10,340 nothing. So we don't like that, we want the system 363 00:21:10,340 --> 00:21:13,256 to be robust. So one of the things that we can do is 364 00:21:13,256 --> 00:21:16,712 that, you know [LAUGH], you tried to, you know, annoy me, it's like during the 365 00:21:16,712 --> 00:21:20,895 relaxations, right? So what we want to do is have a test 366 00:21:20,895 --> 00:21:25,854 which you cannot annoy so easily. And what we do, this is another version 367 00:21:25,854 --> 00:21:28,922 of the test, but instead this time instead of just looking at the set T, I 368 00:21:28,922 --> 00:21:33,490 want to look at all of the subset of the tasks inside T, okay? 369 00:21:33,490 --> 00:21:36,845 So once again if I look at my basic set that I've shown you, ok, I want to look 370 00:21:36,845 --> 00:21:41,328 if that subset is feasible, okay? if that subset if feasible, if this 371 00:21:41,328 --> 00:21:44,743 subset is feasible, and so on. So for every possible subset of the 372 00:21:44,743 --> 00:21:48,780 tasks, I will apply the test that I've shown you on the previous slide, okay? 373 00:21:48,780 --> 00:21:51,160 And which is, you know, obviously here as well, okay? 374 00:21:51,160 --> 00:21:53,831 So that's what I want to do. I don't want you, because there is the 375 00:21:53,831 --> 00:21:57,146 one task in my project which is scheduled very, very late, I don't want you to, I 376 00:21:57,146 --> 00:22:02,230 don't want the test to always say yes. Here I want to be sure that the test is, 377 00:22:02,230 --> 00:22:05,915 you know, looking at all the possible subsets and detecting feasibility for any 378 00:22:05,915 --> 00:22:09,840 of these subsets, okay? Good, it looks good, right? 379 00:22:09,840 --> 00:22:15,340 No, what is the issue? So how many subsets do you have in a set? 380 00:22:15,340 --> 00:22:19,724 Well, you have exponentially many, okay? So now we would have to, you know, run an 381 00:22:19,724 --> 00:22:24,960 exponential number of sets And that doesn't sound too good, okay? 382 00:22:24,960 --> 00:22:30,126 But, but there is something which is really interesting in the structure of 383 00:22:30,126 --> 00:22:34,018 this set, okay? And in practice you only have to look at 384 00:22:34,018 --> 00:22:37,089 the quadratic number of them. And I'm going to give you the intuition, 385 00:22:37,089 --> 00:22:39,369 right? So this is all the task of my problem 386 00:22:39,369 --> 00:22:42,350 again, okay? But now I put some dash lines for 387 00:22:42,350 --> 00:22:45,926 everyone of them, okay. So in these dash lines, okay? 388 00:22:45,926 --> 00:22:48,655 Are denoting the starting date and the end date, okay? 389 00:22:48,655 --> 00:22:52,864 And the late, the earliest starting date, and the latest finishing date or end date 390 00:22:52,864 --> 00:22:57,597 of everyone of these tasks, okay? And what I'm going to show you is that 391 00:22:57,597 --> 00:23:01,268 you basically consider a quadratic number of tasks. 392 00:23:01,268 --> 00:23:05,398 Which are basically optimized by choosing a starting date and choosing an end date, 393 00:23:05,398 --> 00:23:08,354 okay? That's going to give you two tasks and 394 00:23:08,354 --> 00:23:11,957 I'm going to show you how to compute the tasks okay? 395 00:23:11,957 --> 00:23:15,305 So this is the intuition, two red tasks okay so you see this one and that one, 396 00:23:15,305 --> 00:23:18,024 okay? So, and so you see the starting date 397 00:23:18,024 --> 00:23:20,691 there and you see the end date there, okay? 398 00:23:20,691 --> 00:23:24,338 So, when you see this test, okay? Obviously you have the starting date and 399 00:23:24,338 --> 00:23:27,985 you have the end date, okay? And now look at this task in the middle, 400 00:23:27,985 --> 00:23:30,464 okay?? So, I am not considering it right, and 401 00:23:30,464 --> 00:23:33,629 now what I am claiming is that I can put it, okay? 402 00:23:33,629 --> 00:23:36,977 I don't have to, I will never have to ever test taking this task and that task 403 00:23:36,977 --> 00:23:41,860 together, okay it's completely useless to consider that subset, why? 404 00:23:41,860 --> 00:23:45,341 Because if I take this, if I take, you know, if I add this task to these two 405 00:23:45,341 --> 00:23:49,448 tasks here, what's going to happen? I'm not going to change the starting 406 00:23:49,448 --> 00:23:51,037 date. I'm not going to change the end date 407 00:23:51,037 --> 00:23:54,150 because this is in the middle. The only thing that I'm doing here is 408 00:23:54,150 --> 00:23:59,800 essentially increasing the duration. So, I'm making this task stronger, okay? 409 00:23:59,800 --> 00:24:03,384 So, essentially what I'm saying here is that I can, you know, I ca, well, when I 410 00:24:03,384 --> 00:24:07,316 have these three task, okay? So, I don't have to look at the subset of 411 00:24:07,316 --> 00:24:09,724 them because this task that I'm considering now we have the three of 412 00:24:09,724 --> 00:24:13,920 them, I'm going to subsume all of them. This is going to be stronger. 413 00:24:13,920 --> 00:24:17,365 Because it has the same start in there, the same ending, but I'm increasing the 414 00:24:17,365 --> 00:24:20,632 duration, okay? So in a sense to actually find out what 415 00:24:20,632 --> 00:24:24,860 are the subsidized need to look. I take a starting bid. 416 00:24:24,860 --> 00:24:27,940 I take a end bid and then I pack everything in it okay which means that 417 00:24:27,940 --> 00:24:32,710 the starting date has be after and the end that has to be before. 418 00:24:32,710 --> 00:24:35,645 And that's that stuff that I have to look for, okay? 419 00:24:35,645 --> 00:24:40,137 So, this is something that Cazzo and Lavorlt called task intervals, okay? 420 00:24:40,137 --> 00:24:44,493 So if you take two tasks, t1 and t2, then you lift essentially as many tasks as you 421 00:24:44,493 --> 00:24:48,334 can inside, okay? So you take all the task t, whose 422 00:24:48,334 --> 00:24:51,806 starting date after, you know t1, the starting date of t1 and before the end 423 00:24:51,806 --> 00:24:55,638 date of t2, okay? So you have this you know, task 424 00:24:55,638 --> 00:24:59,278 intervals, that are basically, out of strongest, set this, this, this strong 425 00:24:59,278 --> 00:25:04,450 subset that you want to look at, okay? And now basically the feasibilities that 426 00:25:04,450 --> 00:25:08,080 you see here, eh, can only focus on all these task intervals. 427 00:25:08,080 --> 00:25:11,019 They never have to look at anything else, okay? 428 00:25:11,019 --> 00:25:14,925 So you look at all the task intervals for ever pair of, of, of task, and that's 429 00:25:14,925 --> 00:25:20,890 what you, the, the, the, that's on this task interval that you apply the task. 430 00:25:20,890 --> 00:25:23,600 You don't have to look at any other subset, okay? 431 00:25:23,600 --> 00:25:26,720 And so the complexity of [UNKNOWN] here is that, you have a quadratic number of 432 00:25:26,720 --> 00:25:31,770 this, you know, inter-, task intervals. And the test, itself, is linear time. 433 00:25:31,770 --> 00:25:34,150 So you have an algorithm which is in cubic time. 434 00:25:34,150 --> 00:25:37,606 Now, cubic is pretty high. So, we ought to try to, to, to do better 435 00:25:37,606 --> 00:25:41,078 than this and I'm going to show you one you know, one in, one algor, one, some of 436 00:25:41,078 --> 00:25:45,180 the intuition on how you can do better, okay? 437 00:25:45,180 --> 00:25:47,780 So, I'm only going to show you one algorithm here which is going to be 438 00:25:47,780 --> 00:25:51,070 quadratic, okay? But, you can do better in practice and, 439 00:25:51,070 --> 00:25:54,344 and here you can do and log and in general, okay? 440 00:25:54,344 --> 00:25:58,309 So let me give you the intuition behind the quadratic algorithm that we can use 441 00:25:58,309 --> 00:26:02,152 for testing or making all these tasks, and the key idea is very, very simple, 442 00:26:02,152 --> 00:26:06,553 okay? So, what you want is that you want, so, 443 00:26:06,553 --> 00:26:10,633 so, so, let's put it this way, you want to look at one ending date and in one 444 00:26:10,633 --> 00:26:15,445 sweep, okay? So you want to compute all these task 445 00:26:15,445 --> 00:26:20,159 intervals that if e is the latest, the finishing time, okay? 446 00:26:20,159 --> 00:26:24,933 So in essence you look at this e, you fix e and then you're going to compute all. 447 00:26:24,933 --> 00:26:28,413 You're going to look at all the starting dates and take it, computing the 448 00:26:28,413 --> 00:26:33,310 feasibility for all the task intervals. You know, which if e, as the, as, as the 449 00:26:33,310 --> 00:26:36,654 ending date, okay? So in this particular case, what you are 450 00:26:36,654 --> 00:26:39,354 going to do, you are going to do e and then we going to, we going to look at 451 00:26:39,354 --> 00:26:43,460 this S, S3, S2, and S1. And we going to compute incrementally 452 00:26:43,460 --> 00:26:46,560 this task, by adding the duration and then, you know, performing the task, 453 00:26:46,560 --> 00:26:49,437 okay? So let me show you the algorithm, because 454 00:26:49,437 --> 00:26:52,510 the algorithm is going to make clear a couple of points. 455 00:26:52,510 --> 00:26:55,047 So we fix e, right? So e is fixed. 456 00:26:55,047 --> 00:26:57,240 And then we're going to look at the first task, okay? 457 00:26:57,240 --> 00:27:01,618 Now since we want a task interval, okay? And we say that e is the finishing date, 458 00:27:01,618 --> 00:27:06,140 we, will only consider S3, S3 is actually finishing before e, okay? 459 00:27:06,140 --> 00:27:13,450 So the latest finishing time of The task which started, you know, at S3, okay? 460 00:27:13,450 --> 00:27:15,520 Is, actually, you know, earlier than e. Otherwise, you know, it's not a task 461 00:27:15,520 --> 00:27:17,910 interval, okay? So if we have this guy, okay? 462 00:27:17,910 --> 00:27:21,530 So this is the test that you see here. We add the duration, okay? 463 00:27:21,530 --> 00:27:24,170 To the duration d, okay? So that, d, think of d as the 464 00:27:24,170 --> 00:27:28,610 accumulation of all the tasks that we are putting inside this task interval, okay? 465 00:27:28,610 --> 00:27:31,254 So this point, okay? So we have nothing, so we put the 466 00:27:31,254 --> 00:27:34,920 duration of S3, okay? So in other words, 3 is there, okay? 467 00:27:34,920 --> 00:27:38,127 And then we perform the test. But we are, you know, the only thing that 468 00:27:38,127 --> 00:27:41,284 we are looking at now is something which started as 3. 469 00:27:41,284 --> 00:27:44,028 So, we, we do the test S3 plus the duration and that is to be smaller or 470 00:27:44,028 --> 00:27:48,340 equal to e, okay? If it is, great, we are good, okay? 471 00:27:48,340 --> 00:27:52,070 Then you move to the next one, okay? And you're going to do exactly the same 472 00:27:52,070 --> 00:27:56,340 kind of test, okay? So what you are going to do is gonn, but, 473 00:27:56,340 --> 00:28:00,890 but now you are, you, you increase the duration so you have two tasks now, okay? 474 00:28:00,890 --> 00:28:04,292 And what you do is, once again it has to finish before e and, and, the key point 475 00:28:04,292 --> 00:28:07,640 here is that the only thing that you have to do from moving from S3 to S2, is to 476 00:28:07,640 --> 00:28:12,580 add the duration. And now we have another test and we know 477 00:28:12,580 --> 00:28:15,880 that S2 is the already starting date, so we don't have to make any computation to 478 00:28:15,880 --> 00:28:20,422 find which one is the minimum. We know that this guy is the minimum and 479 00:28:20,422 --> 00:28:23,737 thought we test essentially this task interval, can we actually put these two 480 00:28:23,737 --> 00:28:27,210 tasks be and complete them before e, okay? 481 00:28:27,210 --> 00:28:31,178 And so we, we, we, keep doing that for all the tasks, for all the, you know, 482 00:28:31,178 --> 00:28:33,810 [SOUND]. We go, we go like that, for all the tasks 483 00:28:33,810 --> 00:28:38,280 which are, all the starting date in that particular order, okay? 484 00:28:38,280 --> 00:28:41,194 Now this algorithm is going to be quadratic, obviously if the test fails at 485 00:28:41,194 --> 00:28:44,414 any point, okay? So you fail, and otherwise you would have 486 00:28:44,414 --> 00:28:47,169 a successful that particular value of e, okay? 487 00:28:47,169 --> 00:28:50,289 Now the other things that, I need to mention here is that, you will do that 488 00:28:50,289 --> 00:28:53,350 for all the e, okay? All these times, okay? 489 00:28:53,350 --> 00:28:57,550 And that, will, give you, an algorithm which is quadratic. 490 00:28:57,550 --> 00:29:00,610 Because it's linear, for every one, of these e. 491 00:29:00,610 --> 00:29:03,630 And it becomes quadratic because you have a linear of times of e, okay? 492 00:29:03,630 --> 00:29:08,181 So basically the intuition, you fix e And then you just do a sweep, okay? 493 00:29:08,181 --> 00:29:12,361 From right to left, okay? And that is basically how you reduce the 494 00:29:12,361 --> 00:29:18,360 complexity from cubic to quadratic, okay? Now, can we do better than that? 495 00:29:18,360 --> 00:29:21,350 Is it possible to actually improve on that again. 496 00:29:21,350 --> 00:29:24,610 Yes you can, okay? And I'm not going to prove all the 497 00:29:24,610 --> 00:29:28,130 results but there is a beautiful connection, okay? 498 00:29:28,130 --> 00:29:30,820 With something which is called preemptive scheduling, okay? 499 00:29:30,820 --> 00:29:34,360 Now I just want to mention this because this is another relaxation, okay? 500 00:29:34,360 --> 00:29:36,984 So so far, and i-, and it's a little bit the same thing as the linear relaxation 501 00:29:36,984 --> 00:29:40,330 although it's completely different, but anyway never mind, okay? 502 00:29:40,330 --> 00:29:44,042 So what we are trying to do here is that so far I implicitly, and this is the case 503 00:29:44,042 --> 00:29:49,620 in, in many problems assume that none of these tasks can be interrupted. 504 00:29:49,620 --> 00:29:53,420 But what happens if you can actually interrupt the task? 505 00:29:53,420 --> 00:29:56,668 If you can interrupt the task, essentially, checking feasibility 506 00:29:56,668 --> 00:30:00,140 becomes, you know, a very, a very simple problem. 507 00:30:00,140 --> 00:30:04,451 You can solve that in n log n time, okay? And the algorithm there would be very 508 00:30:04,451 --> 00:30:06,300 simple. It would look at all the tasks that you 509 00:30:06,300 --> 00:30:09,224 can schedule at any point, okay? Initially, there is only one, so you're 510 00:30:09,224 --> 00:30:12,326 going to schedule it A1, and then you're going to take the one which terminates. 511 00:30:12,326 --> 00:30:14,766 You know, which has the tightest deadline, and that's the one that you are 512 00:30:14,766 --> 00:30:18,124 going to schedule, okay? If at some point, a new task comes in and 513 00:30:18,124 --> 00:30:21,487 then you can schedule it, you will take the one at that point which can be 514 00:30:21,487 --> 00:30:25,620 scheduled. And which has, you know the the, the 515 00:30:25,620 --> 00:30:29,080 earliest, finishing, latest finishing time, okay? 516 00:30:30,320 --> 00:30:32,392 So in a sense what you do is that every step you look at the task you can 517 00:30:32,392 --> 00:30:34,685 schedule. And you take the one that's the tightest 518 00:30:34,685 --> 00:30:37,150 deadline and that's the one you're scheduling. 519 00:30:37,150 --> 00:30:40,350 So, this algorithm, this greedy algorithm for preemptive scheduling can be 520 00:30:40,350 --> 00:30:43,734 implemented in n log n. And basically solve feasibility for the 521 00:30:43,734 --> 00:30:46,490 preemptive problem, okay? Cool, right? 522 00:30:46,490 --> 00:30:49,550 And actually, you can show that you know, this is exactly the equivalent to all the 523 00:30:49,550 --> 00:30:53,730 tasks that I've shown you. Heck, good connection, right? 524 00:30:53,730 --> 00:30:57,080 Okay, so, now we have essentially good test, for testing feasibility, of course 525 00:30:57,080 --> 00:31:00,754 it's not complete feasibility. We can say, oh we believe it's feasible 526 00:31:00,754 --> 00:31:03,188 but it's not, okay? But the one I want to show you now are 527 00:31:03,188 --> 00:31:05,957 the rules for pruning, and they are truly beautiful, okay? 528 00:31:05,957 --> 00:31:07,730 So they are called, the edge finding rules. 529 00:31:07,730 --> 00:31:10,170 Okay, they are only one of the subset of rules that we can apply. 530 00:31:10,170 --> 00:31:12,530 There are other subset of rules that you can apply for pruning. 531 00:31:12,530 --> 00:31:15,850 But I'm just, you know, once again, I just want to make you curious, okay? 532 00:31:15,850 --> 00:31:18,473 And the key idea is that you're going to select a set omega, of tasks, and then 533 00:31:18,473 --> 00:31:22,280 you're going to select another task, i, okay, which is not in omega, okay? 534 00:31:22,280 --> 00:31:24,560 And the key point is that, look at this, okay? 535 00:31:24,560 --> 00:31:28,915 So you have the task, you have the task here in omega, and you have this task, i. 536 00:31:28,915 --> 00:31:32,307 And what you are wondering is that can this task be scheduled before, has to be 537 00:31:32,307 --> 00:31:36,570 scheduled always after, or always before the other tasks, okay? 538 00:31:36,570 --> 00:31:38,440 That's what you're going to try to do, okay? 539 00:31:38,440 --> 00:31:41,525 And how do you do that, okay? What you're going to do is simply add the 540 00:31:41,525 --> 00:31:45,280 task to the set omega and perform the ta, same tasks, okay? 541 00:31:45,280 --> 00:31:50,939 But, with one variation, right? So, you don't want the test to be to be 542 00:31:50,939 --> 00:31:58,259 such, so you want to the task to note you for the end date the task i, okay? 543 00:31:58,259 --> 00:32:01,049 So you're going to take the start, the earliest starting date of omega and the 544 00:32:01,049 --> 00:32:04,786 task i. So, i, start earlier so you can take it. 545 00:32:04,786 --> 00:32:07,841 You can take that starting date, you take the duration of all the tasks in omega 546 00:32:07,841 --> 00:32:11,497 and i. But then you test, if all these task can 547 00:32:11,497 --> 00:32:16,704 finish before the latest finishing task in omega, okay? 548 00:32:16,704 --> 00:32:20,532 Because you want to see if, you know, if I can be scheduled inside the middle, not 549 00:32:20,532 --> 00:32:26,840 the first, or, you know, before at least, at least one task inside the set omega. 550 00:32:26,840 --> 00:32:30,494 Now if this test tells you no, that basically means that the only way to 551 00:32:30,494 --> 00:32:34,715 satisfy the disjunctive constraints is to make sure that i is actually schedule 552 00:32:34,715 --> 00:32:39,390 after all the tasks. It has to be, you have to increase, you 553 00:32:39,390 --> 00:32:42,640 know, you have to increase the finishing date, that means that i is to be, i is to 554 00:32:42,640 --> 00:32:47,848 be the last task in, of all these sets. It has to be scheduled after all the 555 00:32:47,848 --> 00:32:51,090 tasks of omega, okay? So, in a sense, once you know that, you 556 00:32:51,090 --> 00:32:54,890 can update the starting time, and that's a big update, you'll see, okay? 557 00:32:54,890 --> 00:32:58,355 So you have, you, you, you have, you know that, you know, the task i is to start 558 00:32:58,355 --> 00:33:02,381 after all the tasks in omega. So, what you can do is to think the 559 00:33:02,381 --> 00:33:05,826 starting this over this task, and then the total duration, and you know, that i 560 00:33:05,826 --> 00:33:09,984 is to start after. Actually, you know something which is 561 00:33:09,984 --> 00:33:13,547 even better, you can take the maximum of all the subset. 562 00:33:13,547 --> 00:33:17,081 Because once again, you know, I can actually have pathological case where 563 00:33:17,081 --> 00:33:21,440 it's a subset of this task which gives you the best update. 564 00:33:21,440 --> 00:33:25,300 Not the, the set considering all of the tasks in omega, okay? 565 00:33:25,300 --> 00:33:27,645 So once you have something like this, okay? 566 00:33:27,645 --> 00:33:31,055 So you can apply these rules for the starting date and really pushing a task 567 00:33:31,055 --> 00:33:34,682 very far back. Or for the end date, you can push it, you 568 00:33:34,682 --> 00:33:39,348 know, a task forward, in a sense, okay? And these rules, what is beautiful is 569 00:33:39,348 --> 00:33:42,516 they can, you know, they can be, you can compute a fixed point of these, all these 570 00:33:42,516 --> 00:33:46,517 edge finding rules. of the propagation algorithm in strongly 571 00:33:46,517 --> 00:33:49,140 polynomial time. So this is, this is, so you have a very 572 00:33:49,140 --> 00:33:52,325 strong polynomial time algorithm for applying all these rules for all the set 573 00:33:52,325 --> 00:33:55,870 omega and all the other task, you know, i, okay? 574 00:33:55,870 --> 00:33:59,094 Which is kind of remarkable as well, because once again we have infinitely 575 00:33:59,094 --> 00:34:03,100 many of these sets, okay? So that's the beauty of the algorithm. 576 00:34:03,100 --> 00:34:05,929 You always have the impression that you rare computing exponentially many things 577 00:34:05,929 --> 00:34:08,281 but you can do it in polynomial time, okay? 578 00:34:08,281 --> 00:34:11,761 So let me show you an example of this same example as before, you know A1 A2 579 00:34:11,761 --> 00:34:15,721 A3, okay? What we are wondering is you know can A1 580 00:34:15,721 --> 00:34:21,579 be schedule, be schedule you know before on of these two tasks, okay? 581 00:34:21,579 --> 00:34:25,398 So what do we do, well the task that I've just shown you, is basically assumed well 582 00:34:25,398 --> 00:34:29,407 it cannot be scheduled after so basically reducing. 583 00:34:29,407 --> 00:34:32,055 I'm basically reduce, if we're moving all these values, okay? 584 00:34:32,055 --> 00:34:37,284 I'm reducing the finishing of A1 to the same as A3 and now I'm looking at these 585 00:34:37,284 --> 00:34:41,577 three tasks. Can they be scheduled in these time 586 00:34:41,577 --> 00:34:46,810 windows okay and here it's very easy to see that you cannot find that. 587 00:34:46,810 --> 00:34:50,260 Because you have essentially eleven spots and the total direction is stuck here so 588 00:34:50,260 --> 00:34:54,000 you are going to say ooh I can't schedule these guys there. 589 00:34:54,000 --> 00:34:58,880 That means that one can be scheduled before either tree okay because to be 590 00:34:58,880 --> 00:35:04,583 scheduled after everybody. So you push it by computing what is the 591 00:35:04,583 --> 00:35:09,620 earliest finishing time of this two. You know they take duration of seven. 592 00:35:09,620 --> 00:35:13,070 The first one they cannot be scheduled [SOUND], so this guy is pushed. 593 00:35:13,070 --> 00:35:15,180 And that's to be only in this interval, okay? 594 00:35:15,180 --> 00:35:18,690 So, these you know, these update roots are very strong because they are really 595 00:35:18,690 --> 00:35:22,038 pushing you know, the starting date or pushing the end date of a particular 596 00:35:22,038 --> 00:35:25,400 task, okay? Now, so this is basically the type of 597 00:35:25,400 --> 00:35:27,990 pruning that happens in the scheduling algorithm. 598 00:35:27,990 --> 00:35:29,974 So there are many of, you know many of other resource, resource types but they 599 00:35:29,974 --> 00:35:32,328 do essentially the same thing, pushing the starting date. 600 00:35:32,328 --> 00:35:37,406 You know, pushing the end date, okay? Now, the search is very interesting. 601 00:35:37,406 --> 00:35:39,626 Now, one of the things I told you in the beginning is that you don't need to 602 00:35:39,626 --> 00:35:42,502 actually find the starting time in this application, right? 603 00:35:42,502 --> 00:35:45,750 In Jobshop or as long as you have disjunctive constraints. 604 00:35:45,750 --> 00:35:49,550 What you need to do is basically, order the task on the machine. 605 00:35:49,550 --> 00:35:52,836 So the third strategy is, you know most of the time what it does is choosing a 606 00:35:52,836 --> 00:35:56,453 machine and then ordering the task in the machine. 607 00:35:56,453 --> 00:35:59,149 And then repeating that for the other machine, okay? 608 00:35:59,149 --> 00:36:01,430 That is a typical search procedure for that. 609 00:36:01,430 --> 00:36:04,233 Now you are going to say, which machine? And once again you're going to apply the 610 00:36:04,233 --> 00:36:07,369 first-fail principle that we always use in constraint programming. 611 00:36:07,369 --> 00:36:10,584 Which means all you're going to look at the machine which is tight, okay? 612 00:36:10,584 --> 00:36:13,320 So when you look at the sum of the duration of the task. 613 00:36:13,320 --> 00:36:17,032 And the flexibility that you have in the machine, that's the, you know, these 614 00:36:17,032 --> 00:36:21,236 tasks are really tightly packed inside that machine, okay? 615 00:36:21,236 --> 00:36:23,857 And then which task? Well, what one of the things that, the 616 00:36:23,857 --> 00:36:26,724 search algorithm are going to do is to try to find out which sort of task which 617 00:36:26,724 --> 00:36:30,478 can be scheduled first. And once again they will look at a task 618 00:36:30,478 --> 00:36:34,641 which are really tight or which have to be, you know, scheduled very early on. 619 00:36:34,641 --> 00:36:38,130 And so that's, that's what he's going to be, chosen is a heuristic. 620 00:36:38,130 --> 00:36:41,078 For actually just finding the other task is first on that machine or is before the 621 00:36:41,078 --> 00:36:44,110 other task, okay? So once again what you do here in this 622 00:36:44,110 --> 00:36:47,760 search procedure is exploit the structure of the problem, okay? 623 00:36:47,760 --> 00:36:50,684 So, this is it. What I'm going to do next time is 624 00:36:50,684 --> 00:36:55,963 actually show you some very interesting. You know, search strategies for exploring 625 00:36:55,963 --> 00:36:59,270 the search space of these scheduling problems. 626 00:36:59,270 --> 00:37:02,576 And I'm also going to give you a beautiful hybridization of constraint 627 00:37:02,576 --> 00:37:07,810 programming or map with local search which is really useful in practice, okay? 628 00:37:07,810 --> 00:37:08,780 See you next time.