基于粒子群算法的知识员工任务指派及调度优化
|
摘要
众所周知，知识员工任务指派及调度是NP-HARD问题，科学合理的进行知识员工任务指派及调度是企业人力资源合理配置的重要组成活动。本文详细描述了知识员工任务指派及调度研究问题，并明确了问题假设；构建了研究问题的数学模型，同时提出了基于粒子群算法进行知识员工任务指派及调度优化求解策略。在设计仿真程序时，采取了一种直观的借鉴遗传算法的矩阵编码方法，可以充分利用粒子群算法的并行搜索能力。本文主要的研究内容以及成果如下：
（1）首先结合国内外已有的文献，系统总结了知识员工任务指派及调度以及粒子群算法的研究现状，在此过程中发现较少利用粒子群算法来对知识员工任务指派及调度问题进行研究。
（2）分析总结了知识员工的定义、特征、知识员工任务指派及调度对企业的意义以及知识员工任务指派及调度过程中的难点，依据知识员工任务指派及调度优化的特点建立了相关的优化数学模型，为解决该类问题提供了科学依据。
（3）受粒子群算法应用解决车间作业调度问题的启发，本文探索性的将粒子群算法运用于知识员工任务指派及调度优化问题，并详细的阐述了粒子群算法的概念和基本原理，同时构建了基于粒子群算法的知识员工任务指派及调度优化的算法模型。
（4）基于MATLAB7.0平台建立知识员工任务指派调度决策仿真系统，案例的实证结果表明通过设置适当的参数，粒子群算法可以快速的得到一个较优的排序结果，同时也验证了粒子群算法是一种求解知识员工任务指派及调度问题的有效方法。
Task allocation and scheduling for knowledge workers is known as an NP-hard problem.Scientific task allocation and scheduling for knowledge workers is an important part of rationalhuman resources management in enterprises. This paper gives a detailed description of theresearch problem of task allocation and scheduling for knowledge workers. It also gives theproblem an explicit assumption. Besides，this paper builds a mathematical model of the questionand proposes a constraint problem to solve task allocation and scheduling for knowledgeworkers based on particle swarm optimization (PSO). When designing the simulation program ofthe problem，this paper takes a visual matrix encoding method that draws lessons from the geneticalgorithm，because the method can take advantage of the parallel search capability of the particleswarm algorithm.
The content studied and conclusions drawn are as follows:
(1) This dissertation first reviews the domestic and foreign studies of task allocation andscheduling for knowledge workers. Besides, it gives the state of the field for PSO. In the process，using the PSO to study task allocation and knowledge workers scheduling is rarely found.
(2) On the basis of the research of the definition and characteristics of knowledge workers，thepaper analyzes and summarizes the importance of task allocation and scheduling for knowledgeworkers for enterprises. In allusion to the characteristics of task allocation and scheduling forknowledge workers，this dissertation establishes a mathematical model of task allocation andscheduling for knowledge workers.
(3) In this paper，PSO is used to solve task allocation and scheduling for knowledge workers. Theconcept and principle of the PSO are elaborated. At the same time, this paper builds a algorithmicmodel of task allocation and scheduling for knowledge workers.
(4) Decision system about task allocation and scheduling for knowledge workers is built， whichis based on MATLAB7.0platform. The empirical case confirms that PSO is an effective methodof solving the problem of task allocation and scheduling for knowledge workers.
（1）首先结合国内外已有的文献，系统总结了知识员工任务指派及调度以及粒子群算法的研究现状，在此过程中发现较少利用粒子群算法来对知识员工任务指派及调度问题进行研究。
（2）分析总结了知识员工的定义、特征、知识员工任务指派及调度对企业的意义以及知识员工任务指派及调度过程中的难点，依据知识员工任务指派及调度优化的特点建立了相关的优化数学模型，为解决该类问题提供了科学依据。
（3）受粒子群算法应用解决车间作业调度问题的启发，本文探索性的将粒子群算法运用于知识员工任务指派及调度优化问题，并详细的阐述了粒子群算法的概念和基本原理，同时构建了基于粒子群算法的知识员工任务指派及调度优化的算法模型。
（4）基于MATLAB7.0平台建立知识员工任务指派调度决策仿真系统，案例的实证结果表明通过设置适当的参数，粒子群算法可以快速的得到一个较优的排序结果，同时也验证了粒子群算法是一种求解知识员工任务指派及调度问题的有效方法。
Task allocation and scheduling for knowledge workers is known as an NP-hard problem.Scientific task allocation and scheduling for knowledge workers is an important part of rationalhuman resources management in enterprises. This paper gives a detailed description of theresearch problem of task allocation and scheduling for knowledge workers. It also gives theproblem an explicit assumption. Besides，this paper builds a mathematical model of the questionand proposes a constraint problem to solve task allocation and scheduling for knowledgeworkers based on particle swarm optimization (PSO). When designing the simulation program ofthe problem，this paper takes a visual matrix encoding method that draws lessons from the geneticalgorithm，because the method can take advantage of the parallel search capability of the particleswarm algorithm.
The content studied and conclusions drawn are as follows:
(1) This dissertation first reviews the domestic and foreign studies of task allocation andscheduling for knowledge workers. Besides, it gives the state of the field for PSO. In the process，using the PSO to study task allocation and knowledge workers scheduling is rarely found.
(2) On the basis of the research of the definition and characteristics of knowledge workers，thepaper analyzes and summarizes the importance of task allocation and scheduling for knowledgeworkers for enterprises. In allusion to the characteristics of task allocation and scheduling forknowledge workers，this dissertation establishes a mathematical model of task allocation andscheduling for knowledge workers.
(3) In this paper，PSO is used to solve task allocation and scheduling for knowledge workers. Theconcept and principle of the PSO are elaborated. At the same time, this paper builds a algorithmicmodel of task allocation and scheduling for knowledge workers.
(4) Decision system about task allocation and scheduling for knowledge workers is built， whichis based on MATLAB7.0platform. The empirical case confirms that PSO is an effective methodof solving the problem of task allocation and scheduling for knowledge workers.
引文
[1] Peter F Druck. The landmarks of tomorrow[M]. New York：Harper&Row，1959
[2] Michael R Garey，David S Johnson. Computers and intractability：a guide to the theory ofNP-completeness[M]. New York：W. H. FREEMAN AND COMPANY，1979
[3] Srimathy Mohan. Scheduling Part-time Personnel with Availability Restrictions andPreferences to Maximize Employee Satisfaction[J]. Mathematical and Computer Modelling，2008，48(11):1806-1813
[4] Armann Ingolfsson Fernanda Campello， Xudong Wu， Edgar Cabral.Combining IntegerProgramming and the Randomization Method to Schedule Employees[J]. European Journalof Operational Research，2010，202(1):153-163
[5] O. Guyon， P. Lemaire，é. Pinson，D. Rivreau.Cut Generation for an Integrated EmployeeTimetabling and Production Scheduling Problem[J].European Journal of OperationalResearch，2010，201(2):557-567
[6] Ken Darby-Dowman， James Little，Gautam Mitra and Marco Zaffalon， Constraint LogicProgramming and Integer Programming approaches and their collaboration in solving anassignment scheduling problem[J]，Constraints，1997.3:245-264
[7] Stéfan J. Darmoni，Alain Fajner，Nathalie Mahé，Arnaud Leforestier，Marc Vondracek，Olivier Stelian and Michel Baldenweck.Horoplan: Computer-Assisted Nurse SchedulingUsing Constraint Based Programming[J]，Journal of the Society for Health Systems，1995.1:41-54
[8]秦学志，王雪华.一类最优指派问题的动态规划模型[J].数学的实践与认识，1996（3）：70-73
[9]黄德才.求广义指派决策问题最优解的有效算法[J].控制与决策，1999，14（3）：272-275
[10] X. Cai，K. N. Li.A Genetic Algorithm for Scheduling Staff of Mixed Skills underMulti-criteria [J].European Journal of Operational Research，2000，125(2)：359-369
[11] K. Bouleimen， H. Lecocq. A new efficient simulated annealing algorithm for theresource-constrained project scheduling problem and its multiple mode version[J]. EuropeanJournal of Operational Research，2003（9）：268-281
[12] Uwe Aickelin，Kathryn A. Dowsland.An indirect Genetic Algorithm for a nurse-schedulingproblem[J].Computers&Operations Research，2004（4）：761-778
[13] Walter J. Gutjahr， Marion S. Rauner， An ACO algorithm for a dynamic regionalnurse-scheduling problem in Austria[J]. Computers&Operations Research，2007（3）：642-666
[14] J. Heinonen，F. Pettersson.Hybrid ant colony optimization and visibility studies applied to ajob-shop scheduling problem[J].Applied Mathematics and Computation，2007（4）：989-998
[15] Deng Kui Huanga，Huan Neng Chiub，Ruey Huei Yeha and Jen Huei Changc.A fuzzymulti-criteria decision making approach for solving a bi-objective personnel assignmentproblem[J].Computers&Industrial Engineering，2009（2）：1-10
[16]郭定刚.谈基于遗传算法的航空项目管理资源优化技术研究[D].陕西：西北工业大学，2004
[17]李远敏，陈帆.软件项目管理中人员调度研究[J].微计算机应用，2005，26（2）：142-145
[18]谈文芳，赵强，余胜阳，肖人彬.改进粒子群优化算法求解任务指派问题[J].计算机应用，2007，27（12）：2892-2895
[19]李响，王庆.基于混合遗传算法的农机科研人员任务调度优化研究[J].中国农机化，2008（1）：49-52
[20]时维国，薛倩.求解Job-Shop车间作业调度的混合算法[J].大连交通大学学报，2009（4）：30-34
[21]王静宇，谭跃生，陈振江.基于遗传蚁群混合算法的网格任务调度研究[J].计算机与信息技术，2010（6）：101-105
[22] Seyda Topaloglu.Irem Ozkarahan.An implicit goal programming model for the tourscheduling problem considering the employee work preferences[J]. Annals of OperationsResearch，2004，128（1-4）：135-158
[23] Subhash C Sarin，Sanjay Aggarwal.Modeling and algorithmic development of a staffproblem scheduling[J]. European Journal of Operational Research，2001，128（3）：558-569
[24] Faizul Huq，Kenneth Cutright，Clarence MARTIN.Employee scheduling and makespanminimization in a flow shop with multi-processor work stations：a case study[J]. Omega，2004，32（2）：121-129
[25] Gary M Thompson.A simulated-annealing heuristic for shift scheduling usingnon-continuously available employees[J]. Computers and Operations Research，1996，23（3）：275-288
[26]王庆.知识型企业知识员工任务指派及调度决策问题研究[D].天津：天津大学，2006
[27] Kathryn A Dowsland. Nurse scheduling with tabu search and strategic oscillation[J].European Journal of Operational Research，1998，106（2-3）：393-407
[28]高尚，韩斌，吴小俊.求解旅行商问题的混合粒子群优化算法[J].控制与决策，2004，19(11):1286–1289
[29]钟一文，杨建刚，宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践，2006（6）：88-94
[30]陈文兰，戴树贵.旅行商问题算法研究综述[J].滁州学院学报，2006（3）：1-6
[31]苏晋荣，王建珍.改进粒子群优化算法求解TSP问题[J].计算机工程与应用，2010，46(4)：52-53
[32]朱道飞.钢厂生产作业计划与调度的自组织优化方法研究[D].重庆：重庆大学，2008
[33]高尚，杨静宇.求解流水作业调度问题的混合粒子群优化算法[A].2006中国控制与决策学术年会论文集[C].2006
[34] Cagnina L，Esquivel S，Gallard R.Particle swarmoptimization for sequencing problems: Acase study[A].Proceeding of the2004Congress on Evolutionary Computation[C].USA.2004：536-541
[35]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2001
[36]肖健梅，黄有方，李军军，王锡淮.基于离散微粒群优化的物流配送车辆路径问题[J].系统工程，2005，23(4)：97-100
[37]刘智勇.智能交通控制理论及其应用[M].北京：科学出版社，2003
[38]董超俊，刘智勇，邱祖廉.灾变粒子群优化算法及其在交通控制中的应用[J].计算机工程与应用.2005，41(29)：19-23
[39]王相军，杜波.基于交通信号的智能交通系统的粒子群控制算法[J].科技信息，2008(15)：359-364
[40]李宁，邹彤，孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践，2004.24(4)：130-135
[41]陈曦.基于免疫粒子群优化算法的多约束路由选择算法[J].长沙交通学院学报，2006，22(2)：66-69
[42]陆琳.不确定信息车辆路径问题及其算法研究[D].江苏：南京航空航天大学，2007
[43]裴振奎，刘健，华夏.求解随机车辆路径规划问题的混合微粒群算法[A].2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C].2008
[44]李云峰.卫星—地面站数传调度模型及算法研究[D].湖南：国防科学技术大学，2008
[45]冯林，张名举，贺明峰，戚正君.用改进的粒子群算法实现多模态刚性医学图像的配准[J].计算机辅助设计与图形学学报，2004，16(9)：1269-1274
[46]林晓梅，吕珊珊，朱丹，王爽爽.基于神经网络──粒子群优化算法的医学图像分割新方法[J].长春工业大学学报(自然科学版)，2008，29(2)：72-75
[47]高尚，韩斌，吴小俊.求解旅行商问题的混合粒子群算法[J].控制与决策，2004，19（11)：1286-1289
[48]谭皓，沈春林，李锦.混合粒子群算法在高维复杂函数寻优中的应用[J].系统工程与电子技术，2005.27(8)：1471-1474
[49]吴茜，郑金华，宋武.改进的粒子群算法求解非线性约束优化问题[J].计算机工程与应用，2007(24)：61-64
[50]雷德明，吴智铭.基于粒子群优化的多目标作业车间调度[J].上海交通大学学报，2007(11)：1796-1800
[51]何利，刘永贤，谢华龙，刘笑天.基于粒子群算法的车间调度与优化[J].东北大学学报（自然科学版），2008(4)：565-568
[52]欧微，邹逢兴，高政，徐晓红.基于多目标粒子群算法的混合流水车间调度方法研究[J].计算机工程与科学，2009，31(8)：52-56
[53]苌娟.我国企业知识员工流失管理[D].湖北：武汉理工大学，2005
[54]弗朗西斯·赫瑞比著，郑晓明等译.管理知识员工[M].北京：机械工业出版社，2000
[55]杨杰，凌文较，方俐洛.关于知识工作者与知识性工作的实证解析[J].科学研究，2004（2）：190一196
[56]张京.知识员工绩效结构及影响因素研究[D].湖北：中国地质大学，2009
[57]廖建桥，文鹏.知识员工定义、特征及分类研究述评[J].管理学报，2009，6(2)：277-283
[58]田家华，张光进，姜炜.知识员工考评方法的权变选择研究：绩效特征的视角[J].中国地质大学学报（社会科学版），2008(1)：64-69
[59]彭剑锋，张望军.如何激励知识型员工[J].中国人力资源开发，1999(9)：12-14
[60]陈国颂.Y时代知识员工管理的策略研究[D].上海：华东师范大学，2010
[61]汤舒俊.论企业知识型员工的特点与激励[J].现代商贸工业，2010(9)：131-132
[2] Michael R Garey，David S Johnson. Computers and intractability：a guide to the theory ofNP-completeness[M]. New York：W. H. FREEMAN AND COMPANY，1979
[3] Srimathy Mohan. Scheduling Part-time Personnel with Availability Restrictions andPreferences to Maximize Employee Satisfaction[J]. Mathematical and Computer Modelling，2008，48(11):1806-1813
[4] Armann Ingolfsson Fernanda Campello， Xudong Wu， Edgar Cabral.Combining IntegerProgramming and the Randomization Method to Schedule Employees[J]. European Journalof Operational Research，2010，202(1):153-163
[5] O. Guyon， P. Lemaire，é. Pinson，D. Rivreau.Cut Generation for an Integrated EmployeeTimetabling and Production Scheduling Problem[J].European Journal of OperationalResearch，2010，201(2):557-567
[6] Ken Darby-Dowman， James Little，Gautam Mitra and Marco Zaffalon， Constraint LogicProgramming and Integer Programming approaches and their collaboration in solving anassignment scheduling problem[J]，Constraints，1997.3:245-264
[7] Stéfan J. Darmoni，Alain Fajner，Nathalie Mahé，Arnaud Leforestier，Marc Vondracek，Olivier Stelian and Michel Baldenweck.Horoplan: Computer-Assisted Nurse SchedulingUsing Constraint Based Programming[J]，Journal of the Society for Health Systems，1995.1:41-54
[8]秦学志，王雪华.一类最优指派问题的动态规划模型[J].数学的实践与认识，1996（3）：70-73
[9]黄德才.求广义指派决策问题最优解的有效算法[J].控制与决策，1999，14（3）：272-275
[10] X. Cai，K. N. Li.A Genetic Algorithm for Scheduling Staff of Mixed Skills underMulti-criteria [J].European Journal of Operational Research，2000，125(2)：359-369
[11] K. Bouleimen， H. Lecocq. A new efficient simulated annealing algorithm for theresource-constrained project scheduling problem and its multiple mode version[J]. EuropeanJournal of Operational Research，2003（9）：268-281
[12] Uwe Aickelin，Kathryn A. Dowsland.An indirect Genetic Algorithm for a nurse-schedulingproblem[J].Computers&Operations Research，2004（4）：761-778
[13] Walter J. Gutjahr， Marion S. Rauner， An ACO algorithm for a dynamic regionalnurse-scheduling problem in Austria[J]. Computers&Operations Research，2007（3）：642-666
[14] J. Heinonen，F. Pettersson.Hybrid ant colony optimization and visibility studies applied to ajob-shop scheduling problem[J].Applied Mathematics and Computation，2007（4）：989-998
[15] Deng Kui Huanga，Huan Neng Chiub，Ruey Huei Yeha and Jen Huei Changc.A fuzzymulti-criteria decision making approach for solving a bi-objective personnel assignmentproblem[J].Computers&Industrial Engineering，2009（2）：1-10
[16]郭定刚.谈基于遗传算法的航空项目管理资源优化技术研究[D].陕西：西北工业大学，2004
[17]李远敏，陈帆.软件项目管理中人员调度研究[J].微计算机应用，2005，26（2）：142-145
[18]谈文芳，赵强，余胜阳，肖人彬.改进粒子群优化算法求解任务指派问题[J].计算机应用，2007，27（12）：2892-2895
[19]李响，王庆.基于混合遗传算法的农机科研人员任务调度优化研究[J].中国农机化，2008（1）：49-52
[20]时维国，薛倩.求解Job-Shop车间作业调度的混合算法[J].大连交通大学学报，2009（4）：30-34
[21]王静宇，谭跃生，陈振江.基于遗传蚁群混合算法的网格任务调度研究[J].计算机与信息技术，2010（6）：101-105
[22] Seyda Topaloglu.Irem Ozkarahan.An implicit goal programming model for the tourscheduling problem considering the employee work preferences[J]. Annals of OperationsResearch，2004，128（1-4）：135-158
[23] Subhash C Sarin，Sanjay Aggarwal.Modeling and algorithmic development of a staffproblem scheduling[J]. European Journal of Operational Research，2001，128（3）：558-569
[24] Faizul Huq，Kenneth Cutright，Clarence MARTIN.Employee scheduling and makespanminimization in a flow shop with multi-processor work stations：a case study[J]. Omega，2004，32（2）：121-129
[25] Gary M Thompson.A simulated-annealing heuristic for shift scheduling usingnon-continuously available employees[J]. Computers and Operations Research，1996，23（3）：275-288
[26]王庆.知识型企业知识员工任务指派及调度决策问题研究[D].天津：天津大学，2006
[27] Kathryn A Dowsland. Nurse scheduling with tabu search and strategic oscillation[J].European Journal of Operational Research，1998，106（2-3）：393-407
[28]高尚，韩斌，吴小俊.求解旅行商问题的混合粒子群优化算法[J].控制与决策，2004，19(11):1286–1289
[29]钟一文，杨建刚，宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践，2006（6）：88-94
[30]陈文兰，戴树贵.旅行商问题算法研究综述[J].滁州学院学报，2006（3）：1-6
[31]苏晋荣，王建珍.改进粒子群优化算法求解TSP问题[J].计算机工程与应用，2010，46(4)：52-53
[32]朱道飞.钢厂生产作业计划与调度的自组织优化方法研究[D].重庆：重庆大学，2008
[33]高尚，杨静宇.求解流水作业调度问题的混合粒子群优化算法[A].2006中国控制与决策学术年会论文集[C].2006
[34] Cagnina L，Esquivel S，Gallard R.Particle swarmoptimization for sequencing problems: Acase study[A].Proceeding of the2004Congress on Evolutionary Computation[C].USA.2004：536-541
[35]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2001
[36]肖健梅，黄有方，李军军，王锡淮.基于离散微粒群优化的物流配送车辆路径问题[J].系统工程，2005，23(4)：97-100
[37]刘智勇.智能交通控制理论及其应用[M].北京：科学出版社，2003
[38]董超俊，刘智勇，邱祖廉.灾变粒子群优化算法及其在交通控制中的应用[J].计算机工程与应用.2005，41(29)：19-23
[39]王相军，杜波.基于交通信号的智能交通系统的粒子群控制算法[J].科技信息，2008(15)：359-364
[40]李宁，邹彤，孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践，2004.24(4)：130-135
[41]陈曦.基于免疫粒子群优化算法的多约束路由选择算法[J].长沙交通学院学报，2006，22(2)：66-69
[42]陆琳.不确定信息车辆路径问题及其算法研究[D].江苏：南京航空航天大学，2007
[43]裴振奎，刘健，华夏.求解随机车辆路径规划问题的混合微粒群算法[A].2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C].2008
[44]李云峰.卫星—地面站数传调度模型及算法研究[D].湖南：国防科学技术大学，2008
[45]冯林，张名举，贺明峰，戚正君.用改进的粒子群算法实现多模态刚性医学图像的配准[J].计算机辅助设计与图形学学报，2004，16(9)：1269-1274
[46]林晓梅，吕珊珊，朱丹，王爽爽.基于神经网络──粒子群优化算法的医学图像分割新方法[J].长春工业大学学报(自然科学版)，2008，29(2)：72-75
[47]高尚，韩斌，吴小俊.求解旅行商问题的混合粒子群算法[J].控制与决策，2004，19（11)：1286-1289
[48]谭皓，沈春林，李锦.混合粒子群算法在高维复杂函数寻优中的应用[J].系统工程与电子技术，2005.27(8)：1471-1474
[49]吴茜，郑金华，宋武.改进的粒子群算法求解非线性约束优化问题[J].计算机工程与应用，2007(24)：61-64
[50]雷德明，吴智铭.基于粒子群优化的多目标作业车间调度[J].上海交通大学学报，2007(11)：1796-1800
[51]何利，刘永贤，谢华龙，刘笑天.基于粒子群算法的车间调度与优化[J].东北大学学报（自然科学版），2008(4)：565-568
[52]欧微，邹逢兴，高政，徐晓红.基于多目标粒子群算法的混合流水车间调度方法研究[J].计算机工程与科学，2009，31(8)：52-56
[53]苌娟.我国企业知识员工流失管理[D].湖北：武汉理工大学，2005
[54]弗朗西斯·赫瑞比著，郑晓明等译.管理知识员工[M].北京：机械工业出版社，2000
[55]杨杰，凌文较，方俐洛.关于知识工作者与知识性工作的实证解析[J].科学研究，2004（2）：190一196
[56]张京.知识员工绩效结构及影响因素研究[D].湖北：中国地质大学，2009
[57]廖建桥，文鹏.知识员工定义、特征及分类研究述评[J].管理学报，2009，6(2)：277-283
[58]田家华，张光进，姜炜.知识员工考评方法的权变选择研究：绩效特征的视角[J].中国地质大学学报（社会科学版），2008(1)：64-69
[59]彭剑锋，张望军.如何激励知识型员工[J].中国人力资源开发，1999(9)：12-14
[60]陈国颂.Y时代知识员工管理的策略研究[D].上海：华东师范大学，2010
[61]汤舒俊.论企业知识型员工的特点与激励[J].现代商贸工业，2010(9)：131-132