A Dynamic Programming Algorithm for Check Sorting

The motivation for this paper is a problem faced by banks which process large volumes of deposited checks. The checks must be separated by bank number before shipment to the Federal Reserve or other banks. The sorting is usually accomplished using a reader-sorter which reads the magnetic ink characters on the checks and separates them into different “pockets.” This paper characterizes the optimal sorting strategy and describes an efficient procedure for finding the optimal solution for problems of the size generally found in practice. The algorithm is based on a two state dynamic programming recursion in which characterization theorems are used to drastically reduce the size of the state space and in which the storage requirements are minimal. The paper includes an analysis of computational experience and describes how the algorithm can be used in a real time environment with deadlines.

• 저널Management Science · 24(1) · 59–70
• 토픽Algorithms and Data Compression · Artificial Intelligence
• DOI10.1287/mnsc.24.1.59
• 저자Frederic H. Murphy, Edward A. Stohr