A timed model for the control of discrete event systems involving decisions in the max/plus algebra

The class of discrete event systems that can be modeled as timed event graphs may be described by linear equations in nontraditional algebraic systems where the allowed operations are maximization and addition (`max/plus´ algebra). Event graphs are deterministic in the sense that no decisions are permitted in the systems modeled. The algebraic approach is extended to a broader class of systems which require decisions to be made at certain times in the evolution. Algebraic tools are introduced for modeling sequences of decisions and it is shown that decision-making systems so represented are linear in the resulting algebra. Using this framework, it is possible to evaluate any arbitrary control policy and compare it against a target output criteria or compute an optimal policy