A Stochastic Programming Approach to Scheduling in TAC SCM.
Mike Benisch, Amy Greenwald, Victor Naroditskiy, and Michael Tschantz
Abstract
In this paper, we combine two approaches to handling uncertainty:
we use techniques for finding optimal solutions in the expected
sense to solve combinatorial optimization problems in an online
setting. The problem we address is the scheduling component of the
Trading Agent Competition in Supply Chain Management (TAC SCM) problem, a combinatorial
optimization problem with inherent uncertainty. This problem is
formulated as a stochastic program, and is solved using the sample
average approximation (SAA) method in an online setting to find
today's optimal schedule, given probabilistic models of the future.
This optimization procedure forms the heart of Botticelli, one of the
finalists in the TAC SCM 2003 competition.
Two sets of experiments are described, using one and two days'
worth of information about the future. In the two day experiments
(using one day's worth of information about the future), it is
shown that SAA outperforms the expected value method, which
solves a deterministic variant of the problem assuming all
stochastic inputs have deterministic values equal to their
expected values. In the three day experiments (using two days'
worth of information about the future), it is shown that SAA with
lookahead outperforms greedy SAA. This approach generalizes to
N days of lookahead, and since the problem setting is one
of online optimization, the benefits of two day lookahead accrue
rapidly. It remains to show that our approach improves the
performance of agents in TAC SCM.