Liu Bei wanted to supervise the tasks being completed to ensure they were done well. That was, purchasing the raw materials for weapon production, making bricks for the wall, weapon casting, and wall building. Because Liu Bei couldn't supervise all tasks at once, the completion schedule had to be redesigned. Zhuge Liang pulled out the tablet. [NOISE] >> So Liu Bei is concerned about increasing his defenses and he thinks he should do some quality assurance on some of the task that are happening. So he wants to look at the raw materials that are collected for the weapons and the casting process. He wants to look over the bricks and mortar that are built and the defense building up the wall using those bricks and mortar. So what is happening here is we are adding a new kind of construct to our scheduling problem, which is a resource. So in this case Liu Bei is a resource. So we have two different kinds of resources, unary resources basically say that at most, one task at a time can happen with this unary resource, any one of one thing can happen. We have a another kind of resource which we'll look at later which are called cumulative resources where we're going to limit the amount of resource that is available at any time. So unary resource is, are what we're seeing here, where the number of tasks that require that resource, only one of them can execute at a time. So basically a unary resource forces that only one of the tasks that require that resource can execute at the same time. So unary is also very common, we have a specialized machine we're using for our tasks, then that's a unary resource. A nurse or a doctor or a worker in a roster is a unary resource. Or the track segment, if we're doing rail scheduling, we can only have one train at a time on that track segment, and that track segment is a unary resource. And for our example, Liu Bei, for his quality assurance, if he's going to overlook each of those tasks, he's a unary resource. Only one of those tasks can happen because he needs to be there for the entire time to look over that the thing is happening with sufficient quality. So we've seen so far in our scheduling concepts the start time and the duration and the end time, we've talked about it. And we seen this var int, which is the start time. Up to now we've used fixed durations, but often there are examples where the duration is also a variable. And then we have precedences, that's the other concept we've seen about scheduling so far. With one task can only start after another finishes. And so we can map that basically to the end time of task 1 is before the start time of task 2. So we're going to add a new concept to our scheduling library which is about unary resources on nonoverlap. So since Liu Bei wants to be in charge of the quality assurance on each of these tasks, then none of those tasks can overlap in time. And so that's what this predicate nonoverlap is going to do. It's going to take the start time and duration of one task, the start time and duration of another task, and force that they don't overlap. So what does that mean? Well, it means either task one 1 ends before task 2 begins, or task 2 ends before task 1 begins and that's to make sure they don't overlap in time. And then if we think of Liu Bei is interested in these four tasks, then we just have to make sure that none of them overlap in time. So basically looking at every pair of tasks and forcing that there's a nonoverlap between those two tasks. And that's going to make sure that Liu Bei is available to oversee the quality on each of those tasks. So if we take our basic scheduling solution here, these are the four tasks that Liu Bei was interested in doing quality assurance on, and obviously they overlap in time at present. If we add that, so this is our basic scheduling solution, if we add the nonoverlap constraint then we can see they get spread out in an order such that only one of them is going on at once, and our duration, our make span has increased. >> Guan Yu, as a combat expert, also wanted to supervise the tasks relevant to soldiers. While Zhang Fei, a warfare expert, chose to supervise the tasks associated with recruitment and acquiring resources. Taking this into account, Zhuge Liang pulled out the magical tablet to figure out a more desirable schedule. >> Well, when Liu Bei talks about doing this quality assurance when Guan Yu says well, hang on, I'm an expert in combat. I should basically do some assurance on any of the combat related tasks. So that is training the soldiers with new weapons and selecting the elite army, also training them in defense, and indeed improving their defenses is also a critical task for combat. And so I want to make sure that all of those are done correctly. And, not to be left out, Zhang Fei says, well, I'm an expert in warfare so I want to be doing quality assurance for recruiting the soldiers, building and finding that bricks and mortar that we need to improve the thing finding the raw materials for the weapons and recruiting the craftsmen. All of these things are critical and my expertise and logistics will help and make sure that those are done well. So we can add these additional constraints by basically associating with each of our heroes some set of tasks that they are interested in. So here's Liu Bei's tasks which we've already seen, this Zhang Fei's task which we talked about, here are Guan Yu's tasks and now we're going to build a new predicate exclusive. Which is going to say given a set of tasks let's make sure that none of them overlap. So it's just basically recording the loop that we did only once with Liu Bei but putting it in a predicate because now we're going to use that predicate for each of these different unary resources. So here's Liu Bei's, all of Liu Bei's tasks have to be exclusive so not overlap in time, all of Zhang Fei's tasks and all of Guan Yu's tasks. So we're building this predicate which just did the same as Lui Bei we did there, it looks in every pair of task to make sure using nonoverlap but they don't overlap in time. Now, there's actually, this is a common combinatorial substructures, so there's a global constraint to do it for us. So nonoverlap considers two tasks at a time but what we're very much interested in normally, like the example in the previous slide, is a disjunctive constraint, which is going to force that a set of tasks don't overlap in time. And the disjunctive constraint takes an array of the start times of the tasks that are involved and an array of the duration of the tasks involved and it's going to force that number to overlap. So you can think of disjunctive as defined in this way, here's the array of start times, here's the array of durations. It's going to be by default implemented like this by basically forcing non-overlapping of those phase of task, so it's just the same as very similar to our exclusive predicate we showed in the previous slide. But of course with the global constraints our solvers can implement this in entirely different way, in a much more efficient way in fact. And there's lots of work on how to make disjunctive constraint solve efficiently in our solvers. So we can replace the nonoverlap with this use of the global disjunctive, and hopefully get a much more efficient solver. So in order to do this, of course, we're going to have to build this array of start times and durations for the jobs on a particular resource, unary resource. So here, for our exclusive, remember we're given a set of tasks. So we're going to build up this array of their start times, looking at those tasks and the durations and then we can call the disjunctive constraints. So here's the array of start times we've built up here, the local variable, and the array of durations and now we can call disjunctive. And we'd expect this model to be much more efficient because this disjunctive will typically be supported specially by the solvers. So now if we solve the model with our three experts doing quality assurance, we'll find it takes 130, so that obviously doesn't change whether we use disjunctive or our own nonoverlap version. But the problem is that the defenses are taking too long, so I'm going to have to come back and see how to fix that in the next picture. Now what we've looked at here is an adaptation of what's called the Job Shop Scheduling Problem, which is a remarkably hard problem for even small instances. So there's some 10x10 instances, so that's basically 100 different task arrayed into 10 rows of 10 tasks each which using different machines. So it had different unary resources and some instances which would defined in 1963. We couldn't break out the optimal solution of until 1989 so this is very, very small problems. Really only 100 things to decide which were very, very difficult to solve. And there's a lot of approximation algorithms with solving job shop scheduling, there's lots and lots of different ways of solving job shop scheduling effectively. And indeed the online version where we just have to schedule a job not knowing exactly what's going to happen in the future is also a very interesting problem that people interest in. And discrete optimization plays a part in all this. So what we've seen in this lecture is disjunctive scheduling. So we're going to add this unary resource, which allows to express that two tasks don't overlap in execution, or in fact that a whole set of tasks don't overlap in execution. And that key thing is we don't specify the relative order, that's part of the solvers role, to work out what order to do the tasks in. If we were specified the relative order, then we'd just need a precedence restraint, which would fit into the basic scheduling problem. So this disjunctive global constraint captures the set of tasks that work on a unary resource so any one of them can be executed once. And there is many classic scheduling problems, some of the most studied problems in scheduling which fit in this category. So job shop scheduling and open shop scheduling are two of the most famous.
