JP4728407B2 - Matching system - Google Patents

Description

  The present invention relates to a matching system, and more particularly, to a matching system for determining a combination based on bidirectional desires.

  For example, a method for matching in a matching problem between sets having priority in both directions, such as a matching problem between a set of job applicants and a set of companies that accept applicants, is being proposed (for example, Non-patent document 1).

  Here, it is assumed that each applicant has a priority list in which the companies he / she wants to find employment are ranked according to his / her preference, while each company also has a priority list in which applicants who want to accept are ranked. The priority list ROL (a) of the applicant a is a subset of the set of companies, and is a total ordered set ordered by inequality signs that do not include equal signs by rank. Here, if the applicant a prefers p over p ′, p <p ′ is written (specifically, p is first in priority and p ′ is third in priority) In this case, p (= 1) <p ′ (= 3).) The same applies to the priority list ROL (p) for applicants of company p. Each company also has a recruitment frame (capacity) for accepting applicants. The capacity Q (p) of the company p is an integer of 0 or more. The matching X is a set composed of a pair (a, p) of a candidate and a company, and satisfies the following two conditions.

1. For any volunteer a, there are no more than one pair (a, p) containing a in X.
2. For an arbitrary company p, a pair (a, p) including p is equal to or less than Q (p) company capacity in X.

  An example of matching is shown in FIG. In FIG. 17, as a match between the set of applicants {a1, a2, a3, a4, a5, a6, a7} and the set of companies {p1, p2, p3, p4}, {(a1, p1), ( a2, p3), (a3, p4), (a5, p3), (a6, p4)}. In this matching, applicants a4 and a7 and company p2 have no matching partner.

  FIG. 18 shows an example of a priority list of applicants and companies. In each priority list, the more preferable ones are shown in the above list. In other words, the ranking increases as you go down. In the example of FIG. 18, the applicants place an order of p1 <p4 <p3 for the three companies. The company places the order of a7 <a1 <a4 <a3 <a5 <a6 among the six applicants. Opponents who do not want to match at all are not listed in the priority list.

  The matching problem refers to a problem of finding a combination between a candidate and a company when a set of applicants, a group of companies, and a priority list of applicants and companies are given. The matching method is a solution to the matching problem, that is, a method for obtaining a combination between a candidate and a company. Therefore, the matching system is a system that executes a matching method.

  Moreover, stability can be defined for the above matching. The matching X is stable when the following two conditions are both satisfied.

1. All applicants (businesses) will only match the companies (applications) on their priority list.
2. Of all pairs (a, p) of the applicant and the company, none of them is included in the matching X is a blocking pair. Here, the blocking pair satisfies both of the following three conditions.
2.0. a is described in the priority list of p, and p is described in the priority list of a.
2.1. In X, a does not match any company, or in X, a matches p ′, and p <p ′ holds in the priority list of a.
2.2. The number of applicants matching p in X is less than the capacity Q (p), or there is a candidate a ′ that matches p in X, and a <a ′ in the priority list of p Holds.

  In the matching problem, a method for generating a stable matching is required. When unstable matching is obtained, there is a candidate or company that matches with a partner that is not listed in the priority list, that is, a partner that is not desired at all, or there is a blocking pair. Unstable matching is not fair because both the candidate and the company making up the blocking pair are more likely to have a blocking pair partner than the obtained matching. In other words, the method for generating unstable matching loses the reliability for matching, and impairs the intention of the matching target person to participate in the matching.

  FIG. 19 is a flowchart showing a conventional matching method using the Gale-Shapley algorithm described in Non-Patent Document 1. The feature is that all applicants make proposals in order, starting with the company with the lowest ranking in their priority list (ie, the first choice).

  Before the description of FIG. 19, the outline will be briefly described with reference to FIG. The example in FIG. 20 assumes a matching problem between a set of four hospitals and a set of eight applicants who wish to find employment in those hospitals. All applicants, from Akashi to Kudo, make proposals in order, starting with the company with the lowest ranking in their priority list.

Mr. Akashi first proposed to Futagawa Hospital. First, Mr. Akashi proposed to Futagawa Hospital. In both hospitals, Akashi is fourth in the priority list, so (Akashi, Futagawa Hospital) is provisionally matched.
Next, Mr. Inoue makes a proposal. In Mr. Inoue's priority list, since the first hope is Futagawa Hospital, Mr. Inoue proposes to Futagawa Hospital. At Futagawa Hospital, Ms. Inoue is fifth in the priority list, and there are two Futagawa Hospitals available for one person, so (Inoue, Futagawa Hospital) is provisionally matched.
Next, Ueno-san makes a proposal. In Mr. Ueno's priority list, the first hope is Futagawa Hospital, so Mr. Ueno proposes to Futagawa Hospital. At Futagawa Hospital, Mr. Ueno is 6th in the priority list, and there is no available space in Futagawa Hospital, so he proposes to the second desired hospital in the priority list. In Uchiyama Hospital, the second choice, Ueno is ranked first, so (Ueno, Ichiyama Hospital) is provisionally matched.

Next, Mr. Eguchi proposes to Ichiyama Hospital in the first hope, but because Mr. Eguchi is not in the priority list of Ichiyama Hospital, it is rejected and proposed to Futagawa Hospital in the second hope. Because it is 7th in the priority list of Futagawa Hospital and there is no capacity, it will be rejected and proposed to the 3rd hope Mimura Hospital. Are provisionally matched.
Next, Mr. Okawa proposes to the first hope of Futagawa Hospital. Okawa is third in the Futagawa Hospital's priority list. The capacity is two people, and two people have already been provisionally matched. However, provisionally matched are Mr. Akashi 4th in the priority list and Mr. Inoue 5th. For this reason, Mr. Inoue with the highest ranking is excluded, and (Okawa, Futagawa Hospital) is provisionally matched.
Excluded, Inoue-san proposes again to the hospital with the lowest ranking in his priority list after Futagawa Hospital. The hospital is Ilsan Hospital. However, it is rejected because Mr. Inoue's name is not in the priority list of Ilsan Hospital. Mr. Inoue has been rejected by all hospitals because only the second preference is registered in Mr. Inoue's priority list.

