Y. Xu et aL/ Expert Systems with Applications 37(2010)6948-6956 group is used to measure the matching degree between a proposal Initialize population P(r) based on GRASP group and a reviewer. 3. 4.2. Eliminating possible conflicts of interests Select parents from P(1) In order to ensure the fairness of the project selection, potential conflicts of interests between reviewers and applicants must be avoided as much as possible. For example, the applicants and on operator on parents eviewers cannot come form same institution or have co-authe relationship. If conflicts of interests between any applicant of proposal group and a reviewer exist, then the matching degree be- ween this reviewer and the proposal group is set to be o or a neg- Applyrepair operator on infeasible children tive number so as to avoid the matching. 3.5. Step 5. Assigning reviewers to proposal groups Use local search to improve the quality of children In step 5, the proposal groups generated in step 3 are assigned Evaluate the fitness of childre to reviewers based on the matching degree between proposal whether groups and reviewers calculated in step 4 and other considerations as mentioned in Section 2. Recall that the research problem is to find the most qualified reviewers for each proposal group. That t=t+I is, maximize the matching degree between the proposal groups d reviewers while satisfying the funding constraints. This is ex- pressed in an assignment model as discussed in Section 3.5.1. Then a hybrid approach based on gRASP (Greedy randomized Adaptive Search Procedure)and genetic algorithm is proposed to solve the assignment model for the large volume problems in the following 3.5.1. The assignment model Let n be the number of proposal groups needed to be assigned m be the total number of available reviewers, i be the index of pro- posal groups (i=1,2,., n) be G=1, 2,..., m), a be the required number of reviewers for evaluat- Fig 4. The structure of the hy brid GRASP and gA ing each proposal group(in most funding it is usually 3 or 5) and b be the maximum number of proposal groups that a re- ewer can be assigned to. xy is a binary variable whose value is g algorithm may not be superior to other heuristic 1 if group i is assigned to reviewer j, and 0 otherwise. The mathe algorit when a genetic algorithm is combined with a local matical model can be formulated as follows: search he efficiency of the algorithm can be improve Ahuja, Orlin, Tiwari, 2000). A combination of hybrid GRASI Maximize∑∑Mn2sMax(C*4)k and genetic algorithm can be used to solve the above mathematical model while overcoming the weaknesses of the general GA. It Subject to a vi (1) cludes the steps of initialization, selection, crossover, mutation and other operators as shown in Fig 4 ∑刈≤b可 3.5.3. The hybrid GRASP and GA Xi=0.1 (3) 3.5.3.1. Representation. A matrix whose elements are either 0 1 can be used to represent a solution to the reviewer assignmen Constraint(1)guarantees that the number of proposal groups as- to the jth reviewer, then the value of the corresponding element of signed to each reviewer should not exceed a predetermined number to ensure the review quality when the number of proposals and the solution matrix is 1 or o otherwise. The combination of 0 and 1 reviewers is small, the exact algorithm can work ell to solvi variables in the matrix do are as- signed to which reviewers(as shown in Fig. 5). When the matrix ciently by exact algorithm in reasonable time due to the dual prob- is too sparse, another representation technique is used where the lems of large volume of proposals and reviewers and limited available time. Thus, we propose here a heuristic algorithm based on a hybrid GRASP and genetic algorithm for an efficient solution R1R2R3….R。 when the number of proposals and reviewers is large G1101 G,01 3.5.2. The proposed solution to the assignment model G3110 Genetic algorithms have been applied to several kinds of com- tory performance(Huang Lim, 2006: Nebro, Luque, Luna, Alba 2008: Tang, Quek, Ng, 2005). It has also been shown that a Fig. 5. Representation of an individuals chromosome.group is used to measure the matching degree between a proposal group and a reviewer. 3.4.2. Eliminating possible conflicts of interests In order to ensure the fairness of the project selection, potential conflicts of interests between reviewers and applicants must be avoided as much as possible. For example, the applicants and reviewers cannot come form same institution or have co-author relationship. If conflicts of interests between any applicant of a proposal group and a reviewer exist, then the matching degree be￾tween this reviewer and the proposal group is set to be 0 or a neg￾ative number so as to avoid the matching. 3.5. Step 5. Assigning reviewers to proposal groups In step 5, the proposal groups generated in step 3 are assigned to reviewers based on the matching degree between proposal groups and reviewers calculated in step 4 and other considerations as mentioned in Section 2. Recall that the research problem is to find the most qualified reviewers for each proposal group. That is, maximize the matching degree between the proposal groups and reviewers while satisfying the funding constraints. This is ex￾pressed in an assignment model as discussed in Section 3.5.1. Then a hybrid approach based on GRASP (Greedy Randomized Adaptive Search Procedure) and genetic algorithm is proposed to solve the assignment model for the large volume problems in the following subsections. 3.5.1. The assignment model Let n be the number of proposal groups needed to be assigned, m be the total number of available reviewers, i be the index of pro￾posal groups (i = 1,2,...,n),j be the index of reviewers (j = 1,2,...,m), a be the required number of reviewers for evaluat￾ing each proposal group (in most funding agencies, it is usually 3 or 5), and b be the maximum number of proposal groups that a re￾viewer can be assigned to. xij is a binary variable whose value is 1 if group i is assigned to reviewer j, and 0 otherwise. The mathe￾matical model can be formulated as follows: Maximize X i2I X j2J ½Ming2iMaxkðCjk dgkÞxij Subject to X j xij ¼ a 8i ð1Þ X i xij 6 b 8j ð2Þ xij ¼ 0; 1 ð3Þ Constraint (1) expresses the requirement that each group of propos￾als should be evaluated by a reviewers. Constraint (2) implies that each reviewer should be assigned at most to b proposal groups. Constraint (1) guarantees that the number of proposal groups as￾signed to each reviewer should not exceed a predetermined number to ensure the review quality. When the number of proposals and reviewers is small, the exact algorithm can work very well to solve the above model. However, the above model cannot be solved effi- ciently by exact algorithm in reasonable time due to the dual prob￾lems of large volume of proposals and reviewers and limited available time. Thus, we propose here a heuristic algorithm based on a hybrid GRASP and genetic algorithm for an efficient solution when the number of proposals and reviewers is large. 3.5.2. The proposed solution to the assignment model Genetic algorithms have been applied to several kinds of com￾binatorial optimization problems and have demonstrated satisfac￾tory performance (Huang & Lim, 2006; Nebro, Luque, Luna, & Alba, 2008; Tang, Quek, & Ng, 2005). It has also been shown that a general genetic algorithm may not be superior to other heuristic algorithms. But when a genetic algorithm is combined with a local search strategy, the efficiency of the algorithm can be improved (Ahuja, Orlin, & Tiwari, 2000). A combination of hybrid GRASP and genetic algorithm can be used to solve the above mathematical model while overcoming the weaknesses of the general GA. It in￾cludes the steps of initialization, selection, crossover, mutation and other operators as shown in Fig. 4. 3.5.3. The hybrid GRASP and GA 3.5.3.1. Representation. A matrix whose elements are either 0 or 1 can be used to represent a solution to the reviewer assignment problem, which is referred to as chromosome in genetic algorithm. Using R1, R2,...,Rm, and G1, G2,...,Gn to represent reviewers and proposal groups, respectively, if the ith proposal group is assigned to the jth reviewer, then the value of the corresponding element of the solution matrix is 1 or 0 otherwise. The combination of 0 and 1 variables in the matrix determines which proposal groups are as￾signed to which reviewers (as shown in Fig. 5). When the matrix is too sparse, another representation technique is used where the Initialize population P(t) based on GRASP Select parents from P(t) Apply crossover and mutation operator on parents to yield children Apply repair operator on infeasible children Use local search to improve the quality of children Evaluate the fitness of children to determine whether replace the individuals or not t=t+1 Stop criterion satified Stop Yes No Fig. 4. The structure of the hybrid GRASP and GA. 123 1 2 3 ... 1 0 1 ... 0 0 1 1 ... 0 1 1 0 ... 0 ... ... ... ... ... ... 0 0 1 ... 1 m n RRR R G G G G Fig. 5. Representation of an individual’s chromosome. 6952 Y. Xu et al. / Expert Systems with Applications 37 (2010) 6948–6956