NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/ai/genetic/145

Text File | 1993-01-21 | 11.8 KB | 311 lines

Newsgroups: comp.ai.genetic
Path: sparky!uunet!spool.mu.edu!agate!usenet.ins.cwru.edu!eagle!tedwright.lerc.nasa.gov!wright
From: [e-mail] (Ted Wright)
Subject: Genetic Algorithms for Scheduling (Summary)
Message-ID: <[e-mail]>
Lines: 298
Sender: [e-mail]
Nntp-Posting-Host: tedwright.lerc.nasa.gov
Organization: NASA Lewis Research Center
Date: Thu, 21 Jan 1993 19:04:00 GMT
Lines: 298

Thanks to Dave Schaffer and everyone else that responded:

%J ICGA91
%P 10-17
%T Exploring Problem-Specific Recombination Operators for Job Shop Scheduling
%A Sugato Bagchi
%A Serad Uckun
%A Yutaka Miyabe
%A Kazuhiko Kawamura
%X Abstract: In this paper, the development and implementation of a prototype
job shop scheduling system based on a genetic algorithm is described.
To enhance the performance of the algorithm and to expand the search space, a chromosome
representation which stores problem-specific information is devised.
Problem-specific recombination operators which take advantage of the additional
information are also developed. The results of experimentation
on three different representational schemes are discussed.
%K genetic algorithms applications scheduling; operators recombination knowledge-based operators;
relation AI knowledge representation
heuristic crossover

%A Gary A. Cleveland
%A Stephen F. Smith
%T Using Genetic Algorithms to Schedule Flow Shop Releases
%K application to scheduling, novel operators, application to combinatorial problems
%J ICGA89
%W ds1, lje, library
%P 160-169

%J ICGA91
%P 108-114
%T Looking Around: Using Clues from the Data
Space to Guide Genetic Algorithm Searches
%A Hugh M. Cartwright
%A Gregory F. Mott
%X Abstract: For some classes of problem, the most
appropriate parameters in a GA calculation are a function not
only of the problem type, but also of the data used. A
method of assessing suitable population sizes and crossover
rates for the GA solution of flowshop scheduling problems
is described. Appropriate values of these parameters
are shown to be related to the topology of the data
hyperspace. Systems in which the surface of the
hyperspace is relatively smooth appear to be searched more
efficiently by GAs with smaller populations and higher
crossover rates than data sets yielding corrugated surfaces.
The method is illustrated by consideration of flowshop
scheduling systems that generate surfaces of contrasting
character.
%K genetic algorithms operators recombination; implementation techniques data analysis visualization; applications scheduling

%A Lawrence Davis
%T Job Shop Scheduling with Genetic Algorithms
%Y Has a suggestion for producing a genetic algorithm from a deterministic
program for any given problem. The gene decoding approach is not dissimilar
to that used in bin packing paper (see Derek Smith in GAC\&85) - ds1
%J GAC85
%K gene decoding
%P 136-140
%W ds1

%A B. R. Fox
%A M. B. McMahon
%T Genetic Operators for Sequence Problems
%B FOGA91
%P 284-300
%W ds1, lje
%K Genetic Algorithms, scheduling, recombination, space station

%J ICGA91
%P 430-436
%T A System for Learning Routes and Schedules with Genetic Algorithms
%A Paula S. Gabbert
%A Donald E. Brown
%A Christopher L. Huntley
%A Bernard P. Markowicz
%A David E. Sappington
%K genetic algorithms applications scheduling; transportation problems
%X Abstract: A Genetic Algorithm approach to routing and scheduling trains along a rail
network is shown to be a feasible and useful technique.  Routing and
scheduling in the context of a rail freight transportation network for CSX is
discussed.  A representation of this problem for a Genetic Algorithm approach
is proposed and results of the technique are presented.

%A M.R. Hilliard
%A G.E. Liepins
%A Mark Palmer
%A Michael Morrow
%A Jon Richardson
%T A Classifier Based System for Discovering Scheduling Heuristics
%P 231-235
%J GAC87
%W ds1,library
%K genetic algorithm, job shop scheduling