Next, Mr. Kawaguchi's processing is performed. In Kawaguchi's priority list, since the first hope is Futagawa Hospital, Mr. Kawaguchi proposes to Futagawa Hospital. At Futagawa Hospital, Mr. Kawaguchi is 8th in the priority list, and because there are no vacancies in Futagawa Hospital, he proposes to the second desired hospital in the priority list. In the priority list of the second choice Mimura Hospital, Kawaguchi-san is not named, so it is rejected. Similarly, at the third hope Ichiyama Hospital, the fourth choice Yotsuya Hospital has the name in the 6th place in the priority list, so (Kawaguchi, Yotsuya Hospital) is provisionally matched.
Next, Kimura proposes to Futagawa Hospital, the first hope. Mr. Kimura is first in the Futagawa Hospital priority list. The capacity is two people, and two people have already been provisionally matched. However, it is temporarily matched that Mr. Akashi 4th in the priority list and Mr. Okawa 3rd. For this reason, Mr. Akashi, who has the highest ranking, is excluded and (Kimura, Futagawa Hospital) is provisionally matched.

Excluded, Akashi-san re-proposes to the hospital with the lowest ranking in his priority list next to Futagawa Hospital, but only the first desired Futagawa Hospital is registered in Akashi-san's priority list. As a result, Akashi was rejected by all hospitals.
Next, Mr. Kudo proposes to Yotsuya Hospital, the first hope. In the priority list of Yotsuya Hospital, Kudo is fifth. There are two people, and one person has already been provisionally matched, but there is one room available. Therefore, (Kudo, Yotsuya Hospital) is provisionally matched.

Here, since all applicants are provisionally matched with one of the hospitals or rejected from all the hospitals listed in their own priority list, the processing ends.
Matching results are (Okawa, Futagawa Hospital), (Kimura, Futagawa Hospital), (Ueno, Ichiyama Hospital), (Eguchi, Mimura Hospital), (Kawaguchi, Yotsuya Hospital), (Kudo, Yotsuya Hospital) As a result, Akashi and Inoue were rejected by all hospitals listed on their priority list.

  This processing performed by taking FIG. 20 as an example will be described using the flowchart of FIG. In step S100, provisional matching is made an empty set in advance. In step S101, if there is no unprocessed applicant, the process ends. If there is, the following process is performed for one of the applicants a. In step S102, the index a. Indicates which number of companies in the priority list ROL (a) the applicant a proposes to a. Set i to 1. This indicates that all applicants, in turn, first propose to the company with the lowest ranking in their priority list. In step S103, the number of elements in the priority list ROL (a) is a. If it is smaller than i, the candidate a has finally failed to match any company, and the process returns to step S101. On the other hand, in step S103, the number of elements in the priority list ROL (a) is a. If it is not smaller than i, in step S104, a. Let the i-th company be p. If a is not included in the priority list ROL (p) of p in step S105, a. i to a. The setting is reset to i + 1, and the process returns to step S103. This is because the proposed company p rejects the proposed applicant a unless it is listed in the ROL (p), and the rejected applicant a has a ranking in the company's priority list ROL (a). This is equivalent to re-proposing to the next smaller company. On the other hand, if a is included in the priority list ROL (p) of p in step S105, in step S106, the number of applicants whose p is temporarily matched at that time must be less than the capacity Q (p). For example, the pair (a, p) is added to the provisional matching, and the process returns to step S101. On the other hand, in step S106, if the number of applicants for which p is provisionally matched at that time is not less than the capacity Q (p), in step S107, among the candidates who are provisionally matched with p, The priority list ROL (p) having the highest rank is defined as a1. The ranking in ROL (p) is compared between a1 and the proposal candidate a. If the rank of a is higher, a. i to a. The setting is reset to i + 1, and the process returns to step S103. This corresponds to the company p rejecting a if the rank of a is higher. The rejected applicant a will propose again to the company with the lowest rank in his priority list ROL (a) next to p. After this step S107, the number of applicants temporarily matching with the company p is equal to the capacity Q (p). In step S108, since the rank of a1 is higher than the rank of a, the pair (a, p) is added to the temporary matching, the pair (a1, p) is excluded from the temporary matching, and a is reset to a1. In step S109, a. i to a. The setting is reset to i + 1, and the process returns to step S103. In other words, the candidate (original a1) excluded from the provisional matching proposes again to the company with the lowest rank in his priority list next to p. The process of FIG. 19 ends when all applicants are provisionally matched with any company or rejected from all companies listed in their priority list in step S101. is there. The provisional matching finally obtained at the stage when the processing of FIG. Note that Non-Patent Document 1 describes that matching obtained by the Gale-Shapley algorithm is stable.

“The Stable Marriage Problem”, D.M. Gusfield and R.W. W. Irving, The MIT Press, 1989, p. 9

