Supervising the tasks made the task completion schedule much longer but it was an important undertaking for quality assurance. To make the supervision less time consuming, Zhuge Liang proposed to involve more supervisors. These supervisors could only supervise one of the three types of tasks related to production, soldier training, and warfare. Zhuge Liang pulled out the tablet to help create the schedule. [SOUND] >> So Zhuge Liang has decided that with just the three heroes doing quality control, the whole process of strengthening the defenses are going to take too long. So we're to need more resources to help do that quality control. So for the raw materials, he suggests we have four experts to do quality control. And some of these tasks need quite a bit of quality control. So, we're going to need, so for example the raw materials for the weapons is going to need three experts to look over it. The raw materials for the wall just one expert. The building of the weapons is going to need two experts looking over it and the building of the wall, two experts looking over it. But we have other kinds of tasks where we need the expert in combat expertise quality control. And so for there for hiring for training the solder with a new weapon we're going to two experts of this quality control. For training among them on the walls we again need two. For picking the elite soldiers we're just going to need one. And for strength and defenses, which is also important for the combat perspective, we need two of these quality control experts. And then we have experts in warfare, and they're going to need to be doing quality control for hiring new soldiers. For selecting the raw materials for weapons and raw materials for the walls and indeed for selecting the craftsman. So overall what we've got here is called the resource constrained project scheduling problem, RCPSP. So we're given some tasks, now ten tasks that we have to do to strengthen the fences. We've got precedences between the tasks, just like every other scaling problem we've looked at. And now, we've got resources, as well as in disjunctive scheduling, there were unary resources, now, they're not unary. In each task, we'll need some amount of resources for that particular type. So task t needs res[ r, t] for resource r during it's execution. And we have a limit L[r] for each resource so we can never use more than that amount of the resource at any time. And our aim is to find the shortest schedule to run every task and this is one of the most studied scheduling problems there are. All right, so here's our picture, here's our ten different tasks and we see with the number of figurines that are attached which of the resources are required for this task, and how much. And here's our resources down the bottom. We have four resources of each of the three different kinds of quality control that we need to do. So, let's look at that model, so the start of the model is just the same scheduling model we've seen before, and here is the new thing, right. We're introducing a enumerated type for resources and for each resource we have this limit on how many of the resources are available during our building of the defenses. And we have this for each for each resource and each task, how much of that task and how much resource does that task need. And the data file, well nothing's changed here, the tasks are the same, the precedences the same, the duration's the same. What we have to look at is the next part where we've got here's our resource enumerated types, so we've got three different kinds of quality control quality, military, and combat. The number of resources available for each of these, so we've got four experts in each of these quality control areas. And then for each task how much of each resource is required during its execution. So before we looked at unary resources which are unique but often resources we can have multiple identical copies and that's how we get this cumulative kind of resource. So we might have multiple bulldozers working on our building site or workers which we'll treat of equal capability, because I can do the same tasks. Well perhaps we have multiple operating theaters, you know hospital which are interchangeable or airline gates. And when we model one of these resources with multiple copies then we are going to assume some task t has this resources use t here, we're going to fix the one just particular resource for a while. And we'll assume a limit L on that particular resource at all times. So let's think about visualizing that. So we can think of a task now, for this particular resource as a box. So it has a length, is it's duration, that's the duration of the task. Where it starts is the starting time, so here's time going on here. And this is resource usage going up and down here, and the height is the number of resources it needs. So here we got an example of three different tasks with different starting times and resource usages and durations so we can think of them like boxes. Now how do we make sure that we never use too much of resource at one time but basically what we can do is thing about at every time let's make sure that we don't go over the limits so that's a very straight forward model. So we're looking at all time points and we're summing up all the tasks that are actually running at that time, summing up their resources and making sure that's less or equal to L. And then this expression here in red is checking that task t runs at time i. So you can think it this way, the start time of t has to be less less than or equal to i, that means that the task has started at i or before. And the end time of t which is this start + duration has to be greater than i. So, if that's the case, then the task t is really running at time i and so it needs resources. And notice, we don't consider it to be running at the very end, right. If we take the actual end time, that's where it gives back the resources. Once we've done that, we can look at a resource profile like this example here and we can check that at every time point, we don't go over this resource limit. So if we look at time 0, there's only one task running that's task 4 so the resource used are just 3. At time 1, 4 and 2 are both running, and so the resource usage is 4, still under the limit. Similarly at time 2, it's still 4. At time 3, now 4 has stopped working, but 1 and 3 have started, so it's again 4. At time 4, it's 3, just 1 and 3 are running at this time. At 5 five it's 2, just 1 is running. At time 6 and time 7, it's 2. So this is a schedule that as we're showing graphically meets our resource limits. So the problem with this idea is the size of the number of constraints here, of the size of these constraint is quite large. So we've got basically an expression for each tasks and for each time period, and in many scheduling problems the number of time periods can be very, very large. So how can we do better than that? Well, if we think about it a bit more, there can only really be an overload of the results at the start time of some task. because at the start time we're adding the necessity to have more resources available. So we really don't have to check every time, we only have to check the start times. So an alternate model which only checks the start times instead does this, we look forall task, we're going to sum up the task that are running at its start time. So, this expression here in green says that task t is running at the start time of task t2, right? So just as we did before, but we're looking at only the start time on task t2. And now, if we think about this constraint, we're going to check time 0, because that's the start time for task 4, and the constraint holds. We're going to check time 1, because that's the start time for task 2, and again the result holds. And we're going to check time 3, because that's the start for tasks 1 and 3 and again, the resource limit hold. And we don't need to check any other times, because we know that's the only time we could possibly get an overload, is when a task starts. So, we can write this more explicitly. This way saying for every teacher in task we don't need to sum up task t2. We know that task t2 is running at the start of task t2. So we can take an add of this sum and just add up the resources for task t2. They'll certainly be in we don't have to check this expression here which is checking whether t2 is running at the start of times t2. And this is more explicit formulation will be stronger because sometimes a solve would not be able to look at this if this is t2 here and necessarily work out that it holds or as in this case we've shown that it must hold. So if we compare it with the original time decomposition we've certainly got an advantage it's much smaller in time than the time decomposition because it's only basically the number of tasks squared. But there is a problem as not so much information is going to the solver because here the solver has to reason about the relative start time of tasks. And that is more difficult than just talking about the actual start time of a single task. So there is another way we can do it, of course as we have seen many times in this course when we got a complex repeating sort of idea we should do with a global constraint to do that. And that's what the accumulative global constraint does, it exactly captures a resource constraint. So the cumulative constraint takes an array of start times for all the tasks involved. An array of durations and an array of resource usages and then the limit is the last argument. And basically what it's going to do is exactly what we've seen in these decompositions in the previous slides. It's going to ensure that no more than this limit of the resources used at any time during the execution of these tasks. So there's the kind of MiniZinc type signature for cumulative. Now we should think about cumulative, does this constraint hold right? We've got task the start times are 0, 1 and 4 from 3 different task. The durations are 3, 4, and 2 different task. And the resource usage at 1, 2, and 2 different tasks and the total limit is 3. So if you look at this picture, well it doesn't look like it holds but of course this picture, we're not doing box packing, we'll come to packing later. We've just to think about how much resources it uses every time. So if we push all of those tasks down, we can see the minimum amount of resources we need. And you can see you get this kind of jagged shape. But it's very clear that at time 4, we have too much going on, all right? So these tasks are not really boxes. So an important concept in cumulative scheduling is this notion of a timetable, which is this graph here, which is how much of the resource are we using at every time? And of course, the timetable here shows that the time at time 4, the resource is too high. So just to give you some more thoughts about cumulative. Does this cumulative constraint called hold here? So we have four tasks of this start time and this duration and these resource usages and a resource limit of 4. And another question is let's say we're now taking this example up here. We've got the same durations and the same resource issues but we've made it more flexible what the start times are. So a start time of task 1 could be between 0 and 3, similarly for task 2 etc. So now is it possible to make that cumulative constraint hold, where we've made things more free? So let's look at the answer. So it's very easy to draw this kind of graph of these 4 different tasks, and we'll see it's similar to one we've seen before. So basically at time 3 we had this overload, because 1 and 3 and 2 are all running and that needs 5 resources, so, there is no solution to that. Now, if we freed up the start times, could we make it all fit? Yes because we freed up the start form for 2, we can push it back early at the time 0. And now, it really fits under the resource limit. So, let's try to give you some idea about how you think about these cumulative constraints. All right, let's go back to our model. We're going to add these resource constraints in, using the cumulative global. Basically, for every resource we're going to have this cumulative constraint using the start times of the tasks, and the durations of the tasks, which are the same in every cumulative constraint. And then of course, the resources used for the tasks for this particular cumulative constraint for resource r are just those for that resource for each of the tasks. And the limit is this limit for that resource r. That's what we have to do to add to our model and we've now got a cumulative resource version of our scheduling model. And here is the solution, so now we've shown all the tasks here color coded for which resources they're using and we can sort of check at the start time of every task how much of each resource is being used. So here we're using 4 of the green resource we're using 2 here and 2 here. And if we come back here we're also using 4 we're using 2 here and 2 here and none here etc. And you can see that at each point at each start time of a task these resource constraints are satisfied and there is the entire solution. So you can get it all done in 90 days once we have these more quality control people. So in summary what we are seeing here is the cumulative constraint and in fact, there is lots of ways of actually doing inference in the cumulative constraint. And we will see those in more detail later on in another separate part of this course, but timetable propagation is basically the basic approach. And it's really equivalent to the time decomposition in terms of what is understands, but it's faster than a task decomposition. And then there's many other ways to reason about cumulative, reason about time intervals rather than single times and combinations of energy based reasoning or edge finding and timetable reasoning. So these renewable capacitated resources are the resources we talked about here, so we've got the same number over the entire schedule. That's one particular kind of resource, there are other kinds of resources, which aren't renewable. And we've seen the time decomposition here, which is simply checking those resources each time. The task decomposition which is a bit clever but actually sometimes doesn't work as well is to check the resources just when every task starts. And then the cumulative sorts to give you the best of both worlds. It gives you the same amount of propagation or inference as this time decomposition but it's no bigger than the task decomposition. And what we see in here is actually what's the RCPSP problem or resource constraints project scheduling problem and that's a very core scheduling problem in the world of scheduling.
