A New Graph-Theoretic Heuristic for Facility Layout
提出一种新启发式算法，用于解决设施布局中确定机器相邻关系的问题，该问题可建模为求图的最大权重平面子图。初步计算表明算法表现良好，对工业工程和调度领域有参考价值。
The facility layout problem is important in the modern manufacturing environment because increased machine flexibility and product diversification create additional complexities in scheduling and material handling. An important first step in facility layout is the determination of which machines should be adjacent. This problem can be modelled as that of finding a maximum weight planar subgraph of a graph, given a measure of the desirability that two machines be adjacent based on the anticipated flows and technological constraints. We present a new heuristic that is a generalization of previous work of Foulds and Robinson. Preliminary computational results are presented which suggest that this heuristic performs well.