2.3.2 Disjunctive Scheduling

Loading...

Из курса от партнера The University of Melbourne

Advanced Modeling for Discrete Optimization

51 оценки

The University of Melbourne

Advanced Modeling for Discrete Optimization

51 оценки

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

Из урока

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.

2.3.1 Basic Scheduling10:13

2.3.2 Disjunctive Scheduling10:23

2.3.3 Cumulative Scheduling15:19

2.3.4 Sequence Dependent Scheduling 112:27

2.3.5 Sequence Dependent Scheduling 25:51

2.3.6 Module 3 Summary3:42

Познакомьтесь с преподавателями

Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering
Prof. Peter James Stuckey
Professor
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., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play