JP4355708B2 - 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. 14, as a matching between a set of applicants {a1, a2, a3, a4, a5, a6, a7} and a 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. 15 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. 15, 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 given a set of applicants, a group of companies, and a priority list of applicants and companies. 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. All pairs (a, p) of applicants and companies not included in matching X are not blocking pairs. 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. 16 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. 16, the outline will be briefly described with reference to FIG. The example in FIG. 17 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 is rejected, and when it is proposed to the 3rd hope Mimura Hospital, it is named 6th (Eguchi, 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 request 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.

  With reference to the flowchart of FIG. 16 described above, this processing performed by taking FIG. 17 as an example will be described. 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 if the proposed applicant a is not listed in the ROL (p), and the rejected applicant a is ranked in the company's priority list ROL (a). This is equivalent to reproposing to the next smaller company after p. 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 in FIG. 16 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 temporary 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, for example, a training program for becoming a dentist is a one-to-M combination (M ≧ 2) in which a combination of assigning a plurality of facilities to one training applicant must be determined. You may have to ask for.
In such a case, the above-described matching system has a problem that a combination cannot be obtained.

  Also, if you want to find a 1-to-M combination using a conventional matching system, prepare the required number of matching systems according to the contents of the training program, or repeat the same system over and over again. There has been a problem that it is necessary to perform processing using them.

  For this purpose, it takes a cost to construct and operate multiple systems at the same time, or it takes processing time to continuously operate the required number of times, and the user has similar priority Since it is necessary to input the list ROL data a plurality of times, there is a problem that it takes time for the user, the data to be input is confused, and an input error occurs.

  The present invention has been made to solve such a problem, and it is possible to determine a one-to-many combination from a single input, which does not require time, processing time, and cost. The aim is to obtain a matching system that can be suppressed.

  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 a matching processing target section for performing a matching process is divided into one or more sections. Each element of the set A belongs to one or more groups, and the classification is common to the groups, and the classification process is performed for each group ID of the group. A matching category designation registration unit in which a category ID is registered; a group information storage unit in which a group ID of the group to which each element belongs is stored for each A element ID of each element of the set A; Constant storage means for storing constants acceptable for matching for each B element ID of each element of the set B, and A element I of each element of the set A A first priority list storage means for storing a first priority list uniquely ranked for all or a part of the elements of the set B, and for each element of the set B Second priority list storage means for storing a second priority list uniquely ranked for all or part of the elements of the set A for each B element ID, and the matching category designation A group ID extraction unit that extracts a group ID corresponding to each category ID from the registration unit, and an A element ID that corresponds to the group ID extracted for each category ID is extracted from the group information storage unit. A first ID for extracting a record corresponding to the extracted A element ID from the first priority list and creating a temporary first priority list for each element ID extraction means and the category ID Temporal priority list creation means, and for each category ID, a record including the extracted A element ID is extracted from the second priority list to create a temporary second priority list. Based on the temporary priority list creating means and the temporary first and second priority lists, all the extracted elements of the set A are sequentially assigned to each of the classification IDs in any of the sets B. This is a matching system including matching processing means for performing a matching process on these elements.

  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 a matching processing target section for performing a matching process is divided into one or more sections. Each element of the set A belongs to one or more groups, and the classification is common to the groups, and the classification process is performed for each group ID of the group. A matching category designation registration unit in which a category ID is registered; a group information storage unit in which a group ID of the group to which each element belongs is stored for each A element ID of each element of the set A; Constant storage means for storing constants acceptable for matching for each B element ID of each element of the set B, and A element I of each element of the set A A first priority list storage means for storing a first priority list uniquely ranked for all or a part of the elements of the set B, and for each element of the set B Second priority list storage means for storing a second priority list uniquely ranked for all or part of the elements of the set A for each B element ID, and the matching category designation A group ID extraction unit that extracts a group ID corresponding to each category ID from the registration unit, and an A element ID that corresponds to the group ID extracted for each category ID is extracted from the group information storage unit. A first ID for extracting a record corresponding to the extracted A element ID from the first priority list and creating a temporary first priority list for each element ID extraction means and the category ID Temporal priority list creation means, and for each category ID, a record including the extracted A element ID is extracted from the second priority list to create a temporary second priority list. Based on the temporary priority list creating means and the temporary first and second priority lists, all the extracted elements of the set A are sequentially assigned to each of the classification IDs in any of the sets B. Since this is a matching system including a matching processing means for performing a matching process on such an element, it is possible to determine a one-to-multiple combination from a single input, and it is not time-consuming. It is possible to obtain a matching system that is fast in time and can reduce costs.

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 the dentistry department who wants to train (hereinafter referred to as a participant) has one or more dental medical facilities (ie university hospitals or open dentistry). 7), it is necessary to experience a large number of treatments. For example, as shown in FIG. 7 (a), training is conducted at the facility B in the first term and training is conducted at the facility C in the second term. One participant must seek a combination that matches multiple dental care facilities. In addition, the capacity that can be accepted at one facility is about 1 to 2, but there is little information about each facility, so there is a tendency for participants to refer to the training records of the previous year, etc., and there is hope for a specific facility Since there are situations where it is easy to concentrate, some measure must be taken to improve the matching rate.

  FIG. 7B is a diagram showing an example of a training program for explaining the present embodiment. In the example of Fig. 7 (b), the training setting period (section) is from April of a certain year to March of the following year, and the training setting period is divided into three periods: the previous period, the middle period, and the latter period. The first period (SNO = 1) is April to July, the middle period (SNO = 2) is August to November, and the second period (SNO = 3) is December to March. In FIG. 7 (b), “management type” means training at a relatively large scale medical facility, that is, a university hospital or the like. It is unnecessary. On the other hand, “cooperative type” means training at a so-called practitioner with a small scale of about 1 to 2 people that can be accepted, and this requires a combination determination by matching. The A program is a management type in the first and second half, and a cooperative type in the middle. That is, matching for the middle period is necessary. The B program is managed in the first half and cooperative (and the same facility) in the middle and second half. Since the training is conducted at the same facility in the middle and late periods, it is not necessary to match twice, and a combination of both the middle and late periods can be determined by one matching. The C program is managed in the first half and cooperative (different facilities) in the middle and second half. Therefore, it is necessary to perform the matching process twice in the C program. Participants select one of these three programs, and create a wish list (hereinafter referred to as ROL) in which desired facilities are to be trained in order of preference. In the present embodiment, a complicated matching problem in which a plurality of types of training programs exist and a plurality of facilities need to be assigned to one participant will be described as an example. Further, in the example shown in FIG. 7B, the training settable period (section) and the start timing and end timing of the sections within the section (first term, middle term, and second term) are the same in any program.

  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, the program master file 1, the participant program information file 2, the facility program information file 3, the participant ROL file 4, the facility ROL file 5, and the matching result Six files of the storage file 6 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 7 for communicating with the outside via the communication network 500, a ROL creation means 8 for creating a ROL (desired table), an extraction means 9, and a matching Means 10 are provided.

  FIG. 8 is a diagram showing an example of the program master file 1. In FIG. 8, codes A, B, and C, which are IDs indicating the programs shown in FIG. 7B, are stored as program numbers. SNO stores numbers 1 (first half), 2 (middle half), and 3 (second half), which are IDs indicating the respective divisions shown in FIG. 7B. The continuous SNO is an ID for designating which category of matching results to be continued when the matching result of the medium term (SNO = 2) is continued in the latter term (SNO = 3) as in the B program. Stored. Since the example of FIG. 8 is based on the program information of FIG. 7B, in the first period (SNO = 1), participants in the management-type facilities in any of the programs A, B, and C Since all the members are assigned, there is no need for matching. Therefore, data in the case of SNO = 1 is not stored in the program master file 1. Further, in the latter half of the A program (SNO = 3), since all the persons who selected the A program are assigned to the management-type facilities, there is no need for matching, so the data in the case of SNO = 1 is the program master file 1 It is not stored in. Since it is desirable to be assigned to the same cooperative type in the middle period (SNO = 2) and the latter period (SNO = 3) of the B program, the matching result of the middle period (continuous SNO = 2) is designated as the latter period (SNO = 3). In order to perform processing for subtracting the number of matching in the middle period (SNO = 2) from the capacity in the latter period (SNO = 3) and performing matching for the latter period (SNO = 3) of the C program, In the continuation SNO in the later stage (SNO = 3) record of the program, “2” that is an ID indicating the middle period is stored.

  FIG. 9 is a diagram showing an example of the participant program information file 2. As shown in FIG. 9, the participant program information file 2 stores a user ID for identifying a participant and a program number indicating the training program selected by each participant for each user ID. . That is, the participant with the user ID “001” selects the A program, the participant with the user ID “002” selects the B program, the participant with the user ID “003” selects the A program, ... information indicating that all the participants are stored.

  FIG. 10 is a diagram showing an example of the facility program information file 3. The facility program information file 3 stores information on each facility that conducts cooperative training. That is, the facility program information file 3 includes, for example, information such as a facility code that is an ID for identifying each facility, a facility name, a capacity (capacity of participants), a facility address (location of the facility), and the like. Stored.

  FIG. 11 is a diagram showing an example of the participant ROL file 4. The participant ROL file 4 stores a list in which the facilities desired by each user are arranged in the desired order for each user ID. In FIG. 11, 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. It is not necessary to register all the facilities in the participant ROL file 4, for example, it is not necessary to register in the participant ROL file 4 for facilities that do not want to undergo training, and only the desired facility is registered in the participant ROL file 4. You may make it register.

  FIG. 12 is a diagram showing an example of the facility ROL file 5. The facility ROL file 5 stores a list in which participants desired by each facility are arranged in the desired order for each facility code. In FIG. 12, the participants from the first desire to the nth desire are stored in order for each facility. Each facility, for example, interviews participants and obtains information on the participants, and determines a desired order. Note that it is not necessary to register all the participants in the facility ROL file 5, for example, it is not necessary to register in the facility ROL file 5 for participants who do not want to accept, and register only the desired participants in the facility ROL file 5. You may do it.

