Skip to content

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.

{ 3 } Comments

  1. Mark | September 27, 2007 at 11:23 am | Permalink

    Matt’s talk was nice, but the technical stuff has all been done before (including sufficient float in the schedule, using cost as an objective). I was disappointed that he claimed these were new ideas in his talk.

  2. Matt Ginsberg | October 8, 2007 at 5:11 pm | Permalink

    Thanks very much, Michael! It was a fun talk to give — although now I’ve been invited to repeat it at a shipbuilding conference, and I should probably buy some flame-retardant clothing in preparation …

    Mark, to the best of my knowledge, there are no cost-optimization algorithms out there except for ours. If there is a citation you can point me to or anything along those lines, I’d appreciate it. I certainly believed (and still believe) all the technical results I presented to be novel, but don’t want to give that impression if they aren’t.

  3. shiva subramanian | October 11, 2007 at 11:57 am | Permalink

    I’m a regular reader of your blog.

    Your comment regarding the brittleness of crew schedules is partly true. However, from past experience building crew schedules for a large US airline, the aim has never been cost minimization. Rather, it is an explicit tradeoff between company costs, schedule robustness, crew quality of life, and several other goals and constraints, with clear, measurable metrics for each component. Despite this, crew schedules do break.

{ 1 } Trackback

  1. […] patent) talks about his thinking in this matter. I hadn’t put two and two together: I have blogged on Matt before! Posted by Michael Trick on Sunday, October 10, 2010, at 12:43 pm, and filed under Legal, […]