ANALYSIS OF THREE SERVERS CLOSED SERIES QUEUING NETWORK WITH DELAY TIME USING MAX-PLUS ALGEBRA
Abstract
Max-Plus Algebra, which is the union of the set of all real numbers with an infinite singleton, equipped with maximum (max) and plus (+) operations, can be used to model and analyze algebraically the dynamics of a closed queuing network. This study aims to analyze the effect of delays in the start time of service activities on a closed series queuing network with three servers. This study is a study based on literature studies, mathematical model studies and simulations assisted by the Scilab computer program. The results show that the max-plus eigenvalue of a closed series queuing network with 3 servers, which is also the periodicity of network dynamics, is the largest service time of the server in the network. Delays in servers with the largest service time will continue to propagate for subsequent schedules. Delays in servers whose service time is not the maximum can still be tolerated, as long as the delay does not exceed the size of the element in the initial max-plus eigenvector, which corresponds to its largest service time. In this case, the system will be able to return to normal according to the original schedule, after undergoing a maximum of 4 stages of the service process since the beginning of the delay. Meanwhile, delays that exceed this will cause network scheduling to be late and will continue to spread to subsequent services.
Downloads
References
F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, SYNCHRONIZATION AND LINEARITY : AN ALGEBRA FOR DISCRETE EVENT SYSTEMS. Paris: Wiley, 2001. Accessed: Feb. 02, 2024. [Online]. Available: https://www.rocq.inria.fr/metalau/cohen/documents/BCOQ-book.pdf.
B. Heidergott, G. J. Olsder, and J. van der Woude, MAX PLUS AT WORK. Princeton: Princeton University Press, 2006. [Online]. Available: http://about.jstor.org/terms.
M. A. Rudhito, ALJABAR MAX-PLUS DAN PENERAPANNYA. Yogyakarta: Sanata Dharma University Press, 2016.
N. K. Krivulin, “A MAX-ALGEBRA APPROACH TO MODELING AND SIMULATION OF TANDEM QUEUEING SYSTEMS,” 1995. doi: https://doi.org/10.48550/arXiv.1212.0895.
N. K. Krivulin, “THE MAX-PLUS ALGEBRA APPROACH IN MODELLING OF QUEUEING NETWORKS,” in Summer Computer Simulation Conference, Portland: SCS, Jul. 1996, pp. 485–490. doi: https://doi.org/10.48550/arXiv.1212.0895.
Subiono, “ALJABAR MIN-MAX PLUS DAN TERAPANNYA,” 2015.
N. K. Krivulin, “ALGEBRAIC MODELLING AND PERFORMANCE EVALUATION OF ACYCLIC FORK-JOIN QUEUEING NETWORKS,” in Advances in Stochastic Simulation Methods, V. B. and E. S. Balakrishnan N. and Melas, Ed., Boston, MA: Birkhäuser Boston, 2000, pp. 63–81. doi: https://doi.org/10.1007/978-1-4612-1318-5_5.
J. Komenda, S. Lahaye, J. L. Boimond, and T. van den Boom, “MAX-PLUS ALGEBRA AND DISCRETE EVENT SYSTEMS,” in IFAC-PapersOnLine, Elsevier B.V., Jul. 2017, pp. 1784–1790. doi: https://doi.org/10.1016/j.ifacol.2017.08.163.
B. De Schutter, T. van den Boom, J. Xu, and S. S. Farahani, “ANALYSIS AND CONTROL OF MAX-PLUS LINEAR DISCRETE-EVENT SYSTEMS: AN INTRODUCTION,” Discrete Event Dynamic Systems: Theory and Applications, vol. 30, no. 1, pp. 25–54, Mar. 2020, doi: https://doi.org/10.1007/s10626-019-00294-w.
M. Hoekstra, “CONTROL OF DELAY PROPAGATION IN RAILWAY NETWORKS USING MAX-PLUS ALGEBRA,” Delft University of Technology, Delft, 2020. Accessed: Feb. 02, 2024. [Online]. Available: http://resolver.tudelft.nl/uuid:b5816386-0ed9-4760-a6de-f0db0c3a5226
G. Vissers, “MAX-PLUS EXTENSIONS A STUDY OF TRAIN DELAYS,” Delft University of Technology, Delft, 2022. [Online]. Available: http://repository.tudelft.nl/.
H. Al Bermanei, Applications of Max-Plus Algebra to Scheduling. Abo: Abo Akademi University Press, 2021.
C. Martínez-Olvera and J. Mora-Vargas, “A MAX-PLUS ALGEBRA APPROACH TO STUDY TIME DISTURBANCE PROPAGATION WITHIN A ROBUSTNESS IMPROVEMENT CONTEXT,” Math Probl Eng, vol. 2018, 2018, doi: https://doi.org/0.1155/2018/1932361.
P. Majdzik, “A FEASIBLE SCHEDULE FOR PARALLEL ASSEMBLY TASKS IN FLEXIBLE MANUFACTURING SYSTEMS,” International Journal of Applied Mathematics and Computer Science, vol. 32, no. 1, pp. 51–63, Mar. 2022, doi: https://doi.org/0.34768/amcs-2022-0005.
Z. Sya’diyah, “MAX PLUS ALGEBRA OF TIMED PETRI NET FOR MODELLING SINGLE SERVER QUEUING SYSTEMS,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 17, no. 1, pp. 0155–0164, Apr. 2023, doi: https://doi.org/10.30598/barekengvol17iss1pp0155-0164.
B. Heidergott, “A CHARACTERISATION OF (MAX, +)-LINEAR QUEUEING SYSTEMS,” 2000. doi: https://doi.org/10.1023/A:1019102429650.
B. de Schutter, “MAX-ALGEBRAIC SYSTEM THEORY FOR DISCRETE EVENT SYSTEMS,” Katholieke Universiteit Leuven, Leuven, 1996. Accessed: Feb. 02, 2024. [Online]. Available: https://www.dcsc.tudelft.nl/~bdeschutter/pub/rep/phd.pdf.
S. Siswanto, “THE EXISTENCE OF SOLUTION OF GENERALIZED EIGENPROBLEM IN INTERVAL MAX-PLUS ALGEBRA,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 17, no. 3, pp. 1341–1346, Sep. 2023, doi: https://doi.org/10.30598/barekengvol17iss3pp1341-1346.
G. Ariyanti, “A NOTE ON THE SOLUTION OF THE CHARACTERISTIC EQUATION OVER THE SYMMETRIZED MAX-PLUS ALGEBRA,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 16, no. 4, pp. 1347–1354, Dec. 2022, doi: https://doi.org/10.30598/barekengvol16iss4pp1347-1354.
A. Abate, A. Cimatti, A. Micheli, and M. Syifa’ul Mufid, “COMPUTATION OF THE TRANSIENT IN MAX-PLUS LINEAR SYSTEMS VIA SMT-SOLVING.” [Online]. Available: https://es.fbk.eu/people/amicheli/resources/formats20/.
E. Altman and D. Fiems, “BRANCHING PROCESSES, THE MAX-PLUS ALGEBRA AND NETWORK CALCULUS.” doi: https://doi.org/10.1007/978-3-642-30782-9_18.
G. Espindola-Winck, L. Hardouin, M. Lhommeau, and R. Santos-Mendes, “CRITERIA STOCHASTIC FILTERING OF MAX-PLUS DISCRETE EVENT SYSTEMS WITH BOUNDED RANDOM VARIABLES,” in IFAC-PapersOnLine, Elsevier B.V., Nov. 2022, pp. 13–18. doi: https://doi.org/10.1016/j.ifacol.2023.01.041.
D. Systemes, “SCILAB,” Apr. 01, 2015, Scilab Enterprises, France: 5.5.2. Accessed: Oct. 09, 2024. [Online]. Available: https://www.scilab.org/news/scilab-552-release
S. Subiono, D. Adzkiya, and K. Fahim, “TOOLBOX ALJABAR MAX-PLUS DAN PETRINET,” 2016, Departemen Matematika, Institut Teknologi Sepuluh Nopember, Surabaya: MAXPLUSV04032016. Accessed: Oct. 23, 2024. [Online]. Available: http://koncomatematika.blogspot.com/2016/05/cara-menginstall-toolbox-max-plus-scilab.html
A. E. S. H. Maharani and A. Suparwanto, “APPLICATION OF SYSTEM MAX-PLUS LINEAR EQUATIONS ON SERIAL MANUFACTURING MACHINE WITH STORAGE UNIT,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 16, no. 2, pp. 525–530, Jun. 2022, doi: https://doi.org/10.30598/barekengvol16iss2pp525-530.
Copyright (c) 2025 Marcellinus Andy Rudhito, Dewa Putu Wiadnyana Putra
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
