With Xu Su's help, Liu Bei defeated Cao Ren's azure dragon formation. But later, Xu Su had to return to his hometown because of some family issues, and therefore advised Liu Bei to recruit another wise scholar, Zhuge Liang, as his successor. The brothers visited Zhuge Liang's place three times. Their persistence deeply moved Zhuge Liang, and he finally agreed to assist them. Liu Bei gave him the magical tablet in the belief that he could make better use of it. Liu Bei's growing army attracted the attention of Cao Cao, who was planning to wage war against him. Becoming aware of this plan, Zhuge Liang suggested that they strengthen the defense of the city. Three major tasks were involved. Building a wall, producing more weapons, and selecting elite soldiers. Before building the wall, they needed to make bricks and hire craftsman. Money was required to pay for this. Before producing the weapons, they needed to purchase raw materials, and again, recruit craftsman. This also required funding. Soldiers were recruited to join weaponry or defense training, and those that excelled in this were identified as the elite soldiers. This training could only start after the wall was built and the weapon reduction was complete. The dependence between these tasks made the efficient scheduling of them very tricky. In order to figure out the best schedule to complete these tasks as soon as possible, Zhuge Liang pulled out a tablet. >> So Zhuge Liang has finally joined Liu Bei and he's a very wise man looking at the circumstances that Liu Bei finds himself, he has some suggestions. That Liu Bei should strengthen defenses. Improve the walls of his camp and make his soldiers better. So, there are three kinds of tasks in this strengthening of defenses. So, there's some building tasks to make the wall defenses better. There's improving the weapons, so building some better weapons and then training the soldiers further. So lets look at the wall strengthening task. So basically we're going to need to get some raw materials, and hire some craftsmen. And then once both of those have been done, we can actually strengthen the walls. But of course, in reality, first Liu Bei is going to have to go to the money lender to get some money to pay for these raw materials and the craftsmen. And then he can go off and do the rest of the tasks. For the weapons, we're going to have to get raw materials for the weapons. Craftsmen, again, are needed to build the weapons, and then we can build the weapons once we have both of those things. And once more, Liu Bei needs to go to the money lender to get the money to help do these things. Finally, training an elite army. So he is going to need to recruit some new soldiers and then he can train them. So they need to be trained with the new weapons and trained in wall defense. And then, finally, once that's finished pick out some alike soldiers. And notice he can train both for new weapons and the wall defense at the same time. And in reality those are connected to other tasks we've talked about already obviously the weapons have to built before we can try and using those new weapons and the walls have to be improved or repaired before we should train defending the walls. And so if we take that altogether, we get this non-trivial scheduling task where we have ten different tasks to perform. And, basically, there's an arrow from one task to another, we have to finish this task before we can start this task. So there's a precedence relationship there. And overall we have all of these different tasks with their durations. And that gives us a scheduling problem. So we can redraw it this way without the beautiful pictures, where we're using the length to indicate durations. And again, the arcs indicate precedences, basically. You can only do this task here if the two tasks, this one and this one, that have arrows to it are finished before this one starts. And this is a basic scheduling problem. So scheduling is a very important class of discrete optimization problems, and the basic scheduling problem just involves two things. We've got our tasks with durations and we've got precedences between tasks, saying that this task can only happen when all of the tasks it depends on are finished already. And our usual aim is to schedule tasks to minimize the latest end time. That is to minimize the total amount of time it takes to do all the tasks. So in this case, this is important for Liu Bei to have all of his defenses strengthened, before Cao Cao arrives. So, let's talk briefly about modeling time in discrete optimization problems. So time is usually modeled by integers, not continuous variables, even though it'd make obvious sense to model time in terms of continuous variables. But the interesting thing is these tend to be very large integer variables. So you can often look at the start times of a whole lot of tasks which could start on any minute in a seven day schedule. There's a lot of minutes in seven days. But typically we only care about the earliest time that something happens or the latest time that something happens. And so we can actually deal with these very large ranges effectively because we're not going to try every possibility somehow. We're only going to try interesting possibilities in this very large range. So let's look at a basic scheduling model. So we've got an enumerated type giving us all the tasks that we have to perform, and for each task we have a duration. Now we're going to have a number of precedences between the task P and basically this is a two dimension array. Every row in the array is two tasks, and it says that the first task in that row has to finish before the second task begins. Now our decisions are, for every task, we're going to find its start time. Now when we're working that out, we want to have a set of possible times when we can start. And, of course, the smaller this is the better it is going to be. We don't want to use var int if we can at all help it. And so we can think an easy way of working out an upper bound on how much time it's going to take to do all these tasks is just to sum up all the durations. So that's going to give us certainly enough time to do all these tasks with their precedences. because some of them could be done at the same time. And you can see that this may be a very big number compared to the kinds of size of some of the integers we've looked at it, where we're just assigning people to tables or whatever. So here's an example data file which matches the pictures that we've seen before. So here's our set of tasks, and each of them has a duration. And then we've got 14 precedences, which are given in this array. Basically each row is a precedence. So this element here says that the defense training has to be finished before we can do the ELITEARMY task. And the RAW_MATERIALS have to arrive before we can do the casting of the weapons. So, the model only has one constraint, and it's this one. We're looking through all the precedences and requiring that the first task in every row, every precedence, is finished before the second task in that row begins. And so basically here we say here's the first task in the row, presence i 1 And it finishes what? At the start time, if we add it's duration, that's it's end time. And it has to be less than equal to the start time of the second task that occurs in that row, we go over every row. And then our objective is to minimize what's called the makespan, so that's the time in which the whole project is running. And we calculate that by looking at all of the tasks and finding the last end time, and so the end time of task t is just its start time plus its duration, and I want us to minimize the makespan. And if we looked at the data that we gave then the constraints would actually be generated out things like this, so you can see that the funds tasks, if we take it's start time and add ten, that's when it finishes, that has to be finished before we can start the bricks task. And similarly you take the casting task and add 20, which is how long it takes to do the casting, that has to be finished before we can start the weaponry training task. And we can build a basic scheduling solution here and if you check all of the precedences will hold and you can see that we're pushing the tasks up and the total amount of time that makespan is 85. So that's when we finished this task which is the last task finished. We can see the start times for all the tasks. So this kind of scheduling problem is actually a very special kind of discrete optimization problem because it only really has one kind of constraint. So it only has constraints which are called difference logic constraints which take this form, so it's x which is a variable plus d, some fixed value is less than or equal to y which is also a variable. And this allows you to express basically precedences exactly. That's exactly what a precedence constraint looks like. Note that you can also express equality with difference logic by saying that x plus d is less equal to y and y plus minus d is less than or equal to x. That'll force those two tasks to be related, directly. And if you have a problem which is represented by just a conjunction of difference logic constraints, in fact it can be solved very rapidly. We don't need all the machinery of discrete optimization because it ends up being effectively a longest or shortest path style problem and there are specialized algorithms to do that. But once we add extra constraints, and that's what we're going to do later on, this advantage of being able to handle these different logic constraints disappears. So basic scheduling can be solved by these specialized algorithms if we just have tasks with precedences then we have this difference logic constraints and we can use very very effective methods to solve those. But basic scheduling problems are not usually what we want to do, we normally have to add more constraints to our problem. But a basic scheduling problem is one of the most important discrete optimization problems, because it forms the basis of all scheduling problems.
