Article ID: | iaor20052776 |
Country: | France |
Volume: | 34 |
Issue: | 1 |
Start Page Number: | 27 |
End Page Number: | 47 |
Publication Date: | Jan 2000 |
Journal: | RAIRO Operations Research |
Authors: | Kostreva Michael M., Getachew Teodros, Lancaster Laura |
Keywords: | programming: dynamic, programming: network |
The algorithm in this paper is designed to find the shortest path in a network given time-dependent cost functions. It has the following features: it is recursive; it takes place both in a backward dynamic programming phase and in a forward evaluation phase; it does not need a time-grid such as in Cook and Halsey and Kostreva and Wiecek's ‘Algorithm One’; it requires only boundedness (above and below) of the cost functions; it reduces to backward multi-objective dynamic programming if there are constant costs. This algorithm has been successfully applied to multi-stage decision problems where the costs are a function of the time when the decision is made. There are examples of further applications to tactical delay in production scheduling and to production control.