On the effectiveness of Monte Carlo simulation and heuristic search for solving large-scale block layout problems |
| |
Authors: | Wai Kin Victor Chan & Charles J Malmborg |
| |
Affiliation: | 1. Department of Industrial and Systems Engineering , Rensselaer Polytechnic Institute , Troy , New York , USA malmbc@rpi.edu |
| |
Abstract: | The effectiveness of Monte Carlo simulation relative to intelligent search strategies for solving block layout problems is investigated. For testing purposes, 810 block layout problems are constructed to span a wide range of problem sizes, material flow variation levels, work centre space requirements distributions, and work centre shape distributions. Contrary to preliminary results reported in earlier studies, greedy search and simulated annealing consistently outperform Monte Carlo Simulation across the full range of test problems and sample sizes. This divergence is explained through a comparison based on probabilistic derivations between the proportion of good solutions sampled by the Monte Carlo method and those found by the heuristic search methods. Conditions for the superiority of either method are identified. Therefore, the current study complements earlier studies by providing analytical arguments and additional experimental evidence for the effectiveness of simple Monte Carlo method and intelligent search heuristics on solving layout problems. |
| |
Keywords: | block layout materials handling cost Monte Carlo simulation simulated annealing greedy algorithm |
|
|