### DIMACS Theoretical Computer Science Seminar

Title: Scheduling an Industrial Production Facility:
Applying theory in practice

Speaker: **Cliff Stein**, Columbia University

Date: February 9, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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)

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html