基于小生境遗传算法的技能型员工调度方法

Skilled staff scheduling method based on niche genetic algorithm

研究软件项目开发中一类完全技能型效率异质的员工调度问题,以最短工期为目标建立了相应的整数线性规划模型。为了解决此NP-hard问题,提出一种改进的小生境遗传算法,其在每次迭代中计算当代种群中任意两个个体的汉明距离并给出一个惩罚函数,当两个个体之间的距离小于指定值时,较大个体的适应度值由惩罚函数计算,依据适应度值大小排序选择较小的个体进入下一代,以此形成改进的小生境遗传算法,该算法的优点是在每次迭代中保留了种群的多样性。使用文献中软件开发项目案例,验证了算法的有效性,结果表明该小生境遗传算法的调度结果更优,可达到精确求解法的目标值,并能提供其他最优解。

A kind of workforce scheduling problem with fuU-skill and heterogeneous efficiency was studied in the paper for software development program, and an integer linear programming model was presented. A modified Niche Genetic Algorithm （NGA） was proposed to solve this NP-hard problem, which calculated the Hamming distance between any two individuals in the population and gave a penalty function. If the distance between two individuals was less than the specified value, the larger individual was computed by the penalty function and the smaller individual was sorted relying on fitness value. Finally, NGA selected smaller individual into the next generation and maintained the diversity of population in each iteration. A case taken from a literature was used as a benchmark to verify the scheduling performance of the proposed algorithm. The results demonstrate that the proposed algorithm is better than the algorithm in the literature, and achieves the target value of exact solution and can provide other optimal solutions.