>> The schedule provided by the tablet took too long. Sun Quan's commander in chief, Zhou Yu reported that he had foreseen the need for another shipping channel. He had already arranged in secret for the establishment of a new channel connecting the two critical cities. Now aware of this new channel, Zhuge Liang pulled out the tablet hoping to determine a quicker schedule. >> So, Sun Quan is very disappointed with the results of working on how he can move his ships. 513 hours, almost 22 days is too long. So, he's very disappointed. He's very surprised, though when his advisor, Zhou Yu says, well, actually, I foresaw this problem because I'm so brilliant and I actually dug another channel between the two cities. So now, we can move the ships down two channels at once and that will make it much more efficient. So now, we got a double channel problem. We got two different channels between the two ports and we can send the ships down either channel. So, what has changed? We've now got two channels, one and two and we need to choose for each ship not only when does it start, but also which channel does it use and our constraints are just the same as before. We've got speeds and earliest leaving time. We've got two channels to choose from of different lengths and the constraints on each channel are the same. We have to enter the channel only if it's clear of another ship in the opposite direction and we've got a minimum leeway between the ships. We're going to try to minimize the time to move all the ships. So, let's look at that model and see how we'd adjust it to take into account multiple channels. So we're not just doing double channels here, we could do with more. And so we've got a number of channels here and for each of them, we've got a length. So rather than just having a single length, it was before. The rest of the model data is completely the same. Let's look at the decisions. So rather than adding a single dummy ship, now were going to add a dummy ship for each channel. Because for each channel, we're going to need to have a last ship. So each ship will have a next ship in the same channel and for each channel, we're going to have a dummy last ship. So basically, our extended ship is now got not just one extra, but one for each channel and our extended kinds is just adding a dummy ship kind for each of those extra dummy ships and extension of the speed is the same as before, all the dummy ships get speed zero. And a crucial thing, addition to our model is for each extended set of ships, we've got which channel does it go down between one and the number of channels. And next is unchanged, basically, which is the next ship in the same channel. Now, we need to make sure that our dummy ships are at the end of all time. So their start and end times are the same and we basically insure that each dummy ship is in a separate channel. So the channel of dummy ship s is s-nS and since the dummy ships start at nS plus 1 and then go up to nS plus nC. That's going to force the channel for each of the dummy ships to be different. We have change the relationship between start and end times for all the ships. Basically, we now have to use the length of the channel that they are actually going down to determine the start and the end times for different ships. The alldifferent stays the same. We'll still have next will all be different, because your next can't be the same even if you're on different channels. There's only a single ship in front of you or after you, including these dummy ships, of course. Now, we've got more dummy ships. The relationship between the ship and the next ship completely the same. All of this about the times stays exactly the same, because we're just running two channels and the relationship between you and the next ship doesn't really depend on the channel itself and there's one extra thing we need to make sure. That is the current ship uses channel s and it's next ship is in the same channel. So, the channel next ship is the same. So that's a key different a way making sure that the next ship is on the same channel, as each the ship is next of. The leave before desired time is just same, as before and the objective is the same as before. So now we can run the model and we can solve, and it only takes 293 hours. So, we've reduced from 22 days to slightly over 12 days. So, this is a great success. So what we've seen here is the example of order dependent setup times and costs, and the way to do this is you model this next task explicitly, and then we're going to add constraints to ensure that the setup time or the cost between these order dependent tasks is paid. So in our example, it was this direction change in the channel which forced us to pay more time or wait until that channel was completely clear and it's similar to a mode change in the machine shop scheduling problem like changing threads in a thread scheduling or cool down time for some smelting jobs that require different temperatures. So, this order dependent setup time is a very frequent thing in discrete optimization scheduling problems. So, what we're seeing here are some complex scheduling applications. We have interdependencies between a task and the task that follows. In order to model that, we basically have to model for each task which is the next task and then use that to constrain the schedule. Of course, we could also model for each task, which is the previous task and we'd end up having dummy start times, start tasks, but this is the usual way of doing it.
