Welcome to workshop nine, this is the first workshop
of the course on solving algorithms. >> Okay,
workshop nine is about preparing medicinal herbs.
We saw in chapter four how Shennong was able to resolve the curse issue in the village.
And then no more new kids, they would be become ill again.
But then there are already a whole bunch of boys and girls that are already sick.
So Shennong will have to prepare some herbs to heal these children.
There are different kinds of herbs including ginseng, poria, angelica and
so on.
And then there are different steps for preparing these herbs as well.
Steps including cutting, soaking, brushing, bleaching, and so on.
There are different steps for preparing different herbs, and
the ordering could be important.
For example for preparing ginseng, it could be cut only after it is bleached.
And then also the different steps they might have to utilize, certain tools.
We would have a pottery knife, we would have iron knife,
and the gold knife as well.
But then some of these steps they require the same tools
and in that case, those task which are sharing the same tool,
they cannot overlap. >> Yep.
>> So what's the objective,
what is the goal of Shennong? >> Of course,
Shennong wants to get it all over and done with as quickly as possible,
right? >> Sure, certainly.
>> We want to get all the tasks finished,
which is a usual objective we have when we are doing scheduling kinds of
problems. >> So
should we look at the MiniZinc model? >> Yep,
let's have a look at the MiniZinc model.
So if we open the project file attached to this workshop,
you should pop up a window like this.
And we can look through our MiniZinc model.
So here's the data, of course.
We've got n as the number of tasks, and for each task, a duration.
We've got m which is the number of precedences.
And there's already two arrays here, the pre and the post array.
And we're basically requiring that the pre task finishes before the post
task starts. >> So that's the standard way of
specifying precendences. >> Exactly, we've seen that in plenty of
other examples in this course. >> And
then we've got a number of disjunctions.
So we've got O disjunctions and each of these disjunctions is a set of tasks and
none of those tasks can overlap. >> So we have an array there,
and each array element is a set. >> That's right.
>> A set of tasks.
And all the elements of this set they cannot overlap
with each other.
>> Exactly. >> Right.
>> All right, and so then the principal
decisions are these usually in scheduling problem is, when do we start this task?
Alright, so there's the start time.
But we've also got another version of those decisions here.
The end time, right?
So this is the start time plus the duration, all right?
And obviously these are tightly tied,
if I fix all the start times, I'm obviously going to fix the end times,
because the durations are known.
But if we could also fix the end times, and then we'll fix all the start times,
right? >> So that means we only have to decide on
one set of these decision variables. >> Exactly, alright, so
let's look at our model of the problem.
So here's our precedence constraint, that's pretty straightforward.
We're just saying the end time of the pre-task is less than or
equal to the start time of the post-task.
That clearly means that the first task finishes before the second task begins.
Then we're going to do something interesting,
we're going to introduce some new decision variables, b.
Okay, and this is between pairs of tasks.
This is going to keep track of the relative ordering of pairs of tasks.
But now we only care about pairs of tasks which are in disjunction, alright.
We only care about the relative ordering, so which one's before which one.
In the case that they can't
be at the same time. >> Okay.
>> Alright, so the first part of
this here is basically setting all of the Bs that we don't care about to 0,
because we're never going to worry about them.
Alright, so we don't care about a B, if we have two tasks T1 and T2.
If T1 is greater than or equal to T2, we don't care about it
because we'll always think of the task pair IJ in the order I less than J, right?
So if not the other way, not J, I. >> Okay, so
the reason why we need to have this constraint is because we are defining
a big two dimensional array of Bs, and for every pair of tasks.
But then if the two task,
they are not within a disjunctive relationship then we don't care.
So we would like to set those B's to be 0. >> Yeah, and also for every pair, right,
we have two variables.
So we also want to get rid of half of them.
So this gets rid of the half we don't care about.
And this other test here is, if there's no disjunction where these two tasks appear.
So they can overlap with each other in any way,
then we're just going to set this boolean to 0, since we don't care about it.
Alright, so the real purpose of these booleans is for this constraint here.
So we're looking through every one of our disjunctive sets.
We're taking any two tasks from that disjunctive set where T1 is less than T2,
because we always look in that order
and we say this boolean, t1,
t2 is true means that task1 finishes before task2 begins, right?
And since they're in disjunction,
if that's not the case, then it has to be the other way around.
And so if it's false, it means that task 2 finishes before task 1 begins.
>> Okay, so
in some sense this boolean variable is used to indicate whether a task
should finish before the other one. >> Exactly,
the tasks that we care about. >> Right, sure.
>> So the ones in disjunction.
Alright, finally we're looking at the makespan which is just the maximum end
time. >> Yeah.
>> Right, and then we're going to minimize
that makespan, right? >> I can see that you have already
prepared. >> Okay, so we've prepared because we're
going to have to, well, we've got three choices for variables to put here, right?
We can take start times, or end times, or
the boolean variables. >> Wow.
>> And we have four choices to put for
var selection.
And let's say four choices to put for
value selection. >> So input order is?
>> Input order is just, we try them
in the order they appear in, right? >> Right, and
first-fail is to select the variable with the smallest domain, so that if you-
>> At the current time.
>> Yeah, at the current time.
>> Yeah, and smallest, remember, looks for
the variable which has the smallest current value left over
in its current domain. >> And
largest is just the opposite.
>> Exactly. >> Right.
>> Then indomain_min is setting it to
its minimum value, its maximum value, the median is in the middle.
It's not likely to be very useful for scheduling.
And random, which just seems like a totally bad idea, but
it's often not as bad as you think. >> Right.
>> Alright,
so let's just start off with a very straightforward input order.
We're just going to fix the variables in order indomain_min.
Sort of almost a default kind of search strategy,
if you don't think about anything at all.
Let's start with our simplest example here, and run our model, all right?
So notice one thing, we've got the statistics coming out here,
we've gone into our configuration.
We've actually turned on statistics for solving, and
also, because later on we'll run some examples which take a while.
We've added the silver flags and we've got a time limit of 6,000 milliseconds, or
6 seconds.
Just so that we don't spend a lot of time staring
at the screen. >> Yeah, really depends on how much time
you have for your experiment. >> Exactly, exactly.
All right, so we can see that we found a solution fairly quickly.
12 failures, so indomain_min
is a sort of obvious thing right? >> Yeah.
>> Because we're tring to minimise,
what if we do indomain_max? >> Yeah.
>> Let's have a try and see what happens.
Alright, so I don't know if you saw it flash past,
but we found a lot more solutions on our way to the optimal.
And if you look at the phase, let's say 39 verses the previous one was 12.
>> A lot larger.
>> Exactly, so
really indomain_min was much better than that, right?
What about if we try >> Yeah.
>> if we try indomain_median, so
we're going to set it to a middle value.
Alright,
so if you can see we've got a few answers, >> Mm-hm.
>> 48 failures, which is sort of worse,
in fact, right?
So really setting it to the middle of your range in a scheduling problem is pretty
bad, right?
Because you're not going to learn very much from that.
>> Let's try random as well.
>> Let's try random.
Of course with random we could be super lucky.
So 23 is actually not too bad, it was better than medium
and better than max which was possibly the opposite,
and not as good as min. >> Min is still the best.
>> Yeah, well,
because we're trying to minimise makespan. >> Exactly,
yep. >> Exactly, all right,
what happens here, we'll go back to min.