Suboptimum solution of the back-board ordering with channel capacity constraint

Abstract

The problem dealt with in this paper is the optimum ordering of boards on a linear backplane, which minimizes the maximum number of interboard connections in a large system. First, an approximation algorithm is proposed, which produces a feasible solution whose cost, i.e. the maximum number of interboard connections, is not more than ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1 + \epsilon</tex> ) times the cost of an optimum solution. The algorithm is essentially a branchand-bound method based on Dijkstra algorithm or the uniform cost method, saving computation time and memory space. Second, a quick and straight-forward algorithm is proposed which finds some locally optimum solution very fast and provides a useful information preceding the approximation algorithm. Several experimental results are shown to evaluate the efficiency of the algorithms.