Newsgroups: comp.databases Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!ames!haven.umd.edu!uvaarpa!polaris.cv.nrao.edu!polaris.cv.nrao.edu!dwells From: dwells@fits.cx.nrao.edu (Don Wells) Subject: Re: scheduling software Sender: news@polaris.cv.nrao.edu (News Manager) Message-ID: In-Reply-To: jgb@prism.gatech.EDU's message of 31 May 91 02: 32:07 GMT Date: Fri, 31 May 1991 12:26:17 GMT References: <1991May30.135005.2616@macc.wisc.edu> <30248@hydra.gatech.EDU> Organization: National Radio Astronomy Observatory, Charlottesville, VA Lines: 26 In article <30248@hydra.gatech.EDU> jgb@prism.gatech.EDU (James G. Baker) writes: ... Does your application approach an "NP-complete" problem? You can quickly reach the "lifetime of universe" run-times if not careful. Often, it is reduced to letting the computer to the "best it can" and then allow for some manual playing. My scheduling gets it down to about a 6/200 ratio of problems. The computer "could" do it, but would have to try all combinations potentially. It also does it in about 45 seconds (a nervous 45 seconds, that is :-). Mine was on a PC for cost's sake. Anyone who needs to solve scheduling problems which verge on NP-complete should be aware of the SPIKE system which is used to schedule the Hubble Space Telescope, a *very* difficult case. SPIKE uses a neural net approach, with remarkable success. The key developer is Mark Johnson at the Space Telescope Science Institute in Baltimore, MD. A knowledgeable contact in Europe is Hans-Martin Adorf at the Space Telescope European Coordinating Facility, located at the European Southern Observatory in Garching bei Muenchen. -- Donald C. Wells Associate Scientist dwells@nrao.edu National Radio Astronomy Observatory +1-804-296-0277 Edgemont Road Fax= +1-804-296-0278 Charlottesville, Virginia 22903-2475 USA 78:31.1W, 38:02.2N