Scheduling an Industrial Production Facility:
Applying theory in practice

Cliff Stein
Columbia University

Managing an industrial production facility requires carefully
allocating limited resources, and gives rise to large, potentially
complicated scheduling problems.  In this talk we consider a specific
instance of such a problem: planning efficient utilization of the
facilities and technicians that maintain the United States nuclear
stockpile.
A detailed study of this problem yields a complicated mixed-integer
programming (MIP) model with upward of hundreds of thousands of
variables and even more constraints.  Consistently and quickly solving
such a model exactly is impossible using today's algorithms and
computers, and thus, in addition to using branch-and-bound, we must
use good heuristics and approximation algorithms.

This talk studies several different methods of generating good
solutions, given the solution to the IP relaxation.
We design a suite of sample data and test the algorithms. 

The goals of this project are twofold.  First, we want to develop a
program that could efficiently and accurately help with the 
planning problem.  Second, we want to 
experimentally test various ideas, designed originally for ``cleaner''
problems, in this more challenging context.  This talk will 
focus on the second goal. In summary, we demonstrate the value
of using alpha-points as a way to quickly and cheaply generate,
from one solution of an LP relaxation, many feasible solutions to an
integer program.  In this particular envivonment, the use of
alpha-points, combined with other clever heurstics outperforms local
search.  We also see the value of finding combinatorially-structured
subproblems as opposed to using simple greedy approaches.  

Joint work with:
E. Asgiersson (Columbia University)
J. Berry (Lafayette College)
C. Phillips (Sandia National Labs)
D. Phillips (Columbia University)
J. Wein (Polytechnic University)

--------------------