FIG. 13 is a diagram showing an example of the matching result storage file 6. The matching result storage file 6 stores the matching results obtained as a result of the matching process. That is, as shown in FIG. 13, the SNO (section), the user ID, and the facility code of the allocated facility are stored in association with each other. Thereby, it is possible to confirm in which category (training period) which participant performs training.
In the file structure shown in FIGS. 11 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 the data input process from the matching manager terminal 400. The process when the matching manager registers, adds, or deletes the program master file 1 or the facility program information file 3 is shown. The flow is shown. As shown in FIG. 3, first, the processing means 32 of the matching manager terminal 400 transfers 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 unit 33 of the matching manager terminal 400 transmits the input data to the communication unit 7 of the matching server 100 (step S2). Next, the communication means 7 of the matching server 100 adds, updates, or deletes data in the program master file 1 or the facility program information file 3 according to the received data content (step S3).

FIG. 4 is a diagram showing a data input process from the participant terminal 200, and shows a process flow when the participant inputs a wish table (ROL) indicating various hopes and a desired order regarding the training program. Yes. 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 7 of the matching server 100 (step S12). Next, the communication means 7 of the matching server 100 determines the received data content (step S13). If the received data is ROL data as a result of the discrimination, the ROL creation means 8 of the matching server 100 adds, updates, or deletes data in the participant ROL file 4 (step S15). On the other hand, if the received data is the desired program data as a result of the discrimination, the communication means 7 of the matching server 100 adds, updates, or deletes data in the participant program information file 2 (step S14).
Also, when receiving data input from the facility manager terminal 300, the flow is the same as the flowchart shown in FIG. However, in this case, the processing in steps S13 and S14 is not necessary, and the process proceeds directly from step S12 to step S15, where data in the facility ROL file 5 is added, updated, or deleted. Note that the process of adding, updating, and deleting data to the participant program information file 2, the facility program information file 3, the participant ROL file 4, and the facility ROL file 5 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 ROL extraction processing by the extraction means 9 of the matching server 100 and matching processing by the matching means 10. As shown in FIG. 5, first, the extraction means 9 of the matching server 100 sets SNO = n to 1 which is an initial value of n, and registers the maximum value of n in advance (step S21). Next, the extraction means 9 of the matching server 100 ends the process if the current SNO is larger than the preset maximum value of SNO (= n), and proceeds to step S22 if it is less than the maximum value. (Step S30). Next, the extraction means 9 of the matching server 100 extracts all program numbers corresponding to the current SNO (first time SNO = 1) and no continuation SNO are designated from the program master file 1 (step S22). If there is a corresponding SNO as a result of the extraction, all user IDs corresponding to the program numbers extracted by the extraction means 9 of the matching server 100 are selected from the participant program information file 2 (step S23). On the other hand, if there is no corresponding SNO as a result of extraction and the current SNO is equal to or less than the preset maximum value of SNO, the process proceeds to step S29. Next, the ROL creation means 9 of the matching server 100 takes out the record of the user ID selected in step S23 from the participant ROL file 4 and creates a temporary participant ROL file (step S24). Next, a record including the user ID selected in step S23 is taken out from the facility ROL file 5, and a temporary facility ROL file is created. After that, the capacity information of each facility included in the temporary facility ROL file is extracted from the facility program information file 3, and temporary capacity information is formed from the capacity (the capacity is copied to the temporary capacity information of each facility). (Step S25). Next, the extraction means 9 of the matching server 100 refers to the program master file 1 and determines whether there is any current SNO for which a continuous SNO is specified (step S26). When the continuous SNO is not designated, the matching unit 10 of the matching server 100 performs the matching process using the Gale-Shapley algorithm shown in FIG. 16 and stores the obtained matching result in the matching result storage file 6. (Step S27). On the other hand, if the result of determination in step S26 is that continuous SNO is specified, the extraction means 9 of the matching server 100 refers to the matching result storage file 6 and matches the SNO specified in the continuous SNO. Is identified. Thereafter, the number of matches for each facility is subtracted from the temporary capacity information configured in step S25, and the temporary capacity information is rewritten (the capacity is changed to the capacity obtained by subtracting the number of matches from the capacity) (step S28). ) After that, the process proceeds to step S27. When the process of step S27 ends, the matching means 10 of the matching server 100 increases the value of SNO by 1 (step S29) and returns to the process of step S22.
In the matching process in step S27, if the temporary participant ROL file created in step S24, the temporary facility ROL file created in step S25, the file created in step S25, and branched to step S28, the process proceeds to step S28. The rewritten temporary capacity information is used. The temporary capacity information created in step S28 is transferred to the matching means by being stored in a storage means (not shown).
In the matching process in step S27, all user IDs stored in the temporary participant ROL file are stored in the temporary facility ROL file within the range of the temporary capacity information passed. Processing is performed so as to obtain the facility code and the combination. As a result of the matching process, there may be a case where a user ID that cannot be combined with the facility code may be generated.

  The processing flow of FIG. 5 will be described more specifically based on the example of FIG. First, in step S21, SNO is set to an initial value of 1, and 3 is registered in advance as the maximum value of n. Next, in step S22, all program numbers corresponding to SNO of 1 are extracted from the program master file 1. At this time, as is apparent from FIG. 8, since there is no SNO having one, the process proceeds to step S29, where 1 is added to the value of SNO, and SNO is set to two.

  In step S22, all program numbers having SNO of 2 are extracted from the program master file 1. As shown in FIG. 8, since the programs having SNO of 2 are all A, B, and C, all of them are extracted. In step S23, user IDs corresponding to the A, B, and C programs are all selected from the participant program information file 2. As shown in FIG. 9, in this case, all participants are selected. Next, in step S24, the ROLs of all the participants are taken out from the participant ROL file 4, and a temporary participant ROL file is created. In step S25, a record including the user IDs of all the participants is extracted from the facility ROL file 5, and a temporary facility ROL file is created. Next, in step S26, it is determined whether or not there is a current SNO, that is, a continuation SNO is designated among the SNOs of two. As is apparent from FIG. 8, since there is nothing applicable in this case, the process proceeds to step S27, and matching processing using the Gale-Shapley algorithm is performed based on the temporary participant ROL file and the temporary facility ROL file. The result is stored in the matching result storage file 6. Next, in step S29, 1 is added to the value of SNO, and SNO is set to 3.

  Next, proceeding to step S22, all program numbers for which SNO is 3 and continuation SNO is not specified are extracted from program master file 1. As shown in FIG. 8, the programs having SNO of 3 are B and C, but since B is designated as continuous SNO, B is not extracted but only C is extracted. In step S23, all user IDs corresponding to the C program are selected from the participant program information file 2 shown in FIG. Next, in step S24, the ROL of the selected participant is extracted from the participant ROL file 4, and a temporary participant ROL file is created. In step S25, a record including the user ID of the participant selected from the facility ROL file 5 is extracted, and a temporary facility ROL file is created. Further, temporary capacity information is configured by taking out the capacity information of each facility included in the temporary facility ROL file from the facility program information file 3 and copying the number of the capacity. Next, in step S26, it is determined whether or not there is a current SNO, that is, a continuation SNO is designated among the SNOs of three. As apparent from FIG. 8, since the B program is applicable, the process proceeds to step S28, the matching result storage file 6 is referred to, and the number of matches in the B program of the continuous SNO (in this case, 2) is determined in step S25. Subtract from the configured temporary capacity information to reconstruct the temporary capacity information. As a result, matching is performed in the next step S27 only when the SNO of the C program is 3. Accordingly, the process proceeds to step S27, where matching processing using the Gale-Shapley algorithm is performed based on the temporary participant ROL file, temporary facility ROL file, and temporary capacity information, and the result is stored in the matching result storage file 6 To do. Next, in step S29, 1 is added to the value of SNO, and SNO is set to 4.

  In step S22, since the value of SNO is larger than 3, which is preset as the maximum value, the processing is terminated as it is.

