Advisor(s): Dr. Bruce Weide,
Dr. Shahrukh Irani
Participants: Susan Hohenberger, Tyler Neylon
Start Date: Autumn Quarter 1999
Project Status: Active
Abstract Calendar Project
Development Findings
and ContributionsReturn
to EuropaPFAST, a software package being developed by the OSU Industrial Systems Engineering Department, is currently in need of new and more efficient algorithms for computations on factory layouts. We are currently working with Dr. Shahrukh Irani (IWSE), Dr. Bruce Weide (CIS), and Smart Khaewsukkho (IWSE) on the algorithms for these NP-complete problems.
The project is a matter of developing a heuristically-motivated algorithm which capitalizes on time in order to deliver a near-optimal solution within practical time limits. The complexity of the algorithm for pure optimilism seems so gargantuan as to render the scale of pragmatic applications to nearly null. Thus our algorithm is based on efforts towards highly educated guesses at potentially good solutions, perturbed and hopefully perfected through application of the genetic algorithm.
The current focus is on the cross-breeding and mutation algorithms. We presently have implemented a population initialization technique which is somewhat emiliorated by small doses of chaos, and apparently produces quite satisfactory results. However, much work still remains to be done in order to enable the creatures (each sample factory layout) to mutate (produce an offspring slightly different from a single parent), or breed (produce an offspring by combining the better properties from two parents).
Anyone interested in working on this project is welcome to contact Susan or Tyler.
Smart's Masters Thesis contains an elegant and interactive description of his genetic algorithm.
A good Genetic Algorithm Tutorial may also be useful.
Research continues. The initialization technique employed has yielded significant temporal and quantitative improvements over the previous method. Additional crossover and mutation methods are in development and are predicted to further enhance preformance.
Last modified: Thr Mar 16 18:48:00 EST 2000