A robust heuristic for batting order optimization under uncertainty

Baseball teams are faced with a difficult scheduling problem every day: given a set of nine players, find the optimal sequence in which they should bat. Effective optimization can increase a team's win total by up to 3 wins per season, and 10% of all Major League teams missed the playoffs by 3 or less wins in 1998. Considering the recent $252 million contract given to one player, it is obvious that baseball is a serious business in which making the playoffs has large financial benefits. Using the insights gleaned from a Markov chain model of baseball, we propose a batting order optimization heuristic that performs 1,000 times faster than the previous best heuristic for this problem. Our algorithm generates batting orders that (i) are optimal or near-optimal, and (ii) remain robust under uncertainty in skill measurement.