ahlenius@cell.mot.COM (Mark Ahlenius) (12/14/89)
I am interested in real world applications for simulated annealing. And was wondering if anyone has been using this technique in the "AI field". If so what type of applications has it been used for. Specifically, has anyone used it for applications such as scheduling (like production, etc)? Thanks, -- regards 'mark ahlenius uunet!motcid!ahleniusm
winfave@dutrun.UUCP (Alexander Verbraeck) (12/14/89)
In article <558@granite3.UUCP> ahlenius@cell.mot.COM (Mark Ahlenius) writes: >I am interested in real world applications for simulated >annealing. And was wondering if anyone has been using this >technique in the "AI field". If so what type of applications >has it been used for. > >Specifically, has anyone used it for applications such >as scheduling (like production, etc)? > > Thanks, > 'mark ahlenius Yes, simulated annealing has been used in scheduling applications. I have here in front of me the PhD-thesis of Peter van Laarhoven with the title "Theoretical and Computational Aspects of Simulated Annealing". In this thesis, an empirical analysis of the approach is used on the TSP (Travelling Salesman Problem), the Job Shop Scheduling problem and the Football Pool Problem. The conclusions of this chapter: - the s.a. algorithm has a potential for finding high-quality solutions. - it takes a lot of computing time - s.a. is not a panacea: some sophisticated tailored algorithms from literature are often competitive with and often superior to s.a. - formulating a problem in a way that lends itself to application of simulated annealing is not a trivial task. Once an algorithm is found, the algorithm is easy to implement. I myself haven't used the algorithm in solving production planning (scheduling) problems yet. I plan to do so in the near future. If anyone is interested in more information, post or e-mail. I can perhaps dig up some more literature on this topic. ---------------------------------------------------------------------- Alexander Verbraeck e-mail: winfave@dutrun.tudelft.nl Delft University of Technology winfave@hdetud1.bitnet Department of Information Systems winfave@dutrun.uucp PO Box 356, 2600 AJ The Netherlands dutrun!winfave@hp4nl.uucp ----------------------------------------------------------------------
andrew@dtg.nsc.com (Lord Snooty @ The Giant Poisoned Electric Head ) (12/14/89)
In article <558@granite3.UUCP>, ahlenius@cell.mot.COM (Mark Ahlenius) writes: > I am interested in real world applications for simulated > annealing. And was wondering if anyone has been using this > technique in the "AI field". If so what type of applications > has it been used for. It's being used in quite mundane ways - not what you might expect (i.e. dazzling neural paradigms and the like). For example, in many VLSI CAD packages, the place/route function is often implemented thusly. -- ........................................................................... Andrew Palfreyman a wet bird never flies at night time sucks andrew@dtg.nsc.com there are always two sides to a broken window
gary@hpavla.HP.COM (Gary Jackoway) (12/15/89)
Simulated Annealing has been used in the field of IC and Printed Circuit design, specifically in the placement of parts on the chip or board. If you get a copy of any of the last 3 DAC's (design automation conference proceedings), you'll see plenty of articles on the subject. Paper 35.1 from the 1986 conference gives an overview of papers before that date. I attended several of the discussions concerning the worthiness of SA in the autoplacement field and the bottom line was this: SA with correct temperature control gives excellent results, perhaps better than current methods can manage; you have to be willing to wait (and wait, and wait...). SA is very slow. The major issue was whether the time it takes was worth it. (If its ten times slower than an existing method, then you can use that existing methods ten times with different starting positions and different placement modification rules, and keep the best result.) Hope this helps. Gary Jackoway
cjoslyn@bingvaxu.cc.binghamton.edu (Cliff Joslyn) (12/15/89)
In article <1031@dutrun.UUCP> winfave@dutrun.UUCP (A.Verbraeck) writes: > >If anyone is interested in more information, post or e-mail. I can >perhaps dig up some more literature on this topic. I for one would be *very* interested in seeing a basic bibliography on s.a. Thanks -- O-------------------------------------------------------------------------> | Cliff Joslyn, Cybernetician at Large, cjoslyn@bingvaxu.cc.binghamton.edu | Systems Science, SUNY Binghamton, Binghamton NY 13901, USA V All the world is biscuit shaped. . .