Discrete Optimization, Constraint-based Scheduling. So what I'm going to do today is talk about one of the most fascinating areas, area, areas of Discrete Optimization, which is Scheduling. There are entire books on this, there are journals just on this topic, but what you're going to see, what I'm going to try to do is to make you curious. So that you can learn more about these things. There are beautiful algorithms, beautiful search techniques, and you'll see some of them. So I hope, you know, I'll get you excited about this area, because it's at the same time beautiful scientifically, and there's a lot of application in practice. So what I'm going to do is talk only about scheduling of you know, using Constraint Programming. There are also an entire branch of scheduling using, you know, mixed integer programming, local search and so on. But, you know, this is, this is one of the areas where lo, you know, constraint programming has been really, really very successful. I'm going to talk about, modeling a little bit. About global constraints and telling you, you know, you'll see some very interesting issue arising in this context. And you'll see a lot of very nice techniques behind the scene. Okay? So as I said, it's a very, successful application area for constraint programming. And one of the reason is that you can use all the flexibility of constraint programming. These problems are typically very complex. And you have a lot of different kind of, of constraints, and you can put them together using constraint programming, okay? So this is a typical example of what you can have in this area. So you are minimizing the duration of a big project, and that project has a lot of things to schedule, okay? So, and they are different precedence constraints between them, so some task has to come before others, and so on. And also you know, some of these tasks are going to use the same resources. And so sometimes the can overlap in time, or you know, several of them can overlap in time and things like this, okay? So this is the kind of problems that we are going to look at, okay? So this is an example, okay? So we want to build this bridge. [SOUND], okay? So typically we can't do it in one step, okay? So there variety of tasks, oops. No I, I want to do this again, because you, you missed the best part here. Okay, so we don't want to build that bridge like this. You see that little truck? Okay, anyway. so you have various tasks that you see here, okay? So obviously you have to build the bottom, you have to do the excavation before you can actually do the pillars and so on. And so, so you have precedence constraints between some of these tasks. You can build the top of the, of the bridge before the bottom and then obviously some of these tasks are going to use exactly the same resources. And they, they have to share that. And that's going to put some constraints on how you can actually schedule all these different activities for building this bridge, okay? So that's the kind of problems that we are looking at, okay? of course you have other problems in the steel industry and paper industry, all these things, you know, typically are scheduling problems like that. So typically when you model these problems, these days, what, you know, let's say, constraint programming languages or local search. You know, algorithm are doing is basically building abstraction just for that particular area. It's so big that you want this dedicated language that I'm going to talk about activities, and resources, and things like that. So we sometimes call this model-based computing, okay? It's going to make it easier to actually state the problem, okay? So you'll see, you know, concepts of activities, resources, and I'm going to give you, you know, a sense of what this looks like, although I won't go into the details, okay? Precedents, constraints and so on and so forth. Now behind the scene of use with these are going to be compiled into decision variables and global constraints, and things like this, okay? So, essentially that's a high level language which is compiling to you know, the typical language of constraint programming behind the scene. And then also you know, this concept are going to support dedicated search algorithm. Because we can exploit some of the structure that you have In these applications. And I will talk a little bit about that. But there is much more, you know, behind the scene, and I want to be able to talk about all the techniques that we can use here, okay? So, you know, one of the things that is, you know, the TSP, of, scheduling is called the Jobshop scheduling problem, okay? So it's probably the simplest, scheduling problem but it's also very hard, okay? But it's very simple to state, and people have been competing on this forever, okay? So there are a lot of standard, you know, benchmarks on this, and there are also a lot of open problems. It's not very difficult to actually generate instances that nobody can solve optimally, okay? So what I'm going to give you now is, you know, in two pages, it's in two slides. I'm going to give you the specification of the problem. I'm obstructing some of the fac, you know, some of the right information this slide. But essentially what we have is we have a set of tasks that we have to schedule, okay? And every one of them is a duration, okay? So we know, we're going to assume that we know the duration, it's fixed in this particular case. Now,w e also know that every task is actually usually one resources. This is a simplification right, in real life they typically use different resources, but here they only use one resource, one machine, okay? And we specify which machine that, you know, every task is using. And then we have a set of precedence constraints, okay, of the type (b,a), okay? Which basically means that a can only start after b has completed execution. So you have to finish b before you can start a, okay? So think about it in this, like, Excavating before you start building the bridge, right? And so, these are essentially the data and the various constraints. And what you want to do is schedule all these tasks so that you minimize the project completion time. The er, you know want this project to finish as early as possible. Now in the jargon of optimi, of, of scheduling, this is called a mixed time, okay? But this is one of the very famous objective, there are many others, okay? One of the most studied objective function for scheduling, okay? So let me give you a picture of that so can really what the jobshop is, okay? The constraints are coming form the job. So everyone of these a result of the lines you see on this slide, okay. So these are basically the jobs, okay? So you know, this is let's say the starting of the project. Then you see you know, this is the sequence of tasks inside a job. And the semantics here is that you know, this task is to be completed before the second one started. And after, the second one has to be completed before the third starts and so on and so forth. So this a way to you know, the precedence concerns are coming from, okay? So, they are coming from these jobs which are basically sequences of activities. And then what you see, the colors that you see in this, is, in this, in this pictures. In this picture are basically the machine that every one of these activity has to use, every task has to use, okay? So basically all the tasks which are color in yellow, I have to use the same machine, okay? So I am also showing you here you know, all the tasks of a particular machine that I basically call a machine kit, okay? So all these tasks use are, are using basically the same machine and therefore they cannot overlap in time, okay? You know, every two, every two of them. You know, we have to satisfy the fact that one is to be before or after the other, okay? So basically when you think about that, okay? So for solving these problems one of the things that you have to find out is in order for every one of these machines. And what I have shown you on this slide is basically all the possibly links between every two tasks using that machine, okay? And so what we have to do is to choose a subset of them, which are basically. You know, making a sequence, okay? And so is, so, so in a sense the way to think about this, is that a machine, has to handle all these tasks sequentially. They can be ordered in an arbitrary fashion. Of course, you know, you have to satisfy the present constraints on the jobs. But, but mostly what you're doing is trying to find for every one of these machine, an ordering of all these tasks, okay? So this is one of them, for instance, okay? So you start, you know, over there, and then you go over, ooh, where do we go? we go over, let me see. This is really difficult to see. We go here, and then [LAUGH] we go, we go down and then we go up, and so on and so forth, okay? So you basically have one ordering for that particular machine. All the Tasks here are basically ordered and, and the machine as, as very, you know, as a well defined order, ordering for every one of the task, okay? So this point, if you do that for all the machine, if you order all the machine, the only thing that you are left with are what? You are only left with these precedence constraints, okay? So you have this big graph know, we have all the original precedence constraints and every one of them which comes from the ordering of the machines, okay? And so this point, you know, I have a problem where the only thing I have to do, is to minimize the project duration subject to precedence constraints. And the beautiful thing is that this is a polynomial time problem, okay? We can solve this problem in polynomial time, okay? So we can use topological sorting which is called in that popular a literature of the PERT algorism. Or you know it, it the precedence contraints that are most sophisticated they have also distance. You would use transitive closure, but essentially this problem can be solved fast, you know, importing and obviously in polynomial time, okay? So in a sense the only thing we have to do in this particular problem is order the, you know, the machine. You don't have to choose a starting date, okay? So this step here at the end is going to do that automatically, okay? So you just have to find out the right ordering for all the task on everyone on the machine, okay? So let me show you an example of, you know, a constraint programming model for this particular, for this particular problem. So the, so, so once again, I don't want you to understand this in detail. What I want to show you here, and, and illustrate is the kind of languages that people have built for modeling these applications scheduling. These applications in a high level, okay? So the beginning here the first three line are boring basically here the data and description for every job and every task in that job you have a duration. Then you have the machine for which that particular task. On that particular job he's executing, we compute a time horizon, which is basically the longest time we can schedule all these activities. And so this is basically data, it's basically boring. What is a little bit more interesting here, okay? Is basically the description of, at a high-level, the decision variables, and some of the, the, the resources that, that are going to use for stating the constraints. So what you see there is that we are basically defining a schedule, and then we are basically defining these activities, okay? So for every job, and every task in the job, we are defining that activity and that activity is a particular duration, okay? So this is a concept, you know, this activity of the end of the date /g, will have a starting date and an ending date. And this isn't the level at which we want to rezone here, okay? So we want to be thinking about this activity, its starting date, the end date, possibly the duration if it's not fixed, okay? And we are basically expressing that as a high-level concept on which we want to express the model, okay? We also have an activity which is makespan, that's essentially the completion time of the project, it has duration zero. That is basically a dummy activity that we are putting at the end. And we put a precedence constraint of all the tasks, essentially, to that particular activity. Then we have here is a unary resource. We are, this is basically something that tells you that if there are various tasks which are actually using that resource, they won't be able to overlap in time. You will have to schedule one before the other, okay? So basically, you know, the description of your decision variables and the various. You know, act, you know, resources that you will use for stating the problem, okay? The rest is very much like the constraint programs that we have seen before. What we are doing is minimizing the end date of the makespan, okay? So it's the same as the starting date because the duration is zero, okay? So that's the, that, that's essentially modeling the end, you know, the duration of the project. And then what you see there are basically the various constraints, okay? So the first set of constraints I'm basically the precedent constraints inside this job okay and so you look at all the job and all the tasking in that job, okay? so you are setting that task t and job j as to precedes task t plus one in that same job j, okay? So, that's basically what you are seeing, you know of course, you know the system here understand, what it means to be a precedent constraints. And it will translate that into a simple inequality and I'll show you that in that next slide, okay? The last part that you see here, okay? So the, the next, you know, in between the two here you will, you know, these are the precedent constraints for saying that the makespan is after every one. But these are basically the resource constraints for every one of the task and every one of the job. You are basically specifying which resources they are using, okay? And therefore as you know that, you know, no task can overlap on these resources. You are basically specifying implicitly the, you know, the kind of disjunctive constraints that this problem has to satisfy, okay? So that's at the high-level, the kind of modeling that you have is this scheduling application. Of course, in practice, the resources are typically more complicated, the precedence constraints are more complicated. There may be additional side constraints, and things like this. But this is kind of the, you know, the simplest scheduling problem is the TSP of scheduling problems, okay? Now, behind the scene, this model, this high level model is compiled into a particular set of cons, decision variables and constraints, okay? So in a sense, you, you have to think about it, every activity has three variables. The starting date, okay, of that particular, of that particular activity, the duration of that activity, and the end date of that activity. Okay, so in a sense every variable can be thought of as three of, three variables. The starting date, the end date and the duration. Now, they have redundancy specially if the duration is fixed but, you know, they are basically... We typically use these three because it's really convenient for expressing some of the algorithms. Of course you have a constraint linking them. OK, the constraint is basically stating tha tyou know the starting date plus the duration is equal to the end date. OK, so in a sense an activity you have to think of it as giving you three you know interdependent decision variables linked that way by this constraint. Okay then the other things how to express the precedence constraints, if you have precedence constraints between b and a, okay? So simply it's become a very simple tiny inequality that Sa has to be greater or equal to a or b, okay? It's very simple, okay? The most interesting part here, and that's what I want to focus a little bit, you know, about in the la, the, the last part of the lecture, is the resource constraint. So these resource constraints are going to be compiled, into global constraints which are disjunctive, here, okay? And they are basically specifying that all the, all the activities there, t1 to tn basically cannot overlap in time, okay? So, this sys, this disjunctive constraints here which is really important. So, if you think in terms of the constraint programming model that I've presented in this class earlier, okay? Everyone of these precedence constraints is one of these guys, okay? And then you have also the global constraints, every disjunctive constraint for every one of the resources is going to be one of these constraints. And, of course, they are going to interact through the decision variable, which are the starting date, the end date. And not the duration because they are fixed, but, but essentially the starting and the end dates of every, end dates of every one of the activities, okay? So that's basically the, the, the, the overall model, what's happening behind the scene. What I want to focus on in the rest of the thing, because this is truly beautiful Is, the disjunctive constraints. And how you can actually, how you can actually implement algorithm that are pruning and, and, pruning effectively the search base. For this disjunctive constraints. So this is, so I'm going to illustrate that, all, you know some of this issue, on a very simple example, okay? So we have three activities that are requesting that resources. Okay so what is duration, six. The other one four the last one three. And what you see there is essentially the time window in which they have to be scheduled, okay? So, this is for instance for the, for the, for the ti, four times three, this is the earliest starting time at which that task can start, okay? So, let's say one, okay? And this is the latest finishing date for that particular task, okay? So in a sense, this is the minimum value in the domain of the starting date. This is the largest value in the domain of the ending, you know, variable, of the activity, okay? So every one of these guys can be scheduled anywhere in that time window, okay? So and what we have to do is to choose where to place them Such that they don't overlap in time, okay? And we have to find out, if this is feasible, okay? And how fast we can do that. Now there is one very interesting thing here. Is that, even the simple, one machine problem, is NP-hard, okay? Which is like, so I did, you know, this beautiful model with this disjunctive global constraints. And there is no way I can test this ability in polynomial time. So what are we going to do? Okay, so we could totally compose these thing into very tiny disjunctive constraints, okay, And you could verify this one in polynomial time, okay? But that basically looses. The, the entire globality of the problem. So, so you really don't want to do that because you will get nowhere in trying to solve practical problem. So what we going to do is that instead of solving this problem exactly, we will relax those tenders. And are we going to show you that. In a moment okay so there are a lot of algorithms to do that. I'm going to just make you curious here, okay? And give you basically the intuition behind some of them. And you know put them some connections and entire set of algorithms in this space, okay? And I'm going to use a little of notation. In think it's intuitive but I'm going to go slowly and because we are doing something which are a little bit fan, you know, fancy here, okay? So, I'm going to, I'm going to to, so, so, omega here in this, all, this formula in this subsequent slide, okay? Is a set of task, okay?? And so I'm going to denote s of omega.Think starting date of omega, okay So that's the earliest time at which one of the tasks inside omega can stop, okay. And the way I can compute that is that I look at all the task in omega and I take the one which is the strongest. Smallest possible value in the domain of its starting date. That's what I'm doing. So, when you see s omega, it's the earliest time at which any of these tasks in Omega can start, okay? Then e omega, okay? So, is just the opposite for the ending dates, okay? So, I'm basically look, e omega is the littlest finishing time of all the task in Omega. So, I taking a max overall of this of the maximum value the end value, okay? Of every one the activities, okay? And then the duration of these activities are a little bit interesting as well, okay? So the duration of omega is essentially the sum of all the duration of the tasks in omega, okay? So, you know, remember this notation because we are going to use it over and over and over again, okay? So s omega, earliest starting date of this set of tasks. E omega, that's basically the latest edition date of any of the tasking omega. And d omega is basically the long duration of all the tasking omega, okay? So, so what I'm at this point what we have is that we are trying to find if these constraints is feasible. That's one of the things that the constraints have to do, this disjunctive constraint, is it feasible? We know that this is a hard problem and we are not going to, we are not going to try to solve it. What we are going to do is now approximated efficiently, okay? Well, approximated somehow. And so this is the test, this is the first test that I'm proposing ,okay? To check if a set of tasks can be scheduled on this machine, what I'm going to do is check this little inequality. I'm going to, check that sT plus the duration of T, okay? Is more or equal to eT, okay? You know not eT right, e of T, okay? So, sT is basically the earliest starting date of T, okay? That's the total duration of all the task, and I will be sure that when I add these two things, I can fit them before the latest finishing date of all these tasks, okay? So in the sense, when you look at this picture here, okay? So this is the earliest starting time, okay? This is the latest finishing date, okay? And then you add all the duration of this task, that's basically the solid line inside every one of these tasks. And I want to be sure that when I sum the duration, you know and I add that to the starting date. I'm you know, terminating before I'm ending before the, the latest has ended, okay? That's basically what you're testing here, okay? So the question I have for you is that is this an effective test? Is this something that's going to detect feasibility or, you know, reasonably well, okay? And so one of the things that I told you in the first lecture of this class, right, is that, you know, when you have a question like this. What you have to do is to exaggerate, okay? So I'm going to exaggerate, okay? So this is a set of tasks. Here they have no duration. Well, the duration is fixed and the, the starting there is fixed, okay? And I have this guy this little guy who is all alone okay and seems to be really tight. They don't have much space to be scheduled okay so this is not feasible, okay? If you look at this task you can't schedule that. But because I added this very isolated guy notice that the. Notice that the earliest date is here, the latest finishing date is there. Obviously I have a lot of space here so I will be able to schedule. So essentially I have this I'm always going to say, yes it's feasible, okay? I believe it's feasible. Of course I don't, ever prove but, I, you know, my test is going to say yes, you know, I can prove in feasibility, okay? So, in a sense, this is a terrible test, okay? I can, I can make it arbitrarily bad by adding some task that are basically doing nothing. So we don't like that, we want the system to be robust. So one of the things that we can do is that, you know [LAUGH], you tried to, you know, annoy me, it's like during the relaxations, right? So what we want to do is have a test which you cannot annoy so easily. And what we do, this is another version of the test, but instead this time instead of just looking at the set T, I want to look at all of the subset of the tasks inside T, okay? So once again if I look at my basic set that I've shown you, ok, I want to look if that subset is feasible, okay? if that subset if feasible, if this subset is feasible, and so on. So for every possible subset of the tasks, I will apply the test that I've shown you on the previous slide, okay? And which is, you know, obviously here as well, okay? So that's what I want to do. I don't want you, because there is the one task in my project which is scheduled very, very late, I don't want you to, I don't want the test to always say yes. Here I want to be sure that the test is, you know, looking at all the possible subsets and detecting feasibility for any of these subsets, okay? Good, it looks good, right? No, what is the issue? So how many subsets do you have in a set? Well, you have exponentially many, okay? So now we would have to, you know, run an exponential number of sets And that doesn't sound too good, okay? But, but there is something which is really interesting in the structure of this set, okay? And in practice you only have to look at the quadratic number of them. And I'm going to give you the intuition, right? So this is all the task of my problem again, okay? But now I put some dash lines for everyone of them, okay. So in these dash lines, okay? Are denoting the starting date and the end date, okay? And the late, the earliest starting date, and the latest finishing date or end date of everyone of these tasks, okay? And what I'm going to show you is that you basically consider a quadratic number of tasks. Which are basically optimized by choosing a starting date and choosing an end date, okay? That's going to give you two tasks and I'm going to show you how to compute the tasks okay? So this is the intuition, two red tasks okay so you see this one and that one, okay? So, and so you see the starting date there and you see the end date there, okay? So, when you see this test, okay? Obviously you have the starting date and you have the end date, okay? And now look at this task in the middle, okay?? So, I am not considering it right, and now what I am claiming is that I can put it, okay? I don't have to, I will never have to ever test taking this task and that task together, okay it's completely useless to consider that subset, why? Because if I take this, if I take, you know, if I add this task to these two tasks here, what's going to happen? I'm not going to change the starting date. I'm not going to change the end date because this is in the middle. The only thing that I'm doing here is essentially increasing the duration. So, I'm making this task stronger, okay? So, essentially what I'm saying here is that I can, you know, I ca, well, when I have these three task, okay? So, I don't have to look at the subset of them because this task that I'm considering now we have the three of them, I'm going to subsume all of them. This is going to be stronger. Because it has the same start in there, the same ending, but I'm increasing the duration, okay? So in a sense to actually find out what are the subsidized need to look. I take a starting bid. I take a end bid and then I pack everything in it okay which means that the starting date has be after and the end that has to be before. And that's that stuff that I have to look for, okay? So, this is something that Cazzo and Lavorlt called task intervals, okay? So if you take two tasks, t1 and t2, then you lift essentially as many tasks as you can inside, okay? So you take all the task t, whose starting date after, you know t1, the starting date of t1 and before the end date of t2, okay? So you have this you know, task intervals, that are basically, out of strongest, set this, this, this strong subset that you want to look at, okay? And now basically the feasibilities that you see here, eh, can only focus on all these task intervals. They never have to look at anything else, okay? So you look at all the task intervals for ever pair of, of, of task, and that's what you, the, the, the, that's on this task interval that you apply the task. You don't have to look at any other subset, okay? And so the complexity of [UNKNOWN] here is that, you have a quadratic number of this, you know, inter-, task intervals. And the test, itself, is linear time. So you have an algorithm which is in cubic time. Now, cubic is pretty high. So, we ought to try to, to, to do better than this and I'm going to show you one you know, one in, one algor, one, some of the intuition on how you can do better, okay? So, I'm only going to show you one algorithm here which is going to be quadratic, okay? But, you can do better in practice and, and here you can do and log and in general, okay? So let me give you the intuition behind the quadratic algorithm that we can use for testing or making all these tasks, and the key idea is very, very simple, okay? So, what you want is that you want, so, so, so, let's put it this way, you want to look at one ending date and in one sweep, okay? So you want to compute all these task intervals that if e is the latest, the finishing time, okay? So in essence you look at this e, you fix e and then you're going to compute all. You're going to look at all the starting dates and take it, computing the feasibility for all the task intervals. You know, which if e, as the, as, as the ending date, okay? So in this particular case, what you are going to do, you are going to do e and then we going to, we going to look at this S, S3, S2, and S1. And we going to compute incrementally this task, by adding the duration and then, you know, performing the task, okay? So let me show you the algorithm, because the algorithm is going to make clear a couple of points. So we fix e, right? So e is fixed. And then we're going to look at the first task, okay? Now since we want a task interval, okay? And we say that e is the finishing date, we, will only consider S3, S3 is actually finishing before e, okay? So the latest finishing time of The task which started, you know, at S3, okay? Is, actually, you know, earlier than e. Otherwise, you know, it's not a task interval, okay? So if we have this guy, okay? So this is the test that you see here. We add the duration, okay? To the duration d, okay? So that, d, think of d as the accumulation of all the tasks that we are putting inside this task interval, okay? So this point, okay? So we have nothing, so we put the duration of S3, okay? So in other words, 3 is there, okay? And then we perform the test. But we are, you know, the only thing that we are looking at now is something which started as 3. So, we, we do the test S3 plus the duration and that is to be smaller or equal to e, okay? If it is, great, we are good, okay? Then you move to the next one, okay? And you're going to do exactly the same kind of test, okay? So what you are going to do is gonn, but, but now you are, you, you increase the duration so you have two tasks now, okay? And what you do is, once again it has to finish before e and, and, the key point here is that the only thing that you have to do from moving from S3 to S2, is to add the duration. And now we have another test and we know that S2 is the already starting date, so we don't have to make any computation to find which one is the minimum. We know that this guy is the minimum and thought we test essentially this task interval, can we actually put these two tasks be and complete them before e, okay? And so we, we, we, keep doing that for all the tasks, for all the, you know, [SOUND]. We go, we go like that, for all the tasks which are, all the starting date in that particular order, okay? Now this algorithm is going to be quadratic, obviously if the test fails at any point, okay? So you fail, and otherwise you would have a successful that particular value of e, okay? Now the other things that, I need to mention here is that, you will do that for all the e, okay? All these times, okay? And that, will, give you, an algorithm which is quadratic. Because it's linear, for every one, of these e. And it becomes quadratic because you have a linear of times of e, okay? So basically the intuition, you fix e And then you just do a sweep, okay? From right to left, okay? And that is basically how you reduce the complexity from cubic to quadratic, okay? Now, can we do better than that? Is it possible to actually improve on that again. Yes you can, okay? And I'm not going to prove all the results but there is a beautiful connection, okay? With something which is called preemptive scheduling, okay? Now I just want to mention this because this is another relaxation, okay? So so far, and i-, and it's a little bit the same thing as the linear relaxation although it's completely different, but anyway never mind, okay? So what we are trying to do here is that so far I implicitly, and this is the case in, in many problems assume that none of these tasks can be interrupted. But what happens if you can actually interrupt the task? If you can interrupt the task, essentially, checking feasibility becomes, you know, a very, a very simple problem. You can solve that in n log n time, okay? And the algorithm there would be very simple. It would look at all the tasks that you can schedule at any point, okay? Initially, there is only one, so you're going to schedule it A1, and then you're going to take the one which terminates. You know, which has the tightest deadline, and that's the one that you are going to schedule, okay? If at some point, a new task comes in and then you can schedule it, you will take the one at that point which can be scheduled. And which has, you know the the, the earliest, finishing, latest finishing time, okay? So in a sense what you do is that every step you look at the task you can schedule. And you take the one that's the tightest deadline and that's the one you're scheduling. So, this algorithm, this greedy algorithm for preemptive scheduling can be implemented in n log n. And basically solve feasibility for the preemptive problem, okay? Cool, right? And actually, you can show that you know, this is exactly the equivalent to all the tasks that I've shown you. Heck, good connection, right? Okay, so, now we have essentially good test, for testing feasibility, of course it's not complete feasibility. We can say, oh we believe it's feasible but it's not, okay? But the one I want to show you now are the rules for pruning, and they are truly beautiful, okay? So they are called, the edge finding rules. Okay, they are only one of the subset of rules that we can apply. There are other subset of rules that you can apply for pruning. But I'm just, you know, once again, I just want to make you curious, okay? And the key idea is that you're going to select a set omega, of tasks, and then you're going to select another task, i, okay, which is not in omega, okay? And the key point is that, look at this, okay? So you have the task, you have the task here in omega, and you have this task, i. And what you are wondering is that can this task be scheduled before, has to be scheduled always after, or always before the other tasks, okay? That's what you're going to try to do, okay? And how do you do that, okay? What you're going to do is simply add the task to the set omega and perform the ta, same tasks, okay? But, with one variation, right? So, you don't want the test to be to be such, so you want to the task to note you for the end date the task i, okay? So you're going to take the start, the earliest starting date of omega and the task i. So, i, start earlier so you can take it. You can take that starting date, you take the duration of all the tasks in omega and i. But then you test, if all these task can finish before the latest finishing task in omega, okay? Because you want to see if, you know, if I can be scheduled inside the middle, not the first, or, you know, before at least, at least one task inside the set omega. Now if this test tells you no, that basically means that the only way to satisfy the disjunctive constraints is to make sure that i is actually schedule after all the tasks. It has to be, you have to increase, you know, you have to increase the finishing date, that means that i is to be, i is to be the last task in, of all these sets. It has to be scheduled after all the tasks of omega, okay? So, in a sense, once you know that, you can update the starting time, and that's a big update, you'll see, okay? So you have, you, you, you have, you know that, you know, the task i is to start after all the tasks in omega. So, what you can do is to think the starting this over this task, and then the total duration, and you know, that i is to start after. Actually, you know something which is even better, you can take the maximum of all the subset. Because once again, you know, I can actually have pathological case where it's a subset of this task which gives you the best update. Not the, the set considering all of the tasks in omega, okay? So once you have something like this, okay? So you can apply these rules for the starting date and really pushing a task very far back. Or for the end date, you can push it, you know, a task forward, in a sense, okay? And these rules, what is beautiful is they can, you know, they can be, you can compute a fixed point of these, all these edge finding rules. of the propagation algorithm in strongly polynomial time. So this is, this is, so you have a very strong polynomial time algorithm for applying all these rules for all the set omega and all the other task, you know, i, okay? Which is kind of remarkable as well, because once again we have infinitely many of these sets, okay? So that's the beauty of the algorithm. You always have the impression that you rare computing exponentially many things but you can do it in polynomial time, okay? So let me show you an example of this same example as before, you know A1 A2 A3, okay? What we are wondering is you know can A1 be schedule, be schedule you know before on of these two tasks, okay? So what do we do, well the task that I've just shown you, is basically assumed well it cannot be scheduled after so basically reducing. I'm basically reduce, if we're moving all these values, okay? I'm reducing the finishing of A1 to the same as A3 and now I'm looking at these three tasks. Can they be scheduled in these time windows okay and here it's very easy to see that you cannot find that. Because you have essentially eleven spots and the total direction is stuck here so you are going to say ooh I can't schedule these guys there. That means that one can be scheduled before either tree okay because to be scheduled after everybody. So you push it by computing what is the earliest finishing time of this two. You know they take duration of seven. The first one they cannot be scheduled [SOUND], so this guy is pushed. And that's to be only in this interval, okay? So, these you know, these update roots are very strong because they are really pushing you know, the starting date or pushing the end date of a particular task, okay? Now, so this is basically the type of pruning that happens in the scheduling algorithm. So there are many of, you know many of other resource, resource types but they do essentially the same thing, pushing the starting date. You know, pushing the end date, okay? Now, the search is very interesting. Now, one of the things I told you in the beginning is that you don't need to actually find the starting time in this application, right? In Jobshop or as long as you have disjunctive constraints. What you need to do is basically, order the task on the machine. So the third strategy is, you know most of the time what it does is choosing a machine and then ordering the task in the machine. And then repeating that for the other machine, okay? That is a typical search procedure for that. Now you are going to say, which machine? And once again you're going to apply the first-fail principle that we always use in constraint programming. Which means all you're going to look at the machine which is tight, okay? So when you look at the sum of the duration of the task. And the flexibility that you have in the machine, that's the, you know, these tasks are really tightly packed inside that machine, okay? And then which task? Well, what one of the things that, the search algorithm are going to do is to try to find out which sort of task which can be scheduled first. And once again they will look at a task which are really tight or which have to be, you know, scheduled very early on. And so that's, that's what he's going to be, chosen is a heuristic. For actually just finding the other task is first on that machine or is before the other task, okay? So once again what you do here in this search procedure is exploit the structure of the problem, okay? So, this is it. What I'm going to do next time is actually show you some very interesting. You know, search strategies for exploring the search space of these scheduling problems. And I'm also going to give you a beautiful hybridization of constraint programming or map with local search which is really useful in practice, okay? See you next time.