PARALLELING MODIFIED METHOD OF BRANCH AND BOUND TO SOLVE PROBLEM OF MATCHING CURVES FROM ENDANGERED OR THREATENED

A. Danylchenko

Abstract


Context. The problem of scheduling the passage of procedures of sanatorium patients, which is reduced to the problem of finding an extended maximum matching in a bipartite graph. For the task of matchings with disappearing arcs developed an optimal algorithm of its solution based on branch and bound method. The algorithm takes into account the limits of compatibility procedures. Spend the current experiment based on the evidence of the feasibility of algorithm parallelization for solving the problem of optimal scheduling patients receiving therapeutic treatments applied to its use in the health institutions of Ukraine.

Objective. To prove the feasibility of the algorithm parallelization optimal solution of our problem.

Method. A mathematical model of the problem of matchings with disappearing arcs. Selected computing platforms of different configurations with a variety of computing power: a different number of processor cores, different amounts of memory, etc. Written copyright software for the experiment. The program consists of two modules: a server module, which controls the process of performing calculations and client module that runs on the PC are separated for the purpose of calculating the parallel operations. The experiment was conducted on the basis of sanatorium “Denyshi”. Computational experiments for optimal algorithm parallelization for solving the problem of matchings with disappearing arcs. Computer experiment carried out on a series of random conditions of the problem generated by the program. The analysis of the results by comparing the time solving the problem of matchings with disappearing arcs optimal algorithm on different computing platforms.

Results. The modified method of branches and borders shows the stability of reducing the time of scheduling transmission procedures with increasing computing power.

Conclusions. Estimated minimum time scheduling, received at the computer platform with the maximum number of PCs involved. Estimated time scheduling algorithm parallelization by using modifications of the branch and bound 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.

Keywords


Matching; bipartite graphs; branch and bound method; the method of exhaustive search; parallelization.

References


Danil’chenko A. O., Danil’chenko A. O., brag m S. A. Rozv’yazannya odnogo klasu zadach skladannya rozklad v genetichnimi algoritmami na klasternikh sistemakh, V snik ZH T , 2004, No. 4, pp. 130–135.

Danil’chenko A. O., Pan shev A. V., Danil’chenko A. M. Zadacha pro parospoluchennya z «znikayuchimi» dugami, Zb rnik naukovikh prats’ «Modelyuvannya ta nformats yn tekhnolog », 2012, No. 63, pp. 75–81.

Lupin S.. The method for solving scheduling problems, focused on cluster computing systems, Proceedings of the universities. Ser. Electronics: scientific-technical, 2007, 6, pp. 63–69.

Papadimitriu KH., Staglits K. Kombinatornaya optimizatsiya. Algoritmy i slozhnost’. Moscow, Mir, 1985, 512 p.

Zholobov D. A. Vvedeniye v matematicheskoye programmirovaniye: uchebnoye posobiye. Moscow, MIFI, 2008, 376 p.

Ageev A. Approximate algorithm for solving the problem of metric peripatetic salesman with an estimate of the accuracy.Discrete Analysis and Operations Research. Series 1: Siberian Branch of the Russian Academy of Sciences. Institute of Mathematics. Siberian Branch of the Russian Academy of Sciences. 2009, 4, pp. 3–20.

Li Wenxia Patrikeev E., Dongmei Xiao A DNA Algorithm for the Maximal Matching Problem, Automatics and robot, 2015, No. 10, pp. 106–112.

Sonkin D. Adaptive algorithm of distributing orders for taxi service, The Tomsk Polytechnic University, 2009, No. 5, pp. 65–69.


GOST Style Citations


1. Danil’chenko A. O., Danil’chenko A. O., brag m S. A. Rozv’yazannya odnogo klasu zadach skladannya rozklad v genetichnimi algoritmami na klasternikh sistemakh, V snik ZH T , 2004, No. 4, pp. 130–135.

2. Danil’chenko A. O., Pan shev A. V., Danil’chenko A. M. Zadacha pro parospoluchennya z «znikayuchimi» dugami, Zb rnik naukovikh prats’ «Modelyuvannya ta nformats yn tekhnolog », 2012, No. 63, pp. 75–81.

3. Lupin S.. The method for solving scheduling problems, focused on cluster computing systems, Proceedings of the universities. Ser. Electronics: scientific-technical, 2007, 6, pp. 63–69.

4. Papadimitriu KH., Staglits K. Kombinatornaya optimizatsiya. Algoritmy i slozhnost’. Moscow, Mir, 1985, 512 p.

5. Zholobov D. A. Vvedeniye v matematicheskoye programmirovaniye: uchebnoye posobiye. Moscow, MIFI, 2008, 376p.

6. Ageev A. Approximate algorithm for solving the problem of metric peripatetic salesman with an estimate of the accuracy.Discrete Analysis and Operations Research. Series 1: Siberian Branch of the Russian Academy of Sciences. Institute of Mathematics. Siberian Branch of the Russian Academy of Sciences. 2009, 4, pp. 3–20.

7. Li Wenxia Patrikeev E., Dongmei Xiao A DNA Algorithm for the Maximal Matching Problem, Automatics and robot, 2015, No. 10, pp. 106–112.

8. Sonkin D. Adaptive algorithm of distributing orders for taxi service, The Tomsk Polytechnic University, 2009, No. 5, pp. 65–69.




DOI: https://doi.org/10.15588/1607-3274-2017-3-12



Copyright (c) 2017 A. Danylchenko

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.