%J ICGA91
%P 437-441
%T Genetic Algorithms and Computer-Assisted Music Composition
%A Andrew Horner
%A David E. Goldberg
%X Abstract: Genetic algorithms have been used with increasing
frequency and effectiveness in a variety of problems. This paper investigates
the application of genetic algorithms to music composition. A technique of
thematic bridging is presented that allows for the specification of thematic
material and delegates its development to the genetic algorithm. A look at
the effects of building block linkage subsequently establishes a basis for
implementing a GA-optimizable operation set for the problem. Some preliminary
results are then discussed with an eye toward future work in GA-assisted
composition.
%K genetic algorithms applications scheduling
algorithmic composition; computer-assisted composition; music

%J ICGA91
%P 264-270
%T Simulated Co-Evolution as The Mechanism for Emergent Planning and
Scheduling
%A Philip Husbands
%A Frank Mill
%X Abstract:  The underlying structure of many combinatorial optimisation
problems of practical interest is highly parallel. However, traditional
approaches to these problems tend to use mathematical characterisations that
obscure this inherent parallelism. By contrast, the use of biologically
inspired models casts fresh light on a problem and may lead to a more general
characterisation which clearly indicates how to exploit parallelism and gain
better solutions. This paper describes a model based on simulated co-evolution
that has been applied to a highly generalised version of the manufacturing
scheduling problem, a problem previously regarded as too complex to tackle.
Results from an implementation on a parallel computer are given.
%K genetic algorithms applications scheduling; relation AI planning
Coevolution; distributed problem solving

%A Nagesh Kadaba
%A Kendall E. Nygard
%A Paul L. Juell
%T Integration of Adaptive Machine Learning and Knowledge-Based
Systems for Routing and Scheduling Applications
%K Connectionism, genetic algorithms, XROUTE, expert system, neural network, cogann ref
%W ds1
%J Expert Systems with Applications: An International Journal
%D 1990
%O NDSU-CS-TR-89-25

%J ICGA91
%P 466-473
%T A Hybrid Genetic Algorithm for
Task Allocation in Multicomputers
%A Nashat Mansour
%A Geoffrey C. Fox
%X Abstract: A hybrid genetic algorithm (HGATA) is proposed
for the task allocation problem in parallel computing.  It includes
elitist ranking selection, variable rates for the genetic operators,
the inversion operator and hill-climbing of individuals. Hill-climbing
is done by a simple heuristic procedure tailored to the application.
HGATA minimizes the likelihood of premature convergence and finds
good solutions in a reasonable time. It also makes use of problem-
specific knowledge to evade some computational costs and to reinforce
some favorable aspects of the genetic search. The experimental results
on realistic test cases support the HGATA approach for task allocation.
%K genetic algorithms applications scheduling
Combinatorial optimization; Load balancing;
Parallel computing; Task allocation; "

%A Kendall E. Nygard
%A Paul L. Juell
%A Nagesh Kadaba
%T Artificial Intelligence in Routing and Scheduling Applications
%I Dept. of CS and OR, North Dacota State University
%D 1989
%W ds1
%K genetic algorithms, expert systems, connectionism, neural networks, cogann ref

