Getting cheaper boats and ships

I am in Providence attending this year’s Constraint Programming conference. I’m on the executive and we have developed new bylaws, so instead of listening to all the talks, I am involved in discussions on the minutia of quorums and transition rules. Still, there is some time for the conference itself.

I just saw a terrific talk by Matt Ginsberg of the University of Oregon and On Time Systems, a firm specializing in scheduling optimization. One of the big things they do is shipyard optimization, and he described putting together a system for better scheduling the production of navy submarines (which are boats) and carriers (which are ships). While traditional scheduling involves trying to minimize the amount of time it takes to build something, this sort of scheduling is about minimizing costs (or so he thought). So his firm put together a nice system to minimize the cost of going through the tens of thousands of tasks that go into a boat or ship. If that was the end of the talk, it would have been a fine technical talk on an interesting topic. But he went further.

“Just because a schedule looks good doesn’t mean it is good” is a phrase I wish more people would use. Lots of schedules look good, but when you try to use them they fail for easy-to-see-in-retrospect reasons. One example of this is the highly optimized crew schedules used by airlines. Sure, they look good and they appear to save money, but they are fragile: disruptions can spread throughout the system. Matt brought up two important issues not covered by the “minimize cost” aspects of their schedules. The first is the brittleness seen in airline crew schedules: will delays in one task mess up more? The second is union buy-in. If the goal is to decrease costs, won’t unions naturally be against it?

The brittleness point is important. Indeed, a minimum cost schedule is brittle (though perhaps no more brittle than the schedule currently in place), though it saves about 10.4% on costs. But the methods Matt used can be adapted to make float (the amount any task can be delayed without affecting other tasks) into account. A task with too little float (perhaps just a few work shifts) is at risk of delaying the whole project. But you can combine these objectives: minimize cost and minimize number of tight tasks. It turns out that you can decrease the number of tight tasks by more than 90% (relative to the current schedule) and still save about 10.3% on costs (numbers approximate: I have to learn to take better notes!). So decreasing brittleness comes almost for free!

As for the unions, one fact about shipyards is that they often layoff and then rehire lots and lots of workers. The schedules Matt provides are much smoother in the way they use workers. Certainly far more workers would have consistent jobs under the schedules, and layoffs would not occur near as often.

Overall, the shipbuilders would save money, the unionized workers would have more consistent jobs, and the building process would be less susceptible to delays. What’s not to like?

Well, the firms building the ships are paid by the Navy on a cost-plus basis. The higher the cost, the higher the plus. So they have essentially no interest in saving our money. They like high costs! Next time you see your congressman or -woman, ask “What happened to the ARGOS project to improve ship-building operations? Wasn’t that supposed to save us a few billion dollars?”

While we wait for the companies to work more efficiently, On Time Systems has a scheduling game you can play.