As described above, in a conventional matching system, a one-to-one combination such as a candidate and a company is obtained by the well-established Gale-Shapley algorithm when a stable matching result is obtained.
However, when a plurality of companies form a group and the group has a capacity requirement, matching cannot be performed in consideration of the group capacity requirement. For example, although the hospitals described in FIG. 20 each have a capacity, when a plurality of hospitals constitute a group and the group has a group capacity, the above matching system uses the group. There was a problem that it was impossible to perform stable matching by incorporating the quorum into the algorithm. Specifically, when the total capacity of multiple hospitals exceeds the group capacity, prioritization between multiple hospitals is not performed, and stable matching cannot be performed.

  The present invention has been made to solve such a problem, and obtains a matching system that performs maximum stable matching in consideration of the number of companies and the number of groups in the group including the company. It is an object.

  The present invention is a matching system for matching elements of a set A composed of a plurality of elements and a set B composed of a plurality of elements, wherein each element of the set B belongs to one or more groups For each B element ID of each element of the set B, a quorum file storing the quorum acceptable for matching and a group ID indicating a specific group of the set B A group capacity condition file storing element IDs and the number of group members, and the A element ID of each element of the set A are uniquely ranked for all or part of the elements of the set B. The first priority list file storing one priority list and the B element ID of each element of the set B are uniquely assigned to all or part of the elements of the set A. The second priority list file storing the attached second priority list and the group capacity number stored in the group capacity condition file are referred to. Based on this group capacity number, B belonging to the group A capacity processing unit that calculates an optimized capacity of an element ID, associates the calculated optimized capacity with a B element ID, and stores it in an optimized capacity information file; the first priority list file; the second Matching processing means for performing a matching process on the elements of the set A to any element of the set B based on the number of optimized capacity stored in the priority list file and the optimized capacity information file Is a matching system.

  The capacity processing means instructs the matching processing means to perform matching processing based on constants stored in the first priority list file, the second priority list file, and the constant file, and the matching processing means Stores the matching result as a temporary match result in the storage means, and for each group ID in the group capacity condition file, if it is determined that the group capacity is greater than or equal to the total number of capacity of each B element in the group, The number of each B element is stored in the optimized capacity information file as an optimized capacity in association with the B element ID, while the group capacity is determined to be smaller than the total number of B elements in the group. When referring to the temporary match result, the number of temporary matches for each B element and the total number of temporary matches for each B element in the group are calculated. The optimized number of B element IDs is set based on the ratio of the number of temporary matches of each B element to the total number of temporary matches of the B elements, and the number of the above group capacity. May be stored in the optimized capacity information file in association with the B element ID.

  The capacity processing means optimizes the capacity of each B element when the group capacity is determined to be greater than or equal to the total number of B elements in the group for each group ID in the group capacity condition file. When the number of groups is determined to be smaller than the total number of B elements in the group, the total number of B elements in the group is stored. The optimized number of B element IDs is set based on the ratio of the number of each B element to the value multiplied by the group capacity, and this optimized number is optimally associated with the B element ID. You may memorize | store in a chemical capacity information file.

  The present invention is a matching system for matching elements of a set A composed of a plurality of elements and a set B composed of a plurality of elements, wherein each element of the set B belongs to one or more groups For each B element ID of each element of the set B, a quorum file storing the quorum acceptable for matching and a group ID indicating a specific group of the set B A group capacity condition file storing element IDs and the number of group members, and the A element ID of each element of the set A are uniquely ranked for all or part of the elements of the set B. The first priority list file storing one priority list and the B element ID of each element of the set B are uniquely assigned to all or part of the elements of the set A. The second priority list file storing the attached second priority list and the group capacity number stored in the group capacity condition file are referred to. Based on this group capacity number, B belonging to the group A capacity processing unit that calculates an optimized capacity of an element ID, associates the calculated optimized capacity with a B element ID, and stores it in an optimized capacity information file; the first priority list file; the second Matching processing means for performing a matching process on the elements of the set A to any element of the set B based on the number of optimized capacity stored in the priority list file and the optimized capacity information file As a matching system with the above, the maximum stable matching is performed while taking into account the number of companies and the number of groups in the group that includes the company. , It is possible to obtain a matching system.

It is the block diagram which showed the structure of the whole matching system which concerns on Embodiment 1 of this invention. It is the block diagram which showed the internal structure of each component which comprises the matching system which concerns on Embodiment 1 of this invention. It is the flowchart which showed the flow of the process of the matching system which concerns on Embodiment 1 of this invention. It is the flowchart which showed the flow of the process of the matching system which concerns on Embodiment 1 of this invention. It is the flowchart which showed the flow of the process of the matching system which concerns on Embodiment 1 of this invention. It is the flowchart which showed the flow of the process of the matching system which concerns on Embodiment 1 of this invention. It is the flowchart which showed the flow of the process of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the facility program information file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the group capacity condition file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the participant ROL file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the facility ROL file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the matching result storage file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the optimization capacity | capacitance information file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed the specific example of the flow of a process of the matching system which concerns on Embodiment 1 of this invention. It is the flowchart which showed the flow of the process of the matching system which concerns on Embodiment 2 of this invention. It is explanatory drawing which showed the specific example of the flow of a process of the matching system which concerns on Embodiment 2 of this invention. It is explanatory drawing which showed an example of the matching in the conventional matching method. It is explanatory drawing which showed an example of the priority list | wrist in the conventional matching method. It is the flowchart which showed the flow of the process of the conventional matching method. It is explanatory drawing which showed the conventional matching method.

Embodiment 1 FIG.
The matching system according to the first embodiment of the present invention is a system for determining a combination of 1 to M (M ≧ 1). For example, for example, a graduate of a medical school who wishes to undergo training (hereinafter referred to as a participant) has one or more medical training facilities (that is, a university hospital, a general hospital, etc.) It is necessary to experience training at the facility.

