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


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:

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