Optimal solution methods for the minimum-backtracking row layout problem

Abstract

The problem of finding a reordering of the rows (and, simultaneously, the columns) of square matrices has important applications in the areas of combinatorial data analysis, economics and engineering. One such application is the Minimum-Backtracking Row Layout Problem (MBRLP), which involves the sequencing of workstations in an automated assembly line so as to minimize the total backtracking distance. Dynamic programming and integer programming have previously been proposed as optimal solution methods for the MBRLP; however, the latter method was limited to the case of equal distances between positions in the sequence. We demonstrate that the previously suggested integer programming approach for equidistant MBRLPs can produce infeasible solutions, and develop and test a plausible integer programming model for its replacement. We also present an optimal branch-and-bound procedure for MBRLP that requires far less memory storage than dynamic programming. Our experimental tests revealed that both dynamic programming and the branch-and-bound algorithm efficiently provided optimal solutions to MBRLPs with 25 or fewer workstations, and that neither method was superior in all cases. However, the branch-and-bound algorithm was appreciably faster than dynamic programming for some data conditions, and can be used for problems where computer RAM limitations preclude dynamic programming implementation.

Notes

*Table values correspond to CPU time for a 2.2GHz, Pentium IV PC with 1GB of RAM. Within each workflow condition (WC1, WC2 and WC3), results are reported for (DP) and BB. Integer Linear Programming (ILP) results for (ERLP2) are only reported for n = 15 test problems for WC3 because of the computational burden associated with other categories.

*Table values correspond to CPU time for a 2.2GHz, Pentium IV PC with 1GB of RAM. Within each workflow condition (WC1, WC2 and WC3), results are reported for DP and BB.