Optimization is a common form of decision making, and is ubiquitous in our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions in manpower and material resources management also allow corporations to improve profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, all of these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Basic Modelling for Discrete Optimization. In this course you will learn much more about solving challenging discrete optimization problems by stating the problem in a state-of-the-art high level modeling language, and letting library constraint solving software do the rest. This course will focus on debugging and improving models, encapsulating parts of models in predicates, and tackling advanced scheduling and packing problems. As you master this advanced technology, you will be able to tackle problems that were inconceivable to solve previously. Watch the course promotional video here: https://www.youtube.com/watch?v=hc3cBvtrem0&t=8s
2.3.3 Cumulative Scheduling
Loading...
From the course by The University of Melbourne
Advanced Modeling for Discrete Optimization
45 оценки
From the lesson
Scheduling
Learn how to tackle complex project scheduling problems of various forms, progressively from ones with only basic precedence requirements to ones with unary resources and even cumulative resources. You will see how to model some of the complex constraints that arise in these applications.
Meet the Instructors
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
