Evolving a schedule with batching, precedence constraints, and sequence-dependent setup times: crossover needs building blocks

Darwen, Paul J. (2002) Evolving a schedule with batching, precedence constraints, and sequence-dependent setup times: crossover needs building blocks. In: Lecture Notes in Computer Science (2358), pp. 525-535. From: IEA/AIE 2002: 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 17-20 June 2002, Cairns, QLD, Australia.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website: http://dx.doi.org/10.1007/3-540-48035-8_...
 
2


Abstract

The Travelling Salesman Problem (TSP) has a "big valley" search space landscape: good solutions share common building blocks. In evolutionary computation, crossover mixes building blocks, and so crossover works well on TSP. This paper considers a more complicated and realistic single-machine problem, with batching/lotsizing, sequence-dependent setup times, and time-dependent costs. Instead of a big valley, it turns out that good solutions share few building blocks. For large enough problems, good solutions have essentially nothing in common. This suggests that crossover (which mixes building blocks) is not suited to this more complex problem.

Item ID: 38935
Item Type: Conference Item (Refereed Research Paper - E1)
Keywords: travelling salesman problem, genetic algorithms, batching, lotsizing, sequence-dependent setup times, time-dependent costs
Related URLs:
ISBN: 978-3-540-48035-8
ISSN: 0302-9743
Date Deposited: 30 Jan 2017 22:50
FoR Codes: 08 INFORMATION AND COMPUTING SCIENCES > 0801 Artificial Intelligence and Image Processing > 080108 Neural, Evolutionary and Fuzzy Computation @ 100%
SEO Codes: 86 MANUFACTURING > 8614 Machinery and Equipment > 861403 Industrial Machinery and Equipment @ 20%
86 MANUFACTURING > 8612 Fabricated Metal Products > 861299 Fabricated Metal Products not elsewhere classified @ 10%
86 MANUFACTURING > 8699 Other Manufacturing > 869999 Manufacturing not elsewhere classified @ 70%
Downloads: Total: 2
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page