A resource allocation problem on timed marked graphs: a decomposition approach

Abstract

In complex man-made environments discrete event dynamic systems are frequently encountered, and a timed marked graph is widely accepted as a convenient tool to describe systems of this kind. We consider trade-offs of cost and performance on such a system. First we formulate an optimization problem and transform it into a mixed integer linear programming problem. To improve computational efficiency, we decompose the problem into two phases. In phase one we determine the optimal number of each resource to be adopted in the system, and in phase two we optimize the distribution of these resources over the system. Phase one is solved very quickly and approximately by the dominance relaxation through a binary search procedure. This also gives the estimate of error bounds. An illustrative example shows an application to a jobshop optimization problem, and numerical experiments are carried out for some sample problems.