FIG. 6 is a diagram showing the process of notifying the matching result by the communication unit 7 of the matching server 100. As shown in FIG. 6, the matching unit 10 of the matching server 100 first notifies the notification unit 7 of the end of the matching process (step S31). Next, the communication unit 7 of the matching server 100 notifies the matching result to the communication unit 33 of the matching manager terminal 400 (step S32). Next, the communication unit 33 of the matching manager terminal 400 delivers the notified matching result to the processing unit 32 (step S33). Next, the processing means 32 of the matching manager terminal 400 publishes the transferred matching result on the Internet or the like (step S34).
Note that the disclosure of matching results is not limited to the method shown in FIG. 6, and there is a method of notifying participants and facility managers in paper format and printed results.

  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. However, the present invention is not limited to this, and the set A composed of a plurality of elements (corresponding to the above participant) and Matching problem of matching each element with set B (corresponding to the above facility) consisting of a plurality of elements, and the matching process target section for performing the matching process is divided into one or more sections (corresponding to the above training period SNO) It is divided and each element of set A belongs to one or more groups (corresponding to the above training program), and the above classification is applicable to any matching problem that is common among groups Not too long.

That is, according to the present invention, for each group ID of each group, a matching category designation registration means (corresponding to SNO of the program master file 1) in which the category ID of the category to be matched is registered, and the set A Group information storage means (corresponding to the participant program information file 2) for storing the group ID of the group to which each element belongs, for each A element ID of each element, Constant storage means (corresponding to the capacity of the facility program information file 3) that stores constants acceptable for matching for each B element ID of the element, and the above set for each A element ID of each element of the set A First priority list storage means (first above) storing a first priority list uniquely ranked for all or part of the elements of B (Corresponding to the participant ROL file 4) and a second priority list uniquely ranked for all or some of the elements of the set A for each B element ID of each element of the set B Second priority list storage means (corresponding to the facility ROL file) and group ID extraction means for extracting a group ID corresponding to each category ID from the matching category designation registering means (see FIG. 5 above) And the A element ID extracting means for extracting the A element ID corresponding to the extracted group ID from the group information storage means (for step S23 in FIG. 5 above). For each category ID, a record corresponding to the extracted A element ID is extracted from the first priority list, and a temporary first priority list is created. First temporary priority list creation means (corresponding to step S24 in FIG. 5 above), and for each of the section IDs, a record including the extracted A element ID is extracted from the second priority list. Second temporary priority list creating means for creating a temporary second priority list (corresponding to step S25 in FIG. 5 above) and the temporary first and second priority lists. The matching processing means (corresponding to step S27 in FIG. 5 above) that sequentially matches all the extracted elements of the set A to any element of the set B for each category ID. ).
This configuration corresponds to the configuration of claim 1 and is a configuration in the case where the process does not branch from step S26 to step S28 in the matching processing shown in FIG.

  Furthermore, when the matching system of the present invention is used in the same group by diverting the matching result of the above-mentioned category previously subjected to the matching process as the matching result of the post-processing category in which the matching process is performed thereafter, Matching result continuation use registration means (corresponding to the continuation SNO of the above program master file 1) that registers the division ID of the destination division to be diverted in correspondence with the division ID of the post-processing division for each group ID. ) And for each category ID, the category in which the category ID of the diversion destination is registered is extracted from the matching result continuous use registration unit, and the number of elements of the set A that match in the diversion destination matching result is calculated. Constant subtracting means for subtracting from the constant for each element of the set B in the relevant section (the step of FIG. The matching processing means performs the matching processing using the subtracted constants, and this configuration corresponds to the configuration of claim 2, and corresponds to the configuration of claim 2. The matching process shown in FIG. 5 includes a case where the process branches from step S26 to step S28.

  As described above, according to the present invention, even in the case where the matching processing target section (training setting possible period) is divided into one or more sections (periods), the condition is set for each section (period). Since the combined temporary ROL (participant ROL file and facility ROL file) is created and matching processing is performed using them, the user (participant and the person in charge of the facility) only performs ROL once. Matching results for all categories (all periods) can be obtained simply by inputting, and an increase in the work load of users (participants and facility staff) can be prevented.

  Further, according to the present embodiment, there are a plurality of groups (a plurality of types of training programs (A, B, C)) as shown in FIG. 7B, and one element of the set A ( Matching processing can be easily and reliably performed for a complicated matching problem that requires assignment of a plurality of elements (a plurality of facilities) of the set B to one participant).

  In this embodiment, when the matching result of the category (period) for which matching has been performed earlier is used, the matching result of which category (period) is matched to the matching result continuous use registration means (program master file 1). Register the result you want to continue, do not match for that amount, and subtract the number of people from the constant (capacity) of the set B (facility), and then the remaining number (number of people) ) As a matching process, even if a group (program) that diverts the matching result of the previous division (period) and a group (program) that does not divert exist in the same division (period) A matching result can be obtained automatically and easily without performing any operation.

