A dynamic programming approach to sequencing problems

Abstract

This paper explores a dynamic programming approach to the solution of three sequencing problems: a scheduling problem involving arbitrary cost functions, the traveling-salesman problem, and an assembly line balancing problem. Each of the problems is shown to admit of numerical solution through the use of a simple recursion scheme; these recursion schemes also exhibit similarities and contrasts in the structures of the three problems. For large problems, direct solution by means of dynamic programming is not practical, but procedures are given for obtaining good approximate results by solving sequences of smaller derived problems. Experience with a computer program for the solution of traveling-salesman problems is presented.