In this article the authors consider the problem of determining a path between two nodes in a network that minimizes the maximum of r path length values associated with it. This problem has a direct application in scheduling. It also has indirect applications in a class of routing problems and when considering multiobjective shortest-path problems. The authors present a label-correcting procedure for this problem. They also develop two pruning techniques, which, when incorporated in the label-correcting algorithm, recognize and discard many paths that are not part of the optimal path. The present computational results indicate that these techniques are able to speed up the label-correcting procedure by many orders of magnitude for hard problem instances, thereby enabling them to be solved in a reasonable time.
