An Algorithm for a Class of Three-Dimensional Assignment Problems Arising in Scheduling Applications

Abstract

A scheduling problem often arising in trade shows and conventions is modeled as a planar three-dimensional assignment problem having a special cost structure. A polynomial-time algorithm for solving this case of the planar assignment problem is presented. The algorithm can also be used to solve heuristically a variation of the m-traveling salesman problem which arises as a secondary problem in the original scheduling application. Computational experience with data from a tourism industry convention scheduling problem is given.