Each facility (hospital) has a capacity condition (capacity), but a plurality of facilities may form one group, and the group may have a capacity condition (group capacity). The present embodiment is characterized in that stable matching is obtained even when the total capacity of a plurality of facilities exceeds the group capacity.
Groups are classified under specific conditions. As an example of a group, the location of a facility is a group by prefecture, or a region that includes a prefecture (Hokkaido, Tohoku, Kanto, Shinetsu, etc.) Group. In addition, training contents include groups for each department (general medicine, cardiovascular medicine, cardiac surgery, pediatrics, women's medical care, etc.). Good.
In the present embodiment, it is assumed that one facility belongs to one group and one facility does not belong to a plurality of groups.
In addition, when the group has a capacity requirement, for example, when a group is formed in a prefecture, there is an effect that an appropriate person can be matched to a prefecture where the number of persons is insufficient. When a group is composed of clinical departments, there is an effect of eliminating the bias for each clinical department, or securing a certain number of departments with a shortage of personnel.

  FIG. 1 is a diagram showing an overall configuration of a matching system according to Embodiment 1 of the present invention. As shown in FIG. 1, the matching system according to the first embodiment includes a matching server 100 for performing a matching process for determining a combination of a participant and a facility, and a matching management for performing management and maintenance of the matching server 100, etc. A participant terminal 400, a participant terminal 200 that is operated by a participant to input a desired rank of the facility, and a facility manager working at the facility to input a desired rank of the participant The facility manager terminal 300 of FIG. The matching server 100, the participant terminal 200, the facility manager terminal 300, and the matching manager terminal 400 are connected by a communication network 500 such as the Internet.

  FIG. 2 is a diagram showing an internal configuration of each component shown in FIG. As shown in FIG. 2, in the matching server 100, a facility information file (capacity file) 1, a group capacity condition file 2, a participant ROL file (first priority list file) 3, and a facility ROL Six files of a file (second priority list file) 4, a matching result storage file 5, and an optimized capacity information file 10 are stored. These may be stored in one common storage device, or may be stored in a plurality of storage devices. Further, in the matching server 100, a communication means 6 for performing communication with the outside via the communication network 500, a ROL creation means 7 for creating a ROL file, and a capacity processing means 8 for performing processing related to the capacity. And a matching means 9 are provided.

  FIG. 8 is a diagram showing an example of the facility information file 1. The facility information file 1 stores information on each facility that conducts training. That is, the facility information file 1 includes, for example, a facility code, which is an ID for identifying each facility, and information such as a facility name, the number of persons (number of participants that can be accepted), and a facility address (location of the facility). Stored.

  FIG. 9 is a diagram showing an example of the group capacity condition file 2. The group capacity condition file 2 stores a group code which is an ID for identifying a group, a group facility code indicating a facility code of a facility belonging to the group, and information on the number of groups.

  FIG. 10 is a diagram showing an example of the participant ROL file 3. The participant ROL file 3 stores a list in which the facilities desired by each user are arranged in the desired order for each user ID. In FIG. 10, the facilities from the first desire to the nth desire are stored in order for each user. Each user obtains information on each facility from, for example, a homepage on the Internet and determines a desired order. Note that all the facilities may be registered in the participant ROL file 3 or some of the facilities may be registered.

  FIG. 11 is a diagram showing an example of the facility ROL file 4. The facility ROL file 4 stores a list in which participants desired by each facility are arranged in the desired order for each facility code. In FIG. 11, the participants from the first desire to the nth desire are sequentially stored for each facility. Each facility, for example, interviews participants and obtains information on the participants, and determines a desired order. Note that all the participants may be registered in the facility ROL file 4 or some of the participants may be registered.

FIG. 12 is a diagram showing an example of the matching result storage file 5. The matching result storage file 5 stores the matching results obtained as a result of the matching process. That is, as shown in FIG. 12, the user ID and the facility code of the assigned facility are stored in association with each other. Thereby, it is possible to confirm which participant performs training at which facility.
FIG. 13 is a diagram showing an example of the optimized capacity information file 10. The optimized capacity information file 10 is output by the capacity processing means 8 and is used when the matching means 9 performs matching processing, and stores the optimized capacity number for each facility code.
In the file structure shown in FIGS. 8 to 13, one line in the line direction (horizontal direction) is called a record.

Returning to the description of FIG. As shown in FIG. 2, an input unit 20, a display unit 21, a processing unit 22, and a communication unit 23 are provided in the participant terminal 200.
In addition, since the internal structure of the facility manager terminal 300 is the same as that of the participant terminal 200, description is abbreviate | omitted here.

  In the matching manager terminal 400, an input unit 30, a display unit 31, a processing unit 32, and a communication unit 33 are provided.

  Next, the operation of the matching system according to the first embodiment will be described. FIG. 3 is a diagram showing data input processing from the matching manager terminal 400, when the matching manager performs registration, addition, update or deletion processing of the facility information file 1 or the group capacity condition file 2. The flow of processing is shown. As shown in FIG. 3, first, the processing means 32 of the matching manager terminal 400 delivers the input data received by the input means 30 to the communication means 33 by the operation of the matching manager (step S1). Next, the communication means 33 of the matching manager terminal 400 transmits the input data to the communication means 6 of the matching server 100 (step S2). Next, the communication means 6 of the matching server 100 adds, updates, or deletes data in the facility information file 1 or the group capacity condition file 2 according to the received data content (step S3).

FIG. 4 is a diagram showing data input processing from the participant terminal 200, and shows a flow of processing when the participant inputs a priority list (ROL file) indicating a desired order. As shown in FIG. 4, first, the processing means 22 of the participant terminal 200 delivers the input data received by the input means 20 to the communication means 23 by the participant's operation (step S11). Next, the communication means 23 of the participant terminal 200 transmits the input data to the communication means 6 of the matching server 100 (step S12). Next, the communication unit 6 of the matching server 100 passes the received data content to the ROL creation unit 7, and the ROL creation unit 7 adds, updates, or deletes data in the participant ROL file 3. That is, one or more records storing the user ID, facility code, and rank corresponding to the corresponding user ID are overwritten on the participant ROL file 3 (step S13).
In addition, when receiving data input from the facility manager terminal 300 to the facility ROL file 4, the flow is the same as the flowchart shown in FIG. Note that the process of adding, updating, and deleting data to the facility information file 1, the group capacity condition file 2, the participant ROL file 3, and the facility ROL file 4 can also be performed from the matching manager terminal 400. In this case, each data is transferred to the administrator in a file format by some storage medium, and the administrator performs a file update operation collectively from the matching administrator terminal 400.

  FIG. 5 is a diagram showing a group setting number optimization process by the capacity processing unit 8 of the matching server 100 and a matching process by the matching unit 9. As shown in FIG. 5, the capacity processing unit 8 of the matching server 100 performs the optimization process for the number of facilities in the group for each group, and delivers the optimized number of capacity optimized for each group to the matching unit 9. (Step S21). As will be described later, the optimization processing in step S21 includes provisional matching processing by the matching means 9. After that, the matching means 9 performs matching processing using the Gale-Shapley algorithm shown in FIG. 19 described above for all facilities and all participants of all groups using the delivered optimized capacity. The obtained matching result is stored in the matching result storage file 5 (step S22).

  FIG. 6 is a diagram showing the details of the process for optimizing the capacity of the facilities in the group shown in step S21 of FIG. As shown in FIG. 6, the capacity processing unit 8 instructs the matching unit 9 to perform matching processing based on the number of people stored in the current participant ROL file 3, the facility ROL file 4, and the facility information file 1. Performs matching processing according to the Gale-Shapley algorithm for all facilities and all participants of all groups, and temporarily stores the match results in the storage means. This match result is referred to as a temporary match result for convenience (step S31).

The capacity processing means 8 of the matching server 100 sets a variable representing a group code as n, sets 1 to an initial value of n, and then refers to a group code item in the group capacity condition file 2 to register a group registered in advance. The maximum code value is stored (step S32). The group code shown in FIG. 9 includes a character string instead of a number, but here, each group code uniquely corresponds to a different value of n. For example, the group code G01 corresponds to n = 1, and the group code G02 corresponds to n = 2. As an example of a method for realizing this, the group capacity condition file may store a group number representing a corresponding value of n in association with each group code.
Next, the capacity processing means 8 confirms whether or not the current group code is larger than the maximum value of the stored group code (step S33), and ends the process if the current group code is larger than the maximum value. To do.

  If the current group code is less than or equal to the maximum value, the process moves to step S34, and group facility code information belonging to the corresponding group code is obtained by referring to the group capacity condition file 2, and the capacity of each facility code The number is obtained by referring to the facility information file 1. Then, the total number of facilities of facilities belonging to the group is calculated, and the group capacity number of the current group code is compared with the total number of facilities of facilities belonging to the group (step S34).

  When the group capacity is equal to or greater than the total number of facilities in the group in the comparison in step S34, the optimized capacity information is associated with the facility code with each capacity number of the corresponding facility code as the optimized capacity number. Store in the file 10 (step S36). Thereafter, the group code is incremented by 1 (step S37), and the process returns to step S33.

  If it is determined in step S34 that the group capacity is smaller than the total number of facilities in the group, the process proceeds to step S35. In the process of step S35, the capacity processing means 8 refers to the temporary match result, and extracts the records in which the facility code is included in the group facility code of the current group code from the records included in the temporary match result. Calculate the number of temporary matches for the facility and the total number of temporary matches for all facilities in the group (where the number of temporary matches means the number of participants matched to the facility in the temporary match result, The total number means the sum of the number of participants matched to each facility code included in the group in the temporary match result).

After that, for each facility, a number obtained by multiplying the ratio of the number of temporary matches of the facility with respect to the total number of temporary matches of all facilities in the group by the number of group capacity is set as the optimized capacity number of the corresponding facility code. In addition, when the number calculated | required in this way does not become an integer, you may set so that the optimization capacity | capacitance number may become an integer by rounding off based on the number. In addition, the optimized capacity cannot exceed the capacity of the facility. For this reason, before setting as the optimized capacity number, a comparison is made with the capacity number of each facility, and when the optimized capacity number is larger than the capacity number, correction processing is performed to replace the optimized capacity number with the capacity number. By this correction process, the optimization capacity number of the facilities in the group is readjusted and replaced. This process is called “optimization capacity adjustment process” for convenience and will be described later.
The set optimization capacity is stored in the optimization capacity information file 10 in association with each facility code (step S35). Thereafter, the process proceeds to step S37.

  The optimization capacity adjustment process described above will be described. When the calculated optimization capacity of a facility code is larger than the capacity of the facility code, the corresponding optimization capacity is replaced with the capacity of the facility code. As a result, the total number of optimized capacity is less than the group capacity by the numerical value of the difference between the optimized capacity and the capacity (assumed as numeric value a), so either facility for numeric value a. It may be added to the code optimization capacity (the total optimization capacity may be the same as the group capacity). For example, how to add the numerical value a is calculated for each facility code in the group, and the numerical value a is added to the optimized capacity number of the facility code with the largest difference. It is conceivable that the numerical value “a” is distributed to a certain number in order from the facility code having the largest difference and added.

In the calculation of step S35, the “minimum number of people” is set as the optimized number of people, and when the calculation result of the calculation formula becomes smaller than “the minimum number of people”, the optimized number of people is set to the minimum number of people. Can be configured. For example, assuming that the minimum number of people is two, if the number of optimized capacity is smaller than 2 as a result of the calculation, the number of optimized capacity is recalculated as two. This process is referred to as “minimum capacity correction process” for convenience.
As a result of performing the minimum capacity correction process, there is a possibility that the total number of optimized capacity of facilities in the group may exceed the group capacity. When the total number of optimized capacity is not allowed to exceed the group capacity, the number of optimized capacity for each facility code is subtracted by a fixed value (for example, 1) in descending order of optimized capacity. This method is repeated until the total number of optimized capacity is less than or equal to the group capacity, or the facility code that is subject to the minimum capacity correction process. A method of subtracting the number of qualified members by a certain value (for example, by 1) and repeating this until the total value of the number of optimized members is equal to or less than the number of group members is conceivable. Alternatively, when storing group facility codes in the group capacity condition file 2, priority levels are associated with each group code and stored in descending order of priority, and the number of optimized capacity is fixed in order from the lowest priority facility code. A method of subtracting a number is also conceivable.
However, no matter which method is used, the optimized capacity for any facility code should not be less than the “minimum number of people”, and the subtraction will be subtracted from the number of people that has been found to be below the “minimum number of people”. First, it will be subtracted from the capacity number of the target facility code.
Further, as a result of performing the minimum capacity correction process, when the total value of the optimized capacity exceeds the group capacity, it may be allowed to exceed the group capacity, and the optimization capacity may not be corrected.

The process of steps S34 to S35 will be described using a specific example. FIG. 14 shows examples 1 and 2 as specific examples. Example 1 exemplifies the case where the optimized capacity is calculated for the group code G01. The group code G01 has a group capacity of 25 people, and the group facility codes registered as a group are A001, A003, A010, and A011. Further, as shown in FIG. 14, the capacity number of each facility code is 10, 8, 10, 7 from the top, and the total number of capacity numbers is 35 persons. In the process of step S34 of FIG. 6, when the group capacity is compared with the total capacity of the facilities in the group, the group capacity is smaller than the total capacity, so that the temporary match result is obtained by the process of step S35. Referring to the group facility code, the provisional match number is obtained. It is assumed that the number of provisional match results is 4, 6, 8, and 5 from the top as shown in FIG. Thereafter, the optimized capacity is calculated. The calculation formula is obtained by multiplying the ratio of the number of temporary matches of each facility to the total number of temporary matches of all facilities in the group by the number of groups, and the facility code A001. In this case, 4 (the number of temporary matches of A001) / 23 (total number of temporary matches) × 25 (the number of groups). As a result, in the case of the facility code A001, the optimized capacity is calculated as 4 persons, and the optimized capacity of each facility code is 4, 7, 9, 5 from the top. This optimization capacity is calculated by rounding off, but if the total optimization capacity is allowed to be larger or smaller than the group capacity, it can be calculated by rounding up or down. Good.
By such a calculation method, it is possible to allocate the group capacity to the facilities in the group as the optimized capacity, reflecting the result of the temporary match that has been performed once.

Example 2 in FIG. 14 illustrates the case where the optimized capacity is calculated for the group code G02. The group code G02 has a group capacity of 23 people, and the group facility codes registered as a group are A012, A015, A016, A017, and A018. As shown in FIG. 14, the capacity number of each facility code is 3, 5, 4, 7, 3 from the top, and the total number of capacity is 22 persons. In the process of step S34 in FIG. 6, when the group capacity is compared with the total capacity value of the facilities in the group, the group capacity is larger than the total capacity value. Is not performed, and the capacity number of each facility code becomes the optimized capacity number as it is.
In the specific example shown in FIG. 14, the optimization quorum adjustment process and the minimum quorum correction process are unnecessary, but the process is performed by the method described above as necessary.

  FIG. 7 is a diagram illustrating the process of notifying the matching result by the communication unit 6 of the matching server 100. As shown in FIG. 7, the matching means 9 of the matching server 100 first notifies the communication means 6 of the end of the matching process (step S51). Next, the communication unit 6 of the matching server 100 refers to the matching result storage file 5 and notifies the matching result to the communication unit 33 of the matching manager terminal 400 (step S52). Next, the communication means 33 of the matching manager terminal 400 delivers the notified matching result to the processing means 32 (step S53). Next, the processing means 32 of the matching manager terminal 400 publishes the transferred matching result on the Internet or the like (step S54).

  The disclosure of the matching result is not limited to the method shown in FIG. 7, and there is a method of notifying the participants and the facility manager using a file format and paper on which the result is printed. The matching result may be notified to the participant terminal 200 or the facility manager terminal 300. For example, if the participant terminal 200 is logged in with the user ID 001, the facility information matched with the user ID 001 (for example, information regarding the facility code A001) may be transmitted to the participant terminal 200. .

  In the above explanation, the matching problem between the participant who wishes to participate in the training and the facility of the recipient is explained. Matching problem that matches each element with set B (corresponding to the above-mentioned facility) consisting of a plurality of elements, and set B is classified under a specific condition to form a group, and each group has a group capacity Needless to say, it can be applied to any of the matching problems.

That is, the present invention is a matching system for matching elements of a set A (participant group) consisting of a plurality of elements and a set B (group of facilities) consisting of a plurality of elements, the set B Each element (each facility) belongs to one or more groups, and a capacity file that stores the number of elements that can be accepted by matching for each B element ID (facility code) of each element of the set B (Facility information file 1), a group capacity condition file (group capacity condition file 2) that stores, for each group ID indicating a specific group of the set B, a B element ID belonging to this group and the number of groups For each A element ID of each element of the set A, a first priority list that is uniquely ranked for all or part of the elements of the set B is stored. The first priority list file (participant ROL file 3) and the B element ID of each element of the set B are uniquely ranked for all or part of the elements of the set A The second priority list file (facility ROL file 4) storing the second priority list and the group capacity number stored in the group capacity condition file are referred to. A capacity processing means (corresponding to step S21 in FIG. 5 or the number of optimization capacity of the B element ID belonging to) is stored in the optimization capacity information file in association with the B element ID. 2), and the number of optimized capacity stored in the first priority list file, the second priority list file, and the optimized capacity information file. And a matching processing means (corresponding to step S22 in FIG. 5 or equivalent to the matching means 9 in FIG. 2) for matching the elements of the set A with any element in the set B. Matching system.
This configuration corresponds to the configuration of claim 1 and is a configuration for performing the matching process shown in FIG.

