ABSTRACT
This chapter presents basic complexity results and a methodology to solve polynomially the optimization problem. The optimization problem is proved to be NP-complete for a marked event graph. Several polynomial transformations reduce subsequently the structure of the marked timed weighted event graph (MTWEG) if it is supposed to be live with places of bounded capacity. The chapter presents a brief description of timed weighted event graph (WEG) and their associated feasible schedules. A simple academic example is also described, followed by the characterization of the infinite set of precedence relations associated to any MTWEG. The chapter shows that if the capacity of places has to be bounded, the timed WEG studied must be limited to a subclass of nets called symmetric normalized graphs. MTWEG considered for modelling data exchanges for streaming applications: transitions correspond to specific treatments. Places are associated with buffers. However, these systems are usually modelled using synchronous dataflow graphs, which are strictly equivalent to MTWEG.