Embodiment 2. FIG.
In the first embodiment, the training settable period (section) and the start time and end time of the section within the section (first term, middle term, second term) are the same in any program as shown in FIG. 7B. It was supposed to be. On the other hand, during the training available period (for example, one year from April 2006 to March 2007), the A program is April to June 2006, the B program is May to October 2006, and the C program Can be matched by applying the matching system shown in the first embodiment, even if training for a period different from September 2006 to January 2007 is set. In the present embodiment, the flow of processing when the period set for each program is different will be described.

FIG. 18 is an example showing the configuration of the program master file 1 according to the present embodiment. By configuring the program master file 1 as shown in FIG. 18, the matching process can be performed by the same process as the process shown in FIGS. The file configuration other than the program master file 1 is the same as that described in the first embodiment.
The setting of the program master file 1 will be described. Specifically, the unit of classification (SNO) is set to one month, and for example, the classification from April 2006 to March 2007 is set as 1, 2, 3,. Thereafter, the program master file 1 is configured by replacing the period set by each program with the division (SNO) and the continuous SNO. As shown in FIG. 18, for example, in the A program, SNO = 1 (April 2006), SNO = 2 (May 2006), SNO = 3 (June 2006) are set, and SNO = 2 Continuation SNO = 1 is set, and SNO = 3 is set to continuation SNO = 2. By setting in this way, a matching result can be obtained in the flow of the matching process shown in FIG.

  As described above, in this embodiment, even if the training period in the section is different for each program, the matching process is performed by subdividing the training period and replacing the training period with a category. be able to. Depending on the program settings, the starting date of the training may start from the middle of the month (for example, the 15th) instead of starting from the first day of each month. When substituting for a segment, the segment may be further subdivided to correspond to the duration of the training (for example, if there is a program that includes a training that starts on the 15th day of any month, the SNO is set to 1 to 24).

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 executes 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 “to means” in the description of the embodiment. 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.

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 explanatory drawing which showed the example of the training program in the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the program master file of the matching system which concerns on Embodiment 1 of this invention. It is explanatory drawing which showed an example of the participant 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 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 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 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. It is explanatory drawing which showed an example of the program master file of the matching system which concerns on Embodiment 2 of this invention.

