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:
See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html