0:11

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.

Â 0:45

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.

Â 1:09

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.

Â 1:37

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.

Â 1:55

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.

Â 2:42

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.

Â 3:26

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.

Â 3:57

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.

Â 4:19

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.

Â 5:05

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.

Â 6:00

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.

Â 6:48

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?

Â 7:06

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.

Â 8:55

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.

Â 10:05

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?

Â 11:14

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?

Â 11:54

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.

Â 12:33

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.

Â 13:08

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.

Â