A Sequential Method for Discrete Optimization Problems and its Application to the Assignment, Travelling Salesman, and Three Machine Scheduling Problems

Abstract

A discrete optimization problem is defined in which a number of items are to be arranged in a sequence of positions in order to obtain a minimum cost configuration. A simple sequential method is proposed for the solution of this problem. The method is composed of two stages. The first stage builds up an initial arrangement by introducing the items into the positions individually. The second stage adjusts these positions until no further improvement can be made by a simple alteration of the arrangement. The aim of the method is to provide near optimum results with relatively little calculation. The scheme is shown to be successful on a number of well known problems in operations research.