Optimization of Deterministic Timed Weighted Marked Graphs

Timed marked graphs, a special class of Petri nets, are extensively used to model and analyze cyclic manufacturing systems. Weighted marked graphs are convenient to model systems with bulk services and arrivals. We consider two problems of practical importance for this class of nets. The marking optimization problem consists in finding an initial marking to minimize the weighted sum of tokens in places while the average cycle time is less than or equal to a given value. The cycle time optimization problem consists in finding an initial marking to minimize the average cycle time while the weighted sum of tokens in places is less than or equal to a given value. We propose two heuristic algorithms to solve these problems. Several simulation studies show that the effectiveness of the proposed approach is significantly faster than existing ones. Note to Practitioners—This paper is motivated by the optimization of manufacturing systems such as assembly lines and job-shops. The quantity of products which have to be stored or moved and the number and type of machines which operate the system have economical consequences. Therefore, the main problem for designers is to find a trade-off between minimizing the cost of the resources and maximizing the system’s throughput. To this end, we formalize and address two problems. First, we aim to minimize the use of resources required to meet a desired throughput. Second, we aim to maximize the throughput with a given set of available resources. However, the existing result