So welcome to workshop seven. Here we're going to solve a scheduling problem, where it's about Liu Bei's third visit to Zhuge Liang. He's failed twice to convince Zhuge Liang to join him. This time he's doing all his homework and he's going to visit anyone who could help him. And so it's basically a scheduling problem with a few wrinkles, because some of the people can't be visited on the weekend. So, here's our data. We've got our set of people and how long they have to be visited, who can be visited on the weekend, their rank, which will come important in the objective, and a set of precedences. Just like a normal, basic scheduling problem. We've got which day the time period starts on, and the total amount of time. We're basically making sure we've got enough time to visit everyone. >> Right. >> And the key decisions, of course, in any scheduling problem, are what's the start time? And then we're trying to minimize the end time of the whole thing. Okay, the first thing we can do is- >> You have forgotten to talk about the objective. >> The objective? Well we'll get to the objective, but the objective is minimizing the end time. And that's most important, and then secondly, to minimize the number of rank violations, where we visit a person of higher rank before a person of lower rank. >> This is very important in the Chinese culture. >> All right, so the first thing we're going to do is make sure the precedences hold, and that's fairly straightforward. We've seen this constraint many times before. We're basically just looking at each of the precedence pairs, and ensuring that the end time of the first thing in that precedence pair… >> So let me try to understand, your notion of a time is the number of days from your starting day? >> Yes, so if the starting day is say a Tuesday, right? >> A Thursday I think. >> Well, that's in the data, yes the starting day is a Thursday in the data. Then that means day 0 in this TIME is a Thursday. >> Right, okay. >> All right, which means that day 1 is a Friday, day 2 is a Saturday. All right, so let's finish off our precedence constraint. So that's a constraint we've seen many times before. The end time of the first pair in this first guy in this precedence pair is before the start time of the second one. >> The second one, so it should be a 2. >> It should be a 2. >> [LAUGH] >> Yeah, very well seen. Now the other thing in this project, is there's one resource, that's Liu Bei himself. He can only be visiting one person at a time. So, we’ve got a unary resource, Liu Bei is not two people. And there's an obvious disjunctive constraint, all of these visits can't overlap. >> You also need a semicolon in include statement. >> I need a semicolon there as well. >> Yep. >> The power of pair programming. >> Yeah. >> Now, the more complicated part of this is, what are we going to do about these weekend people, the people that can't be visited on weekends? So we can imagine adding constraints where we could look at every person on the weekend and make sure that their task filled only within weekdays. But we can do it better than that by thinking about it as another kind of resource, all right? So we can basically think about these tasks, also need to use another resource, which is like non-weekend days. >> Or another kind of task, right? And then these tasks can overlap with the weekend tasks. >> Yeah, so we're basically going to build up some extra artificial tasks, which are weekends. And they're going to fill up that slot so that no one can be on the weekends. So that's the first thing we're going to do, we’re just going to build an array of the weekends basically. So the weekend_start, let's call it, So when does the weekend start? So we're going to look over all of the ts in TIME, and we're going to think about when all the weekends start. So if our starting day is 3, all right? >> Yeah. >> Then, the first weekend, the first Saturday, is day 2. >> Right. >> Right? So if we take the starting day and add t, then that mod 7 = 5 is basically giving us a Saturday. >> Because day 5 is a Saturday. >> Yeah, that's what our thing up there says. I can't get my thing to go onto the same line. It was on the same line, that's why, all right. But that's all I need to do. Except now, yes. All right, so that's the weekend starts. But of course, these are going to be tasks that we use in a disjunctive constraint, so we also have to have their duration. So let's have an array of durations. And we now know how many, of these we need, which is just this number of elements in the weekend_start array. These are integers. They are length 2. Let's just say i in 1..length(weekend_start). I haven't given this variable a name. >> Exactly. >> Let's say- >> You're typing too fast. >> [LAUGH] Typing too fast and thinking too slow. >> [LAUGH] >> So that's the weekend durations, all right? So the other thing we need to do for these is that these tasks can’t overlap with any of the people who can't be visited on the weekend. So we're going to have to extract those people. So we're going to get the start times for those people, so let's call it notweekend_start. So we're just going to extract the start times for the people, that can't be on the weekend. So, on_weekend is it? >> Better go and take a look at the name of the variable. >> p equals false. >> Right. >> Pretty sure. >> Yeah, on_weekend, yes. >> That's the name, on_weekend, yep. And of course we need to also extract the durations, because we're going to use them in a disjunctive constraint. So that's going to be almost exactly the same except here. Well they're not going var TIME, they're going to be integers. And we have just extracted the weekend times. Okay, now we can constrain them. Now we have to convince ourselves that basically none of these tasks should be able to overlap. If I can type these big names. So that's the start times of all these artificial tasks for weekends, and the tasks which are not allowed to be on the weekends. And the second argument is, of course, the durations of these things. All right, so at this point we might want to actually just run and see if everything is correct, okay? Find our typos. So we've put an extra bracket there for no discernible reason. Now we can run, and we seem to be getting something. There's a problem here. So we haven't constrained our end time. Obviously we need to add some constraints to make sure the end time is after every other task. So forall(p in PERSON), if we take the end time of p. All right, that should be able to do that. All right, so now we're getting a schedule that looks good. But we haven't done the objective, or actually, it looks like we're getting the minimal time anyway. >> Uh-huh. >> So I must have a solve somewhere, otherwise it wouldn't have run. So what we're trying to do is minimize the end time plus the rank violations, right, but we gotta work out what that rank violations is. So it's easy enough to work out the rank_violations, because we're just summing up, we're looking at all pairs of people, Where the rank of person p1, is greater than the rank of person p2, so that's a more important person. But they're visited beforehand. >> Right, and that's a no no. >> Well it's going to have to happen actually. The data is going to force this to happen sometimes. So we're not going to get away with zero rank violations. But now we have to think about this objective. So minimizing the end time is the most important thing, so how can we do that? Well, we have to think, how big can the rank violations be? >> Right. >> So basically, we know, actually it can only be- >> n choose two? >> Yeah, the number of people there are choose two. But rather than work out exactly what n choose two is, let's just multiply, the more important objective by the number of people squared, which is bigger than n choose two. >> So essentially, we only have to multiply a number that is big enough. >> Exactly, any number that is big enough so we know that the rank violations can't be as big as the person squared. So that means that we'll always be minimizing the end time before we worry about the rank violations. All right, so if we run our model now, we hope to get the right answer. >> Yeah. >> Well so we’ve got an answer, not the same as the one in the course. >> But the same objective. >> The same end time, but a different number of rank violations. >> 12. >> Okay. >> Yeah, so perfect. >> No, I think we can do better than that. >> Yeah? 37 and then 5. >> Yeah, so let's see if we're calculating the rank violations correctly. We've got two people, the rank of p1 is greater than the rank of p2, and the start of p1, ah...is greater than... is less than, right? >> Okay. >> So we had written the wrong definition of rank violations, all right. >> There's the value we expect. >> All right, so that brings us to the end of workshop seven. We won’t show you how to do the fancy output, but that's available in the files.
