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

  • Anna Danylchenko Zhytomyr State Technological University, Ukraine
  • Svetlana Kravchenko Zhytomyr state technological university, Ukraine
Keywords: bipartite graphs, branch and bound method, method of exhaustive search

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

Download data is not yet available.

Author Biographies

Anna Danylchenko, Zhytomyr State Technological University

Department of computer engineering

Svetlana Kravchenko, Zhytomyr state technological university

Department of Software Systems

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


👁 369
⬇ 263
Published
2017-03-23
How to Cite
Danylchenko, A., & Kravchenko, S. (2017). 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. EUREKA: Physics and Engineering, (2), 16-23. https://doi.org/10.21303/2461-4262.2017.00305
Section
Computer Sciences and Mathematics