A GENERALIZATION OF DYNAMIC PROGRAMMING FOR PARETO OPTIMIZATION IN DYNAMIC NETWORKS

Issue		RAIRO Oper. Res. Volume 34, Number 1, January-March 2000


Page(s)		27 - 47
DOI		10.1051/ro:2000100

DOI: 10.1051/ro:2000100

RAIRO Rech. Opér. (vol. 34, n $^\circ$ 1, 2000, pp. 27-47)

A GENERALIZATION OF DYNAMIC PROGRAMMING FOR PARETO OPTIMIZATION IN DYNAMIC NETWORKS

Teodros GETACHEW, Michael KOSTREVA and Laura LANCASTER

Received July 1996

Clemon University, Department of Mathematical Sciences, Clemson, South Carolina 29634-1907, U.S.A.

Abstract:

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 bath 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.

Résumé:

Keywords: Pareto optimization, dynamic network, shortest path, dynamic programming, time-dependent cost function.

Contents

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.