×

zbMATH — the first resource for mathematics

An improved approach for marking optimization of timed weighted marked graphs. (English) Zbl 1439.90072
Summary: Timed weighted marked graphs are a mathematical formalism suitable to model automated manufacturing systems in which synchronization and bulk services and arrivals appear, such as assembly lines and kanban systems. In this paper, we aim to develop practically efficient methods for the marking optimization of timed weighted marked graphs, a problem which consists in finding an initial resource assignment to minimize the cost of resources under a given requirement on the cycle time. Starting with a live initial marking, we first compute the critical places of a timed weighted marked graph by exploring an equivalent model called timed marked graph. Then, we develop an analytical method to identify the critical circuit of the system to which tokens will be iteratively added. Application to a real manufacturing system is finally provided, which shows that the developed approach is significantly more efficient than the existing ones.
MSC:
90C35 Programming involving graphs or networks
90C90 Applications of mathematical programming
Software:
Gurobi; HYPENS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bhattacharyya, S.; Murthy, P.; Lee, E., Synthesis of embedded software from synchronous dataflow specifications, J VLSI Signal Process, 21, 2, 151-166 (1999)
[2] Campos, J.; Chiola, G.; Silva, M., Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector, IEEE Trans Software Eng, 17, 2, 117-125 (1991)
[3] Cottenceau, B.; Hardouin, L.; Boimond, Jl, Modeling and control of weight-balanced timed event graphs in dioids, IEEE Trans Autom Control, 59, 5, 1219-1231 (2014) · Zbl 1360.93420
[4] Ghamarian AH, Geilen MCW, Stuijk S, Basten T, Moonen AJM, Bekooij MJG, Theelen BD, Mousavi MR (2006) Throughput analysis of synchronous data flow graph. In: Proc. 6th Int appl concur syst design, pp 25-36
[5] Giua, A.; Piccaluga, A.; Seatzu, C., Firing rate optimization of cyclic timed event graphs, Automatica, 38, 1, 91-103 (2002) · Zbl 1015.93034
[6] Govindarajan, R.; Gao, Gr, Rate-optimal schedule for multi-rate dsp computations, J VLSI Signal Process, 9, 3, 211-232 (1995)
[7] Gurobi (2018) Optimization Gurobi. [Online]. Available: http://www.gurobi.com/
[8] He Z, Li ZW, Giua A (2014) Marking optimization of deterministic timed weighted marked graphs. In: Proc. 10th IEEE int. conf. autom. sci. eng.. Taipei, pp 413-418
[9] He, Zhou; Li, Zhiwu; Giua, Alessandro, Cycle Time Optimization of Deterministic Timed Weighted Marked Graphs by Transformation, IEEE Transactions on Control Systems Technology, 25, 4, 1318-1330 (2017)
[10] He, Zhou; Li, Zhiwu; Giua, Alessandro, Optimization of Deterministic Timed Weighted Marked Graphs, IEEE Transactions on Automation Science and Engineering, 14, 2, 1084-1095 (2017)
[11] He, Z.; Li, Zw; Giua, A., Performance optimization for timed weighted marked graphs under infinite server semantics, IEEE Trans Autom Control, 63, 8, 2573-2580 (2018) · Zbl 1423.90078
[12] Lafit S, Proth JM, Xie XL (1991) Marking optimization in timed event graphs. In: Proc. Int conf. appl. theory Petri nets. Springer, Berlin, pp 281-300
[13] Lee, E.; Messerschmitt, D., Synchronous data flow, Proc IEEE, 75, 9, 1235-1245 (1987)
[14] Liu, M.; Wang, Sg; Zhou, Mc; Liu, D.; Al-Ahmari, A.; Wu, Nq; Li, Zw, Deadlock and liveness characterization for a class of generalized Petri nets, Infor Sci, 420, 403-416 (2017)
[15] Ma, Zy; Li, Zw; Giua, A., Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints, IEEE Trans Autom Control, 60, 7, 1774-1785 (2015) · Zbl 1360.93431
[16] Ma, Zy; Li, Zw; Giua, A., Characterization of admissible marking sets in Petri nets with conflicts and synchronizations, IEEE Trans Autom Control, 62, 3, 1329-1341 (2017) · Zbl 1366.93356
[17] Marchetti, O.; Munier, A., Complexity results for weighted timed event graphs, Discrete Optim, 7, 3, 166-180 (2010) · Zbl 1242.90279
[18] Millo, Jv; De Simone, R., Periodic scheduling of marked graphs using balanced binary words, Theor Comput Sci, 458, 113-130 (2012) · Zbl 1262.68025
[19] Munier, A., Régime asymptotique optimal d’un graphe d’événements temporisé généralisé: Application à un problème d’assemblage, RAIRO-APII, 27, 487-513 (1992) · Zbl 0801.90056
[20] Murata, T., Petri nets: properties, analysis and applications, Proc IEEE, 77, 4, 541-580 (1989)
[21] Nakamura M, Silva M (1999a) Cycle time computation in deterministically timed weighted marked graphs. In: Proc. 7th IEEE int conf emerg technol factory autom, vol 2, pp 1037-1046
[22] Nakamura M, Silva M (1999b) An iterative linear relaxation and tabu search approach to minimum initial marking problems of timed marked graphs. In: Proc. European control conf, pp 985-990
[23] Sauer, N., Marking optimization of weighted marked graphs, Discrete Event Dyn Syst, 13, 3, 245-262 (2003) · Zbl 1023.90005
[24] Sessego, Fausto; Giua, Alessandro; Seatzu, Carla, HYPENS: A Matlab Tool for Timed Discrete, Continuous and Hybrid Petri Nets, Applications and Theory of Petri Nets, 419-428 (2008), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1143.68494
[25] Sriram, S.; Bhattacharyya, Ss, Embedded multiprocessors: scheduling and synchronization (2009), Boca Raton: CRC Press, Boca Raton
[26] Stuijk S, Geilen M, Basten T (2006) Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. In: Proc. 43rd Design autom. conf., pp 899-904
[27] Teruel, E.; Chrzastowski-Wachtel, P.; Colom, Jm; Silva, M., On weighted T-systems, Appl Theory Petri Nets, 616, 348-367 (1992)
[28] Tong, Y.; Li, Zw; Seatzu, C.; Giua, A., On the equivalence of observation structures for Petri net generators, IEEE Trans Autom Control, 61, 9, 2448-2462 (2016) · Zbl 1359.93289
[29] Tong, Y.; Li, Zw; Seatzu, C.; Giua, A., Current-state opacity enforcement in discrete event systems under incomparable observations, Discrete Event Dyn Syst, 28, 2, 161-182 (2018) · Zbl 1398.93223
[30] Van Schuppen, Jh; Silva, M.; Seatzu, C., Control of discrete-event systems-automata and Petri net perspectives, Lect Notes Control Inf Sci Springer, 433, 319-340 (2012) · Zbl 1254.93007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.