Further, in the matching system according to the present invention, the capacity processing means includes matching processing based on constants stored in the first priority list file, the second priority list file, and the constant file in the matching processing means. The matching processing means stores the matching result in the storage means as a temporary match result (corresponding to step S31 in FIG. 6), and the group capacity number is within the group for each group ID of the group capacity condition file. If it is determined that the total number of the B elements is equal to or greater than the total number, the number of corresponding B elements is stored in the optimized capacity information file in association with the B element ID as the optimized capacity (step of FIG. 6). On the other hand, if it is determined that the group capacity is smaller than the total capacity of the B elements in the group, The B element ID record in the group is extracted with reference to the result of the check, the number of temporary matches for each B element and the total number of temporary matches for each B element in the group are calculated, and the total number of temporary matches for the B element in the group The number of provisional matches of each facility with respect to the value is multiplied by the number of group capacities, and the optimized number of facilities code is set, and this optimized number is optimally associated with the B element ID. It memorize | stores in a chemical capacity information file (equivalent to step S35 of FIG. 6).
This configuration corresponds to the configuration of the second aspect and is a configuration for performing the processing shown in FIG.

  As described above, according to the present embodiment, when a plurality of facilities constitute one group and the group has the number of groups, the total number of the capacity of the plurality of facilities particularly indicates the number of groups. When it exceeds, stable matching can be obtained.

  Moreover, according to this Embodiment, when a group is comprised in a prefecture, the appropriate personnel can be matched with the prefecture where a staff is insufficient. In addition, because matching is performed in consideration of the number of group members, when a group is formed in a department, it is possible to eliminate the bias for each department and to secure a certain number of departments with insufficient staff. .