Explanation of symbols

  1 program master file, 2 participant program information file, 3 facility program information file, 4 participant ROL file, 5 facility ROL file, 6 matching result storage file, 7 communication means, 8 ROL creation means, 9 extraction means, 10 matching Means, 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 (2)

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,
The matching process target section for performing the matching process is divided into one or more sections,
Each element of the set A belongs to one or more groups,
The above categories are common to the above groups,
For each group ID of the group, a matching category designation registration means in which the category ID of the category for performing the matching process is registered,
Group information storage means for storing, for each A element ID of each element of the set A, the group ID of the group to which each element belongs;
Constant storage means for storing constants acceptable for matching for each B element ID of each element of the set B;
A first priority list storage 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 Means,
A second priority list storage 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 Means,
Group ID extraction means for extracting a corresponding group ID for each of the classification IDs from the matching classification designation registration means;
A element ID extracting means for extracting the A element ID corresponding to the extracted group ID from the group information storage means for each of the category IDs;
First temporary priority list creation means for creating a temporary first priority list by extracting a record corresponding to the extracted A element ID from the first priority list for each category ID When,
Second temporary priority list creating means for creating a temporary second priority list by extracting a record including the extracted A element ID from the second priority list for each category ID; ,
Based on the temporary first and second priority lists, all the extracted elements of the set A are sequentially matched to any element of the set B for each section ID. A matching system comprising: a matching processing means to perform. In the same group, when the matching result of the above-mentioned category that has been matched first is used as the matching result of the post-processing category that is subsequently matched, the post-processing is performed for each group ID. Matching result continuous use registration means for registering the category ID of the destination category to be diverted in correspondence with the category ID of the category of
For each category ID, a category in which the category ID of the diversion destination is registered is extracted from the matching result continuous use registration unit, and the number of elements of the set A that match in the diversion destination matching result is applicable. Constant subtracting means for subtracting from a constant for each element of the set B in the section,
The matching system according to claim 1, wherein the matching processing unit performs the matching processing using the subtracted constant.

Images