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.2 Disjunctive 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
Liu Bei wanted to supervise the tasks being completed to ensure they were
done well.
That was, purchasing the raw materials for weapon production, making bricks for
the wall, weapon casting, and wall building.
Because Liu Bei couldn't supervise all tasks at once,
the completion schedule had to be redesigned.
Zhuge Liang pulled out the tablet.
[NOISE] >> So
Liu Bei is concerned about increasing his defenses and he thinks he
should do some quality assurance on some of the task that are happening.
So he wants to look at the raw materials that are collected for
the weapons and the casting process.
He wants to look over the bricks and mortar that are built and
the defense building up the wall using those bricks and mortar.
So what is happening here is we are adding a new kind of construct to our
scheduling problem, which is a resource.
So in this case Liu Bei is a resource.
So we have two different kinds of resources,
unary resources basically say that at most, one task at a time can happen with
this unary resource, any one of one thing can happen.
We have a another kind of resource which we'll look at later which are called
cumulative resources where we're going to limit the amount of resource that is
available at any time.
So unary resource is, are what we're seeing here, where the number
of tasks that require that resource, only one of them can execute at a time.
So basically a unary resource forces that only one
of the tasks that require that resource can execute at the same time.
So unary is also very common, we have a specialized machine we're using for
our tasks, then that's a unary resource.
A nurse or a doctor or a worker in a roster is a unary resource.
Or the track segment, if we're doing rail scheduling, we can only have one
train at a time on that track segment, and that track segment is a unary resource.
And for our example, Liu Bei, for his quality assurance,
if he's going to overlook each of those tasks, he's a unary resource.
Only one of those tasks can happen because he needs to be there for the entire
time to look over that the thing is happening with sufficient quality.
So we've seen so far in our scheduling concepts the start time and
the duration and the end time, we've talked about it.
And we seen this var int, which is the start time.
Up to now we've used fixed durations, but
often there are examples where the duration is also a variable.
And then we have precedences,
that's the other concept we've seen about scheduling so far.
With one task can only start after another finishes.
And so we can map that basically to the end time of task
1 is before the start time of task 2.
So we're going to add a new concept to our
scheduling library which is about unary resources on nonoverlap.
So since Liu Bei wants to be in charge of the quality assurance on each of these
tasks, then none of those tasks can overlap in time.
And so that's what this predicate nonoverlap is going to do.
It's going to take the start time and duration of one task, the start time and
duration of another task, and force that they don't overlap.
So what does that mean?
Well, it means either task one 1 ends before task 2 begins, or task 2 ends
before task 1 begins and that's to make sure they don't overlap in time.
And then if we think of Liu Bei is interested in these four tasks,
then we just have to make sure that none of them overlap in time.
So basically looking at every pair of tasks and
forcing that there's a nonoverlap between those two tasks.
And that's going to make sure that Liu Bei is available to oversee the quality on
each of those tasks.
So if we take our basic scheduling solution here,
these are the four tasks that Liu Bei was interested in doing quality assurance on,
and obviously they overlap in time at present.
If we add that, so this is our basic scheduling solution, if we add
the nonoverlap constraint then we can see they get spread out in an order such that
only one of them is going on at once, and our duration, our make span has increased.
>> Guan Yu, as a combat expert,
also wanted to supervise the tasks relevant to soldiers.
While Zhang Fei, a warfare expert,
chose to supervise the tasks associated with recruitment and acquiring resources.
Taking this into account,
Zhuge Liang pulled out the magical tablet to figure out a more desirable schedule.
>> Well, when Liu Bei talks about doing this quality assurance when Guan Yu says
well, hang on, I'm an expert in combat.
I should basically do some assurance on any of the combat related tasks.
So that is training the soldiers with new weapons and
selecting the elite army, also training them in defense, and
indeed improving their defenses is also a critical task for combat.
And so I want to make sure that all of those are done correctly.
And, not to be left out, Zhang Fei says, well, I'm an expert in warfare so
I want to be doing quality assurance for recruiting the soldiers,
building and finding that bricks and mortar that we need to improve the thing
finding the raw materials for the weapons and recruiting the craftsmen.
All of these things are critical and my expertise and
logistics will help and make sure that those are done well.
So we can add these additional constraints by basically associating with
each of our heroes some set of tasks that they are interested in.
So here's Liu Bei's tasks which we've already seen, this Zhang Fei's task which
we talked about, here are Guan Yu's tasks and
now we're going to build a new predicate exclusive.
Which is going to say given a set of tasks let's make sure that none of them overlap.
So it's just basically recording the loop that we did only once with Liu Bei but
putting it in a predicate because now we're going to use that predicate for
each of these different unary resources.
So here's Liu Bei's, all of Liu Bei's tasks have to be exclusive so
not overlap in time, all of Zhang Fei's tasks and all of Guan Yu's tasks.
So we're building this predicate which just did the same as Lui Bei we did there,
it looks in every pair of task to make sure using nonoverlap but
they don't overlap in time.
Now, there's actually, this is a common combinatorial substructures, so
there's a global constraint to do it for us.
So nonoverlap considers two tasks at a time but what we're very much
interested in normally, like the example in the previous slide, is a disjunctive
constraint, which is going to force that a set of tasks don't overlap in time.
And the disjunctive constraint takes an array of the start times of the tasks that
are involved and an array of the duration of the tasks involved and
it's going to force that number to overlap.
So you can think of disjunctive as defined in this way,
here's the array of start times, here's the array of durations.
It's going to be by default implemented like this by basically forcing
non-overlapping of those phase of task, so it's just the same as very similar
to our exclusive predicate we showed in the previous slide.
But of course with the global constraints our solvers can implement this in entirely
different way, in a much more efficient way in fact.
And there's lots of work on how to make disjunctive constraint solve efficiently
in our solvers.
So we can replace the nonoverlap with this use of the global disjunctive, and
hopefully get a much more efficient solver.
So in order to do this, of course, we're going to have to build this array of start
times and durations for the jobs on a particular resource, unary resource.
So here, for our exclusive, remember we're given a set of tasks.
So we're going to build up this array of their start times, looking at those tasks
and the durations and then we can call the disjunctive constraints.
So here's the array of start times we've built up here, the local variable, and
the array of durations and now we can call disjunctive.
And we'd expect this model to be much more efficient because this disjunctive
will typically be supported specially by the solvers.
So now if we solve the model with our three experts doing quality assurance,
we'll find it takes 130, so that obviously doesn't change whether we use disjunctive
or our own nonoverlap version.
But the problem is that the defenses are taking too long, so
I'm going to have to come back and see how to fix that in the next picture.
Now what we've looked at here is an adaptation of what's
called the Job Shop Scheduling Problem, which is a remarkably hard problem for
even small instances.
So there's some 10x10 instances, so that's basically 100 different task
arrayed into 10 rows of 10 tasks each which using different machines.
So it had different unary resources and
some instances which would defined in 1963.
We couldn't break out the optimal solution of until 1989 so this is very,
very small problems.
Really only 100 things to decide which were very, very difficult to solve.
And there's a lot of approximation algorithms with solving job shop
scheduling, there's lots and
lots of different ways of solving job shop scheduling effectively.
And indeed the online version where we just have
to schedule a job not knowing exactly what's going to happen in the future
is also a very interesting problem that people interest in.
And discrete optimization plays a part in all this.
So what we've seen in this lecture is disjunctive scheduling.
So we're going to add this unary resource,
which allows to express that two tasks don't overlap in execution,
or in fact that a whole set of tasks don't overlap in execution.
And that key thing is we don't specify the relative order,
that's part of the solvers role, to work out what order to do the tasks in.
If we were specified the relative order, then we'd just need a precedence
restraint, which would fit into the basic scheduling problem.
So this disjunctive global constraint captures the set of tasks
that work on a unary resource so any one of them can be executed once.
And there is many classic scheduling problems,
some of the most studied problems in scheduling which fit in this category.
So job shop scheduling and open shop scheduling are two of the most famous.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
