Complexity results for Weighted Timed Event Graphs

AbstractThe minimization of the amount of initial tokens in a Weighted Timed Event Graph (in short WTEG) or a Timed Event Graph (in short TEG) under throughput constraint is a crucial problem in industrial area such as the design of manufacturing systems or embedded systems. Two important variants are studied in this paper: the first one concerns the maximization of the throughput for minimum places capacities of a TEG. It is proved NP-complete by a polynomial reduction with the K-colorability problem. The second one is the minimization of the overall places capacities with a maximum throughput. This problem is also proved NP-complete for a TEG. A polynomial subcase and a 2-approximation polynomial algorithm for a WTEG are then provided