DEVELOPMENT OF A COMPUTATIONAL EXPERIMENT FOR THE PARALLELING OF THE MODIFIED BRANCH AND BOUND METHOD FOR THE PROBLEM FOR THE APPOINTMENT OF PROCEDURES TO PATIENTS IN SANATORIUM
Abstract
For the matching problem with vanishing arcs, an optimal algorithm based on the branch and bound method was developed to find the maximum matching in a bipartite graph [1].
The algorithm takes into account the limits of compatibility procedures. The calculated experiment is aimed at proving the feasibility of paralleling of the optimal algorithm for solving the problem of scheduling the reception of medical procedures by patients for use in the sanatoriums of Ukraine.
The experiment was carried out on computing platforms of different configurations with different computing power: a different number of processor cores, different amounts of memory, etc.
Estimated minimum time scheduling, received at the computer platform with the maximum number of PCs is involved. Estimated time scheduling algorithm paralleling by using modifications of the branch and bound method is directly proportional to the number of vertices of a bipartite graph (which is equal to the sum of the number of procedures and the number of patients), the number of assigned procedures and restrictions.Downloads
References
Danilchenko, A. (2012). Optimal algorithm for solving the problem of matching with vanishing arcs. Science news, 6, 46–54.
Lupin, S. A., Milehina, T. V. (2007). The method for solving scheduling problems, focused on cluster computing systems. Proceedings of the universities. Ser. Electronics, 6, 63–69.
Gafarov, E. (2007). Hybrid algorithm for solving the problem of minimization of summarized delay for one device. Information technology, 1, 30–37.
Tymofijeva, N. K., Grycenko, V. I. (2011). Solving the problem of scheduling theory planning by structural alphabet search algorithm and hybrid. Upravliaiushchie sistemy i mashiny, 3, 21–36.
Panishev, A., Danilchenko, A., Danilchenko, A. (2012). The problem of matching with the disappearing "arcs". Simulation and informational technologies, 63, 75–81.
Papadimitriou, C. H., Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 528.
Biro, P., Manlove, D. F., Mittal, S. (2010). Size versus stability in the marriage problem. Theoretical Computer Science, 411 (16-18), 1828–1841. doi: 10.1016/j.tcs.2010.02.003
Mugurel, I. A. (2014). Practical Algorithmic Optimizations for Finding Maximal Matchings in Induced Subgraphs of Grids and Minimum Cost Perfect Matchings in Bipartite Graphs. Theory and Applications of Mathematics & Computer Science, 4 (1), 1–13.
Gelain, M., Pini, M., Rossi, F., Venable, K., Walsh, T. (2013). Local Search Approaches in Stable Matching Problems. Algorithms, 6 (4), 591–617. doi: 10.3390/a6040591
Sonkin, D. M. (2009). Adaptive algorithm of distributing orders for taxi service. Bulletin of the Tomsk Polytechnic University, 315 (5), 65–69.
Li, W., Patrikeev, E. M., Xiao, D. (2015). A DNA Algorithm for the maximal matching problem. Automation and Remote Control, 76 (10), 1797–1802. doi: 10.1134/s0005117915100070
Sergiyenko, A. M., Simonenko, V. P., Simonenko, A. V. (2016). An enhanced scheduling algorithm for task planners in heterogeneous distributed computing systems. System Research and Information Technologies, 2, 20–35. doi: 10.20535/srit.2308-8893.2016.2.03
Matsiy, O. B., Morozov, A. V., Panishev, A. V. (2016). A Recurrent Algorithm to Solve the Weighted Matching Problem. Cybernetics and Systems Analysis, 52 (5), 748–757. doi: 10.1007/s10559-016-9876-4
Copyright (c) 2017 Anna Danylchenko, Svetlana Kravchenko
This work is licensed under a Creative Commons Attribution 4.0 International License.
Our journal abides by the Creative Commons CC BY copyright rights and permissions for open access journals.
Authors, who are published in this journal, agree to the following conditions:
1. The authors reserve the right to authorship of the work and pass the first publication right of this work to the journal under the terms of a Creative Commons CC BY, which allows others to freely distribute the published research with the obligatory reference to the authors of the original work and the first publication of the work in this journal.
2. The authors have the right to conclude separate supplement agreements that relate to non-exclusive work distribution in the form in which it has been published by the journal (for example, to upload the work to the online storage of the journal or publish it as part of a monograph), provided that the reference to the first publication of the work in this journal is included.