Y. Xu et al/ Expert Systems with Applications 37(2010)6948-6956 1"element is taken place by the code numbers of the reviewers, 2007: Feo Resende, 1995). The neighborhood structure N for a and"0"element is deleted to reduce the space size solution s to a specific problem is a subset of the solutions N(s).Gi- ven two solutions represented by two matrices p and g the differ 3.5.3.2. Initialization. The initial population is generated in the con- ence between p and q can be defined as: &(pq)=(i,D)lp(i, J) struction phase of GRASP. In the construction phase of GRASP, a * q(i,)), and the distance between p and g is defined to be feasible solution is iteratively constructed, one element at a time d(p, q)= 8(p, q) For the majority of GRASP, the most commonly (Aiex, Resende, Pardalos, Toraldo, 2005: Alvarez-Valdes, Crespo, used neighborhood structure is the so-called k-exchange neighbor- Tamarit,&Villa, 2008). The element added to the solution is ran- hood structure. The k-exchange neighborhood of a solution p can domly selected from a restricted candidate list(Resende, Mart, be defined allego, duarte, 2008), which is formed by ordering all candidate lements according to the benefit(here it is the matching degree p)={qld(p,q)≤k}, where2≤k≤min(n,m between a proposal group and a reviewer)of selecting this element This neighborhood structure is also employed in the proposed is above the threshold can be selected given a n m reviewer and method. However, the common exchange technique of just swap- proposal group assignment matrix P. a row index ie(1,.,n). and assignment problem because it leads to infeasible solutions. Thus a column indexjE[1,., m), and let X(P, i, j) be the following com- a new local search mechanism is proposed for this problem. patibility function Each step of the local search is composed of two operations X(P ii-1, for matrix p, assigning group i to reviewerjis allowed deleting and inserting operation. Deleting operation is based on lO. otherwise eliminating some nonzero elements and changing their values from X(P, i.) can be used as an index to determine whether assigning a forming an incomplete assignment matrix. The inserting operation proposal group to a reviewer is available. a candidate list is com- is based on completely constructing the incomplete assignment ment pair can be added to the candidate list. Chromosomes (or phase sing the constructing phase described in the initialization posed of all available elements. If X(P, ij)=1, then this(i, )assign- matrix solutions)are generated by iteratively adding available elements 3.5.3.6. Termination criteria. Genetic algorithm continues the above 3.5.3.3. The selection, crossover and mutation operator. The selection procedure until some predetermined criteria are achieved. Several operator determines from which chromosomes the next genera- criteria were commonly used in previous research, such as the tion will be generated(Michalewicz, 1996: Pezzella, Morganti, number of executed generation(Chen, Pan, Lin, 2008). a particu- Ciaschetti, 2008). It ensures that better members of the population lar objective function, and the homogeneity of the population (with higher fitness value)will have higher probability of being se-(Huang Lim, 2006). This research uses a fixed number of gener have a small probability of being selected. For this problem, the fit- ness value of the chromosome is measured by objective function in the assignment model. And the roulette wheel selection method 3.6. Step 6. Adjusting the assignment results (Hung, 2008) is used to select parents from population. The aim of crossover is to generate new individuals which The purpose of the proposed approach is to help managers to maintain some characteristics of their parents and at the meantime perform the reviewer assignment task efficiently and effectively extend the search space. The crossover scheme used here is similar Atter assignment results are obtained using the proposed ap to the traditional two-point crossover scheme in genetic algorithm proach, they can be checked and adjusted by managers according where the row position replacing the bit position to the specific funding policies. The mutation operator can maintain the diversity of the popu lation and prevent the premature convergence. In this algorithm, 4. System design and development the mutation operator can be described as follows: for any ran- domly selected individual expressed as a binary array, randomly This section describes the design and development of a prote select two column sites and interchange the values of the corre- type system for supporting reviewer assignment based on the ap- proach proposed in Section 3. The high level architecture of the system is shown in Fig. 6. The upper layer of the system provides 3.5.3.4. The repair operator. From the earlier mentioned crossover an interface for users who can access the system via the Web. It and mutation operator, it is obvious that constrains #(1)in the also enables users to adjust the assignment results based on the assignment model are always maintained, while constraints #(2) outcome provided by the system may be violated. So some infeasible solutions may be generated This system supports the whole proposal assignment process during the evolution process, and their proportion in the popula- through the fulfillment of six tasks: identifying valid proposals tion may become large. One way to deal with this is using a penalty and reviewers, classifying them according to their disciplines, par function method to guide the search direction because of its sim- titioning proposals into proposal groups based on the practical plicity and ease of implementation(Gen Cheng, 1997). But this needs of funding agencies, calculating the matching degree be- method cannot guarantee that constrains are satisfied and may tween each proposal group and reviewer, assigning proposal lead to infeasible results. Besides, a good penalty function is diffi- groups to reviewers, and adjusting the assignment results. In the ult to determine. Thus, a repair operator is used to fix infeasible phase of validity identification, valid proposals and reviewers are solutions and make them feasible, like using a greedy approach selected for further consideration. These valid proposals and to transfer the work of overloaded reviewers to others reviewers are classified according to their disciplines. Proposals are grouped based on funding policies and requirements. Then, 3.5.3.5. Local se search algorithm works by succe the matching degree between proposal groups and reviewers are searching a better solution in the neighborhood of the current solu- calculated using a matching model Based on the matching degre tion and replac e current solution(Boudia, Louly, Prins, proposal groups are assigned to reviewers. Also the managers‘‘1” element is taken place by the code numbers of the reviewers, and ‘‘0” element is deleted to reduce the space size. 3.5.3.2. Initialization. The initial population is generated in the con￾struction phase of GRASP. In the construction phase of GRASP, a feasible solution is iteratively constructed, one element at a time (Aiex, Resende, Pardalos, & Toraldo, 2005; Alvarez-Valdes, Crespo, Tamarit, & Villa, 2008). The element added to the solution is ran￾domly selected from a restricted candidate list (Resende, Martı´ , Gallego, & Duarte, 2008), which is formed by ordering all candidate elements according to the benefit (here it is the matching degree between a proposal group and a reviewer) of selecting this element and use a threshold to ensure that only the elements whose benefit is above the threshold can be selected. Given a n m reviewer and proposal group assignment matrix P, a row index i 2 {1,...,n}, and a column index j 2 {1,...,m}, and let X(P,i,j) be the following com￾patibility function: XðP;i;jÞ ¼ 1; for matrix p; assigning group i to reviewer j is allowed 0; otherwise X(P,i,j) can be used as an index to determine whether assigning a proposal group to a reviewer is available. A candidate list is com￾posed of all available elements. If X(P,i,j) = 1, then this (i,j) assign￾ment pair can be added to the candidate list. Chromosomes (or solutions) are generated by iteratively adding available elements. 3.5.3.3. The selection, crossover and mutation operator. The selection operator determines from which chromosomes the next genera￾tion will be generated (Michalewicz, 1996; Pezzella, Morganti, & Ciaschetti, 2008). It ensures that better members of the population (with higher fitness value) will have higher probability of being se￾lected for mating, while the worse members of the population still have a small probability of being selected. For this problem, the fit￾ness value of the chromosome is measured by objective function in the assignment model. And the roulette wheel selection method (Hung, 2008) is used to select parents from population. The aim of crossover is to generate new individuals which maintain some characteristics of their parents and at the meantime extend the search space. The crossover scheme used here is similar to the traditional two-point crossover scheme in genetic algorithm where the row position replacing the bit position. The mutation operator can maintain the diversity of the popu￾lation and prevent the premature convergence. In this algorithm, the mutation operator can be described as follows: for any ran￾domly selected individual expressed as a binary array, randomly select two column sites and interchange the values of the corre￾sponding two columns. 3.5.3.4. The repair operator. From the earlier mentioned crossover and mutation operator, it is obvious that constrains # (1) in the assignment model are always maintained, while constraints # (2) may be violated. So some infeasible solutions may be generated during the evolution process, and their proportion in the popula￾tion may become large. One way to deal with this is using a penalty function method to guide the search direction because of its sim￾plicity and ease of implementation (Gen & Cheng, 1997). But this method cannot guarantee that constrains are satisfied and may lead to infeasible results. Besides, a good penalty function is diffi- cult to determine. Thus, a repair operator is used to fix infeasible solutions and make them feasible, like using a greedy approach to transfer the work of overloaded reviewers to others. 3.5.3.5. Local search. A local search algorithm works by successively searching a better solution in the neighborhood of the current solu￾tion and replacing the current solution (Boudia, Louly, & Prins, 2007; Feo & Resende, 1995). The neighborhood structure N for a solution s to a specific problem is a subset of the solutions N(s). Gi￾ven two solutions represented by two matrices p and q, the differ￾ence between p and q can be defined as: d(p,q) = {(i,j)jp(i,j) – q(i,j)}, and the distance between p and q is defined to be: d(p,q) = jd(p,q)j. For the majority of GRASP, the most commonly used neighborhood structure is the so-called k-exchange neighbor￾hood structure. The k-exchange neighborhood of a solution p can be defined as NkðpÞ¼fqjdðp; qÞ 6 kg; where 2 6 k 6 minðn; mÞ This neighborhood structure is also employed in the proposed method. However, the common exchange technique of just swap￾ping k elements of the solution is not suitable for this reviewer assignment problem because it leads to infeasible solutions. Thus, a new local search mechanism is proposed for this problem. Each step of the local search is composed of two operations: deleting and inserting operation. Deleting operation is based on eliminating some nonzero elements and changing their values from one to zero in a complete group-reviewer assignment matrix, forming an incomplete assignment matrix. The inserting operation is based on completely constructing the incomplete assignment matrix using the constructing phase described in the initialization phase. 3.5.3.6. Termination criteria. Genetic algorithm continues the above procedure until some predetermined criteria are achieved. Several criteria were commonly used in previous research, such as the number of executed generation (Chen, Pan, & Lin, 2008), a particu￾lar objective function, and the homogeneity of the population (Huang & Lim, 2006). This research uses a fixed number of gener￾ations as the stopping rule. 3.6. Step 6. Adjusting the assignment results The purpose of the proposed approach is to help managers to perform the reviewer assignment task efficiently and effectively. After assignment results are obtained using the proposed ap￾proach, they can be checked and adjusted by managers according to the specific funding policies. 4. System design and development This section describes the design and development of a proto￾type system for supporting reviewer assignment based on the ap￾proach proposed in Section 3. The high level architecture of the system is shown in Fig. 6. The upper layer of the system provides an interface for users who can access the system via the Web. It also enables users to adjust the assignment results based on the outcome provided by the system. This system supports the whole proposal assignment process through the fulfillment of six tasks: identifying valid proposals and reviewers, classifying them according to their disciplines, par￾titioning proposals into proposal groups based on the practical needs of funding agencies, calculating the matching degree be￾tween each proposal group and reviewer, assigning proposal groups to reviewers, and adjusting the assignment results. In the phase of validity identification, valid proposals and reviewers are selected for further consideration. These valid proposals and reviewers are classified according to their disciplines. Proposals are grouped based on funding policies and requirements. Then, the matching degree between proposal groups and reviewers are calculated using a matching model. Based on the matching degree, proposal groups are assigned to reviewers. Also the managers Y. Xu et al. / Expert Systems with Applications 37 (2010) 6948–6956 6953