A Petri net representation for dynamic programming problems in management applications

Dynamic programming (DP) is a very general optimization technique, which can be applied to numerous management decision problems. In order to develop a software system that automates many of the tasks a user encounters when attempting to solve an instance of an optimization problem with discrete DP an intermediate problem representation in the form of a Petri net (PN) turns out to be useful. The specialized PN model presented in this paper captures the essential components of a DP problem instance. It uses the standard semantics of place/transition nets, a low-level PN class, whereas previous work (Lew, 2002; Lew and Mauch, 2003; and Mikoljczak and Rumbut, 1997) relied on high-level PNs. This approach is illustrated by a simple financing example, but the methodology works for a wide range of management problems and can be applied to more complex instances. Among the benefits of this representation are the possibility to perform consistency checks on the PN level and the existence of a simple procedure to translate a model instance into executable code that could be integrated into existing solvers. Also, a software system currently under development automates the task of transforming a DP functional equation into the PN model suggested in this paper. Users need not construct the PN model directly.