Embodiment 2. FIG.
The system configuration diagram in the present embodiment is as shown in FIGS. 1 and 2 used in the first embodiment. What is characteristic in the present embodiment is that the capacity optimization process shown in step S21 of FIG. 5 is based on a method different from that of the first embodiment. Other processes are as described in the first embodiment.

  FIG. 15 is a flowchart showing the intra-group application setting number optimization process in the present embodiment. As shown in FIG. 15, the capacity processing means 8 of the matching server 100 sets a variable representing a group code as n and sets 1 to an initial value of n, and then refers to the group code item in the group capacity condition file 2 The maximum value of the group code registered in advance is stored (step S41). Next, the capacity processing means 8 confirms whether or not the current group code is larger than the maximum value of the stored group code (step S42), and if the current group code is larger than the maximum value, the process ends. To do.

  If the current group code is less than or equal to the maximum value, the process moves to step S43, and group facility code information belonging to the corresponding group code is obtained by referring to the group capacity condition file 2, and the capacity of each facility code The number is obtained by referring to the facility information file 1. Then, the total number of facilities of facilities belonging to the group is calculated, and the group capacity of the current group code is compared with the total number of facilities of facilities belonging to the group (step S43). If the group capacity is equal to or greater than the total capacity of the facilities in the group in the comparison in step S43, the optimized capacity information file 10 is associated with the facility code with each capacity of the corresponding facility code as the optimized capacity. (Step S45). Thereafter, the group code is incremented by 1 (step S46), and the process returns to step S42.

  If it is determined in step S43 that the group capacity is smaller than the total number of facilities in the group, the process proceeds to step S44. In the process of step S44, the capacity processing means 8 sets a number obtained by multiplying the ratio of the capacity of each facility to the total capacity of the facilities in the group by the number of group capacity as the optimized capacity of the corresponding facility. In addition, when the number calculated | required in this way does not become an integer, you may set so that the optimization capacity | capacitance number may become an integer by rounding off based on the number. The set optimization capacity is stored in the optimization capacity information file 10 in association with each facility code (step S44). Further, in the calculation of step S44, the “minimum capacity correction process” described in step S35 of the first embodiment is similarly processed. Thereafter, the process proceeds to step S46.