%J ICGA91
%P 474-479
%T Conventional genetic algorithm for job shop problem
%A Ryohei Nakano
%A Takeshi Yamada
%X Abstract: The job shop problem (JSP) is NP-hard, much harder than
the traveling salesman problem.
This paper shows how a conventional Genetic Algorithm can efficiently
solve the JSP.
We introduce unique ideas in representation, evaluation, and survival.
A solution is succinctly represented as a binary genotype even though
the JSP is an ordering problem.
Mostly a genotype {\bf g} produced by conventional crossover is
illegal, i.e., represents no feasible schedule.
Therefore an evaluation function first finds a legal genotype {\bf g'}
as similar to {\bf g} as possible, and then evaluates {\bf g'} to
determine the fitness of {\bf g}.
The fitness of {\bf g} is evaluated as the total elapsed time of the
corresponding schedule.
In survival of genotypes, we introduce a new treatment, called forcing,
that replaces the genotype {\bf g} with {\bf g'} when {\bf g} is
selected as the survivor.
Forcing both quickens convergence of Genetic Algorithms and drastically
improves solution quality.
A conventional Genetic Algorithm using the three ideas is applied to
three well-known JSP benchmarks.
The solution quality approaches those obtained by branch and bound
methods.
%K genetic algorithms applications scheduling; relation AI heuristic search
job shop problem;

%J ICGA91
%P 69-76
%T A Comparison of Genetic Sequencing Operators
%A T. Starkweather
%A S. McDaniel
%A K. Mathias
%A C. Whitley
%A Darrell Whitley
%X Abstract: This work compares six sequencing operators that have been developed
for use with genetic algorithms.
An improved version of the edge recombination operator
is presented, the concepts of adjacency, order, and
position are reviewed in the context of these operators,
and results are compared for a 30 city ``Blind'' Traveling
Salesman Problem and a real world warehouse/shipping scheduling application.
Results indicate that the effectiveness
of different operators is dependent on the problem domain;
operators which work well in problems where adjacency is
important (e.g., the Traveling Salesman) may not be effective for
other types of sequencing problems.
Operators which perform poorly on the Blind Traveling Salesman
Problem work extremely well for the warehouse scheduling task.
%K genetic algorithms applications scheduling; operators recombination other recombinators;
population dynamics age structure
Edge Scheduling, Traveling Salesman

%J ICGA91
%P 502-508
%T The Application of Genetic Algorithms to Resource Scheduling
%A Gilbert Syswerda
%A Jeff Palmucci
%K genetic algorithms applications scheduling;
%X Abstract: We present a detailed report of the construction of an optimizer for a
resource scheduling application.  The optimizer is a combination of local
expert search and global search provided by a genetic algorithm.  We present
the issues confronted in solving this real-world scheduling problem, show how
we addressed these issues, and describe how we isolated the genetic algorithm
portion of the system from these details.  The resulting optimizer provides a
good tradeoff between quickly providing good results and improving schedules
with further search.

%A Gilbert Syswerda
%T Schedule Optimization Using Genetic Algorithms
%P 332-349
%K scheduling, application systems integrated test station,
Navy
%B Handbook of Genetic Algorithms
%E Lawrence Davis
%I VNR
%D 1991
%W ds1

%A N.L.J. Ulder
%T Genetic Local Search: A Population-based Search Algorithm
%R Nat. Lab. Technical Note NR. 050/90
%I N.V. Philips
%C Eindhoven, Netherlands
%D FEB 27, 1990
%W ds1
%K hybrid, hillclimbing, traveling salesman, TSP, jobshop scheduling
%Y combines genetic algorithm and hillclimbing -- ds1

%A Darrell Whitley
%A Timothy Starkweather
%A D'Ann Fuquay
%T Scheduling Problems and Traveling Salesmen:
The Genetic Edge Recombination Operator
%K application to combinatorial problems, novel operators, GENITOR, application to scheduling, problem: traveling salesperson, sequencing problems, representation: binary
%J ICGA89
%W ds1, lje, library
%P 133-140

%A Darrell Whitley
%A Timothy Starkweather
%A Daniel Shaner
%T The Traveling Salesman and Sequence Scheduling:
Quality Solutions Using Genetic Edge Recombination
%P 350-372
%K algorithms, TSP
%B Handbook of Genetic Algorithms
%E Lawrence Davis
%I VNR
%D 1991
%W ds1


Ted Wright ([e-mail])
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.0

mQCNAiqvp90AAAEEAO0VFsrmnZhmALDOZEG6vPlTwB5jqM5swOkhDqJIOHOtyNug
2ZfCpsQUYcrVCKjGs4zaivEoiQxi+538mwNhL9HXQK+I3HR2xESzpJEoLiv62kMI
cwVbEw9QAuxY7Z01KHi+bNYhYQvzBczaVttPJdOTvNpbUCzWIeKXEM95WINbAAUR
tChUZWQgV3JpZ2h0IDx3cmlnaHRAbGltczAxLmxlcmMubmFzYS5nb3Y+
=uu9S
-----END PGP PUBLIC KEY BLOCK-----