效率异质型员工项目调度算法研究.pdfVIP

18 2011 ，47 （13） Computer Engineering and Applications 计算机工程与应用 效率异质型员工项目调度算法研究 1，2 1 柳春锋 ，杨善林 LIU Chunfeng1，2 ，YANG Shanlin1 1.合肥工业大学 管理学院，合肥 230009 2.浙江旅游职业学院，杭州 311231 1.School of Management ，Hefei University of Technology ，Hefei 230009 ，China 2.Tourism College of Zhejiang ，Hangzhou 311231 ，China LIU Chunfeng ，YANG Shanlin.Study on algorithm for project scheduling with heterogeneous efficiency workforce.Com- puter Engineering and Applications ，2011 ，47 （13）：18-21. Abstract ：Project scheduling with heterogeneous efficiency workforce to minimize project duration is considered ，and the cor- responding integer linear programming is presented.To solve the NP-hard problem ，a priority rule-based heuristic is proposed ， which selects the prior task-employee pair according to precedence constraints and priority rule to assign the task at each it- eration until all tasks are scheduled.A Hybrid Simulated Annealing （HSA ）can be constructed through applying the heuristic to generate initial schedule ，choosing the swap neighborhood structure and insertion neighborhood structure to obtain neighbor schedule ，and employing the revised forward recursion algorithm to compute objective function value.Numerical experiments are conducted to show that the proposed HSA performs well with respect to accuracy and efficiency of solution. Key words ：project scheduling ；heterogeneous efficiencies ；heuristic ；simulated annealing ；precedence constraints 摘 要：研究了员工具有异质效率、最小化项目工期的项目调度问题，并建立了相应的整数线性规划模型。为解决此NP-hard 问 题，提出了基于优先规则的启发式算法，其在每次迭代中根据优先约束和优先规则选择优先任务员工对以分配任务，直至所有任 务都完成调度。通过应用启发式算法生成初始调度，选用交换邻域结构和插入邻域结构产生邻域调度，并使用改进的前向递归 算法求解目标函数值，构造出混合模拟退火算法。数值实验显示该算法能快速准确地进行寻优。 关键词：项目调度；异质效率；启发式算法；模拟退火；优先约束 DOI：10.3778/j.issn. 1002-8331.2011.13.006 文章编号：1002-8331（2011）13-0018-04 文献标识码：A 中图分类号：O221；F406.2；TP301 1 前言 形，其中员工是多技能的，任务也需要多种技能。 项目调度和员工配置问