The process of step S44 will be described using a specific example. FIG. 16 shows examples 1 and 2 as specific examples. Example 1 exemplifies the case where the optimized capacity is calculated for the group code G01. The group code G01 has a group capacity of 25 people, and the group facility codes registered as a group are A001, A003, A010, and A011. Further, as shown in FIG. 15, the capacity number of each facility code is 10, 8, 10, 7 from the top, and the total number of capacity numbers is 35 persons. In the process of step S43 in FIG. 15, when the group capacity is compared with the total capacity of the facilities in the group, the group capacity is smaller than the total capacity, so the optimized capacity is obtained by the process of step S44. The calculation formula is to multiply the ratio of the capacity of each facility to the total capacity of the facilities in the group by the number of groups, and in the case of the facility code A001, 10 (A001 capacity Number) / 35 (total number of facilities in the group) × 25 (group capacity). As a result, in the case of the facility code A001, the optimized capacity is calculated as 7 persons, and the optimized capacity is 7, 6, 7, 5 from the top.
With such a calculation method, the group capacity can be allocated to the facility code in the group as an optimized capacity.

Example 2 in FIG. 16 illustrates the case where the optimized capacity is calculated for the group code G02. The group code G02 has a group capacity of 23 people, and the group facility codes registered as a group are A012, A015, A016, A017, and A018. Further, as shown in FIG. 16, the capacity number of each facility code is 3, 5, 4, 7, 3 from the top, and the total number of capacity is 22 persons. In the process of step S43 in FIG. 15, when the group capacity is compared with the total capacity value of the facilities in the group, the group capacity is greater than the total capacity value. Is not done.
In the specific example shown in FIG. 16, the minimum capacity correction process is not required, but the process is performed by the method described above as necessary.

In the matching system of the present invention, when the capacity processing means determines that the group capacity is equal to or greater than the total number of the B elements in the group for each group ID of the group capacity condition file, each of the corresponding B elements Is stored in the optimized capacity information file in correspondence with the B element ID as the optimized capacity (corresponding to step S45 in FIG. 15), while the group capacity is determined from the total number of B elements in the group. When it is determined to be small, the optimized capacity of the corresponding B element ID is set based on the ratio of the capacity of each B element to the total capacity of the B elements in the group multiplied by the number of groups. The optimized capacity number is stored in the optimized capacity information file in association with the B element ID (corresponding to step S44 in FIG. 15).
This configuration corresponds to the configuration of claim 3 and is a configuration for performing the processing shown in FIG.

Embodiment 3 FIG.
The system configuration diagram in the present embodiment is as shown in FIGS. 1 and 2 used in the first embodiment. What is characteristic in the present embodiment is that the capacity optimization process shown in step S21 of FIG. 5 is based on a method different from that in the first and second embodiments. Other processes are as described in the first embodiment.
In Embodiments 1 and 2, the optimized capacity is determined using division by the group capacity. In the third embodiment, the optimized capacity is determined using subtraction in consideration of the group capacity.

In the third embodiment, the number of temporary matches is first set as an optimization capacity, and then the optimization capacity of each facility code is subtracted by a certain value (for example, 1) in descending order of the optimization capacity. Repeat until the total number of optimized capacity is less than the group capacity.
In Example 1 of FIG. 14, the provisional match number (that is, the initial value of the optimized capacity) of the facility code A010 is as large as 8, so the optimized capacity number of the facility code A010 is first reduced to 7. Still, the optimization capacity of facility code A010 is still the largest, so this is further reduced to 6. Here, since the optimization capacity numbers of the facility code A003 and the facility code A010 are equal to 6, the optimization capacity number is decreased to 5 in the next stage. In this way, the subtraction is repeated until the total value of the optimized capacity is less than or equal to the group capacity.
If there are multiple facility codes with the maximum number of optimized capacity, all of the facility codes may be subtracted uniformly as described above. It is good also as subtracting only.

