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.4 Sequence Dependent Scheduling 1
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
The excellent defensive strategy designed by Zhuge Liang
greatly reduced the threat posed by Cao Cao's army.
Cao Cao was angry about this failure, and
he declared a war against Liu Biao, the ruler of the Jing Province.
Unfortunately, Liu Biao died soon after and
his successor, Liu Cong, surrendered to Cao Cao.
Cao Cao and his army gradually overtook the surrounding cities and
armies in the Jing Province.
In face of Cao Cao's strengthening control,
the three brothers were forced to leave Jiangan.
To save their army however, Zhuge Liang suggested they
form an alliance with Sun Quan, the ruler of the state of Eastern Wu.
Zhuge Liang went to Wu and successfully persuaded Sun Quan to join them.
The brothers and their army moved to Eastern Wu soon thereafter, and
began to repair their defense in case of an attack.
In preparing their defense, Sun Quan highlighted the importance of two
critical cities in Wu that were currently inbalanced in terms of weapons and armor.
One city had more weapons than needed but less armor,
while the other city had fewer weapons and more armor.
Fortunately, Sun Quan was aware that there was a shipping channel
between the two cities that they could use to exchange the weapons and the armor.
The channel was so narrow that no two ships travelling in
opposite directions could pass through at one time.
Ships that were travelling in the same direction, however, could travel through
together, provided that there was enough distance kept between their sails.
Every ship had to leave at a particular time which was determined by how long it
took to load.
Sun Quan hoped to come up with a schedule to ship the weapons and
armor as quickly as possible.
As an ally, Zhuge Liang decided to solve this scheduling problem for him,
using the tablet.
>> So Sun Quan has a problem.
He has one city with a surplus of armor, and
another city with a surplus of weapons.
So what he wants to do is put all this armor in ships and
send it to the other city, and put all the weapons in these ships here, the surplus,
and send it to this city.
And then both cities' defense will be improved.
But there's only a very narrow channel, 32 kilometers channel,
between the two cities.
So one ship can be going from this city to the other.
That's fine.
Or we can have one ship going this way along the channel.
That's fine.
But if we try to send two ships in opposite directions along the channel,
then they can't pass and that's not going to be allowable.
There's also a safety distance between the ships.
So because it's a narrow channel,
we want to make sure that they don't get entangled with each other.
So we have to keep them 2 kilometers apart as they go along this channel,
if they're going in the same direction.
Obviously, we can have multiple ships going in the same direction
without any problem.
Now these ships have to be loaded with the excess goods.
And so there's some start time.
So we can't actually have a ship leave before it's loaded.
So there's some earliest start time when it could start.
And what we're trying to do is optimize the time, the makespan from moving all
the ships from this city to this city, and all the ships from this city to this city.
So that's the time that we're trying to optimize.
So we can think about this more pictorially.
We have a number of ships going from A to B, let's call them L, and
a number of ships going from B to A, let's call them E, along this single channel.
And this single channel problem is specified here.
Each ship has a specific speed and can't leave any earlier than its desired time,
that's when it is loaded.
The channel in this case is 32km long.
And we have to be careful.
A ship can only enter the channel if it's clear, so
if there's no ship sailing in the opposite direction in that channel.
And if two ships are in the channel going the same direction obviously,
then they can be no closer than 2 kilometers.
And we're trying to minimize the time to move all the ships.
So let's think about this channel.
So the channel is a complex unary resource.
So we can sort to graph this thing.
Here's Port A, here's Port B, here's the length of the channel.
So where is every ship in the channel?
So here we've got first ship heading out.
And we need to keep a leeway.
So this leeway is this distance here of 2 kilometers.
And then we can have this second ship, once the first ship reaches 2 kilometers,
this second ship can head out.
And here you can see because the ships are going the same speed,
they're going to keep that 2 kilometer distance.
But we have to consider other cases.
So if the first ship goes faster, and
the second ship leaves after it's 2 kilometers out, then there's no problem.
It's not going to catch up, because it's a slower ship, so
that will keep the leeway constraint.
But the other case when the first ship here is slower than the second ship,
then it can't leave as soon as this ship has gone 2 kilometers out,
because it will catch up.
So it has to leave later in order that there's still 2 kilometers left
at the end.
So what we have here is an example of a sequence dependent unary resource.
And so this sequence dependent between tasks is very common for unary resources.
So basically,
the schedule depends on which task precedes another on that resource.
So example of this is are in smelting.
So we if have some machinery that doing some task on metal,
then it might have to cool down to perform a cold task after there was a hot task.
We can have any number hot tasks directly after each other, or
any number of cold tasks directly after each other.
Similarly, embroidery.
If we're using embroidery of some t-shirts or
whatever, if the colors of the thread currently on the machine
are enough to do the next embroidery task, there's no slow down.
We can do this task straight away.
Otherwise, there's a break where we have to have someone come in and
change the colors of the threads that are on the machine.
And the problem we're looking at here is the single channel problem.
So ships traveling in different directions need to wait until the channel is cleared.
But if they're traveling in the same direction then they can basically go
as close together as is possible.
So effectively the start time of the next task is delayed
depending on what the previous task was.
So let's think about our single channel problem.
So we have a number of ships, and each of them has a speed and
a desired time to leave.
And we're going to give it basically a direction of the ships.
They can go from atob or btoa.
So that's the direction array.
And we have some leeway between the two ships and
a maximum time, the times that we're going to allow, we're going to think about.
So, when we're modeling activity sequences, so
sequences of activities where the durations in between depend on this
sequence, then in order to make decisions about the next activity,
in this case a ship, we need to know what the current activity is.
So the way we're going to do that is model, for each ship,
exactly what is the next ship that is going to go.
And that's going to allow us, when we're looking at ship one, to work out what
the next ship is, and then make decisions about ship six relative to ship one.
We could also use a previous array, which would work similarly.
So each of the ships is going to have a next ship in the sequence.
So there's a problem with that is there somehow has to be a last ship here and
that doesn't have a next ship.
So, how are we going to overcome that?
We're going to introduce a dummy ship at the end.
So we're going to add an extra ship into our problem,
which really isn't a real ship.
And it can be the next ship for the last ship and it won't have a next, all right?
So, let's look at our single channel problem.
So here we're extending our ship type with an extra ship, and that's the dummy ship.
And we're introducing a new type of ship, the dummy ship, and
we're basically extending this direction array to be this kind.
So for all the normal ships,
the kind of the ship is just the same as the direction.
But for the dummy ship now, our extra ship, its kind is dummy number three.
And we're going to extend our speed array to include a speed array for
the next ship.
So here the dummy ship has just a speed 0.
We're going to have start times and end times for
this extended set of ships, so not just the original ones, start times and
end times including for the dummy ship.
And then importantly, only for the original ships,
we're going to have a next ship, which could be one of these extended ships.
So it's allowed to be the dummy ship.
All right, now, we're going to just make the start and end time for
the dummy ship the end of all time.
So it's meant to be far away and not going to influence our problem.
And then, we have a relationship between the start and
end time of all ships, all the, not the extended ships but all the ships.
So the start time, then we take the length of the channel, and then the speed which
we're using an inverse here, the speed is really the inverse of the speed.
And that's going to give us the end time.
And the key constraint which is going to make sure that this
next is correct is going to be that these are all different.
So that's one thing, so we're always going to have an all.
The next ship is going to be different.
We know that's the case.
And now we have to reason about the channel.
So, once we know the next ship,
it's reasonably simple to reason about the channel.
So if the next ship is in the opposite direction,
it can only start once this current ship finishes.
If the next ship is in the same direction, it can start after we have
traveled 2,000 meters, so that would give the leeway at the beginning.
But that's not enough because if the next ship is faster than the current ship,
then it could catch up.
So it has to be at least 2000 meters apart when it reaches the destination.
So we can code that fairly straightforwardly.
So we look at every ship.
And we look at its kind and the kind of the next ship.
If they add up to three, we're in opposite directions.
So this is kind one and this is kind two, or this is kind two and this is kind one.
And obviously the dummy ship will never have this,
because we'll always add up to more than three.
So this is just a shorthand for
checking that the two ships are in the opposite direction.
And if that's the case the start time of the next ship has to be greater than or
equal to the end time of the current ship.
All right, so that's the case of opposite direction ships.
What if the next ship is in the same direction?
Then we know that if we take the start time of the current ship and
we add the time it takes to move along the leeway,
then that has to be, that's the earliest time we could start the next ship.
But that's not enough.
We also have to look at the end times.
And if we take the time that the current ship finishes, and then we add
the amount of distance that the next ship can move, the time it takes for the next
ship to move along the leeway, that's the earliest end time for the next ship.
All right, so that will allow constraints to make the two ships
always stay at least 2 kilometers apart.
We've got other constraints.
The start time has to be greater than or
equal to the desired time because if they're not loaded, we can't run.
And finally the objective is just minimizing the maximum
of all the end times of all the ships, not the end ship,
obviously, which was at the end of all time anyway.
Now we have to be careful about this model, that this alldifferent constraint
is going to force that the next of all the ships is different.
But if we look at this example, here the next of all of these ships are different.
So 3 has a next of 1, one has a next of 6, 6 has a next of 4, and 4 has a next of 3.
And this would allow us to say that the next ship of 3 is 1.
Is that going to be allowed?
Well, by the alldifferent, yes.
But luckily, we have these constraints also that the ship and
the next ship and their start times.
And we know that the start time of the next ship is always greater than the start
time of the previous ship.
So if we look at the current ship 3, its next ship is 1.
But the start time of ship 1 is before the start time of ship 3, so
this won't be possible.
So we will have to have some picture more like this, where all the ships
point forward, until someone finally gets the dummy ship as the next ship.
But there are problems where this kind of constraints halt and
then we need a different global constraint.
The circuit global constraint will allow us to do things like this.
So if we solve the model, we find all the start and end times and we can see
the total amount of time required is 513, which is the largest of the end times.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