In addition, when performing the subtraction process, if the “minimum number of people” is set and the optimized capacity is subtracted, if the number is less than the minimum, the subtraction process will not be performed on the optimized capacity of the facility code. It can be configured.
Further, when the total number of optimized capacity is smaller than the group capacity, a fixed number is added in descending order of the optimized capacity. However, when the number of optimized capacity is equal to the number of capacity, processing is performed for the facility code having the next largest number of optimized capacity.

  According to the third embodiment, in exchange for the loss of fairness according to the number of temporary matches, facilities with a small number of temporary matches can be maintained without reducing the optimized capacity.

Furthermore, as a modified example of the third embodiment, a reference for determining a facility code to be subtracted can be different from that of the third embodiment. For example, participant ROL file 3, facility ROL file 4, or both may be considered.
For example, a criterion of subtracting the optimized capacity of the least popular facility can be used. This process is executed as follows. First, for each facility code, the participant ROL file 3 is referred to for all participants temporarily matched with the facility, and the average of the priority of the facility is calculated. Then, the optimized capacity number of the facility code having the highest average priority, that is, the least popular facility code is subtracted. In this way, the subtraction is repeated until the total value of the optimized capacity is less than or equal to the group capacity.

  According to such a modification, the priority can be taken into consideration in the optimization capacity determination process itself.

  Moreover, the method of the said Embodiment 1- Embodiment 3 is applicable also when the group is comprised hierarchically. That is, when a plurality of groups further constitute one meta group and the meta group also has a capacity requirement, the provisional optimization capacity is first determined based on the group capacity, and then the meta capacity is determined. The final optimized capacity can be determined based on the group capacity.

In each of the above embodiments, the matching system (matching server 100, participant terminal 200, facility manager terminal 300, matching manager terminal 400) can be realized by a computer. Although not shown, each device includes a CPU (Central Processing Unit) that realizes the function of the device by executing a program.
For example, the CPU is connected to a ROM (Read Only Memory), a RAM (Random Access Memory), a communication board, a display device, a K / B (keyboard), a mouse, an FDD (Flexible Disk Drive), and a CDD (Compact Disc) via a bus. Drive), magnetic disk device, optical disk device, printer device, scanner device and the like.
The RAM is an example of a volatile memory. ROM, FDD, CDD, magnetic disk device, and optical disk device are examples of nonvolatile memory. These are examples of a storage device or a storage unit.
Data and information handled by each device of the above-described embodiment are stored in a storage device or a storage unit, and are recorded and read by each unit of the device.
The communication board is connected to a WAN (Wide Area Network) such as a LAN, the Internet, or ISDN. The magnetic disk device stores an operating system (OS), a window system, a program group, and a file group (database).
The program group is executed by a CPU, OS, and window system.
Each part of each of the above devices may be configured by a program that can be operated by a computer in part or in whole. Alternatively, it may be realized by firmware stored in the ROM. Alternatively, it may be implemented by software, hardware, or a combination of software, hardware, and firmware.
The program group stores a program that causes the CPU to execute the processing described as “˜means” in the description of the embodiment and realizes the function of the means. These programs are created by computer languages, such as C language, HTML, SGML, and XML, for example.
The program is stored in another recording medium such as a magnetic disk device, FD (Flexible Disk), optical disk, CD (compact disk), MD (mini disk), DVD (Digital Versatile Disk), and read by the CPU. And executed.

  1 facility information file, 2 group capacity condition file, 3 participant ROL file, 4 facility ROL file, 5 matching result storage file, 6 communication means, 7 ROL creation means, 8 capacity processing means, 9 matching means (matching processing means) 10 Optimized capacity information file, 20 input means, 21 display means, 22 processing means, 23 communication means, 30 input means, 31 display means, 32 processing means, 33 communication means, 100 matching server, 200 participant terminal, 300 Facility manager terminal, 400 matching manager terminal, 500 communication network.

Claims (3)

A matching system for matching elements of a set A composed of a plurality of elements and a set B composed of a plurality of elements,
Each element of the set B belongs to one or more groups,
For each B element ID of each element of the set B, a quorum file storing the quorum acceptable for matching,
For each group ID indicating a specific group of the set B, a group capacity condition file storing a B element ID belonging to this group and the number of group capacity,
A first priority list file storing a first priority list uniquely ranked for all or part of the elements of the set B for each A element ID of each element of the set A When,
A second priority list file storing a second priority list uniquely ranked for all or part of the elements of the set A for each B element ID of each element of the set B When,
Refers to the group capacity stored in the group capacity condition file, calculates the optimized capacity of the B element ID belonging to the group based on this group capacity, and associates the calculated optimized capacity with the B element ID In addition, capacity processing means for storing in the optimized capacity information file,
Based on the optimized capacity numbers stored in the first priority list file, the second priority list file, and the optimized capacity information file, the elements of the set A are changed to any of the elements of the set B. On the other hand, a matching system comprising: matching processing means for performing matching processing. The capacity processing means instructs the matching processing means to perform matching processing based on constants stored in the first priority list file, the second priority list file, and the constant file, and the matching processing means Stores the result of the matching as a temporary match result in the storage means,
For each group ID in the above group capacity condition file, if it is determined that the group capacity is equal to or greater than the total number of B elements in the group, each element number of the corresponding B element is set as the optimized capacity number. Stored in the optimized capacity information file in association with
On the other hand, when it is determined that the group capacity is smaller than the total number of B elements in the group, the provisional match result is referred to, and the number of temporary matches for each B element and the total number of provisional matches for each B element in the group. Value is calculated, and the optimized capacity of the corresponding B element ID is set based on the ratio of the number of provisional matches of each B element to the total number of provisional matches of the B elements in the group multiplied by the above group capacity The matching system according to claim 1, wherein the optimized capacity number is stored in an optimized capacity information file in association with the B element ID. The capacity processing means optimizes the capacity of each B element when the group capacity is determined to be greater than or equal to the total number of B elements in the group for each group ID in the group capacity condition file. Store it in the optimized capacity information file in association with the B element ID as the capacity,
On the other hand, if it is determined that the group capacity is smaller than the total number of B elements in the group, the ratio of the number of each B element to the total number of B elements in the group multiplied by the group capacity 2. The matching capacity according to claim 1, wherein an optimization capacity number of the corresponding B element ID is set based on the information, and the optimization capacity number is stored in an optimization capacity information file in association with the B element ID. system.

Images