服务系统中的多技能人员调度

自21世纪以来，信息技术的飞速发展和广泛普及在推动传统行业改造和升级的同时也催生了许多新型服务业，服务业的广度和深度得到了大大加强，服务业已成为我国社会经济增长的主动力。人力资源是组织的资源，在服务型组织中更是如此。而且，因为教育经历、社会阅历、工作经历以及个人自身的心理和生理特征等方面的综合因素决定了“人”这一类资源具有天然的多技能特征，尤其是在组织的人力资源开发基础上的资源更是如此。在服务组织的日常运营管理中，如何结合服务需求特征进行多技能人员分配和任务调度是服务系统的一类非常关键的问题，有效的多技能人员分配和任务调度方法能促使服务组织提高服务水平，提升服务效率，降低服务成本，甚至能提升服务组织中人员的个人价值。
结合服务系统运作管理的实践需要，已有大量有关人员调度的研究成果，研究的应用出现在信息技术服务、医疗健康服务、设备维护服务、居家养老服务、安保巡检服务、生产制造服务等领域中。对于多技能人员调度的研究和应用也是近年来人们的关注点之一。作者近十年来一直从事面向IT服务、健康服务、社会化养老服务、物流服务等应用领域的研究、开发与实践工作，在这些工作中对多技能人员调度有较多的思考，先后以项目型服务、独立型任务、同服务对象时序关系型任务等需求下的服务系统为对象，基于服务分类分别研究了其中的多类多技能人员调度问题，这些研究工作通过基于服务任务关联特征的服务分类这一主线有效地串联起来，具有一定的系统性。从而，作者得以在此基础上结合相关文献的研究成果终集结成本书。
全书共分为8章。第1章中，基于人力资源在服务运作管理中作用的讨论，提出了考虑不同服务任务关联特征的服务分类方法，从而在这种服务分类方法下针对各类多技能人员调度问题展开讨论。后续各章中，基于项目型服务驱动的问题在第2~5章讨论，基于独立型服务任务驱动的问题在第6~7章讨论，基于同服务对象的时序关系型任务驱动的问题在第8章讨论。第2章以工期小化为目标，讨论了多技能人员分配与项目调度问题，分别考虑了任务不可中断和可中断特征； 第3章在第2章的基础上，考虑了多技能人员的个人价值目标——人尽其才，构造了多目标多技能人员调度问题模型，开发了有效的多目标算法； 第4章则从现实项目管理背景出发，在多技能人员分配和项目调度中考虑了资源转移时间问题； 第5章以IT开发项目中的服务外包为典型对象，研究提出了多技能主体下的项目调度与协调方法； 第6章以服务对象所提出的独立服务任务为驱动，考虑 “互联网 ”背景下线下的多服务站情形，讨论了多服务站多技能人员调度问题； 第7章则是汇集服务对象的独立型服务需求，从而形成对服务人员的需求特征，在这种结构下讨论服务系统的多层级人员调度问题； 第8章是一类人员调度与路径规划协同优化问题，以典型的家庭医生服务为背景，阐述了同一服务对象多种时序关系任务情形下的巡访服务人员调度问题。
本书由刘振元总体策划，参与研究并撰写本书各章节的人员具体分工如下： 第 1章由刘振元、袁慧涛、刘在盛撰写，第 2章由袁慧涛、周成、刘振元、廖广锐、毕阳撰写，第 3章由周成、刘振元、程璐、熊体凡撰写，第 4章由杨柳、刘振元、袁慧涛、熊体凡撰写，第 5章由袁慧涛、刘振元、杨柳、熊体凡撰写，第 6章由朱志鹏、刘振元、周跃、刘在盛、蒋光建撰写，第 7章由刘在盛、刘振元、朱志鹏、董骏武撰写，第 8章由王俊、刘振元、刘在盛、邵义舜、余晶撰写。全文由刘振元统稿。
本书的各部分内容是作者多年来研究的工作积累，书稿的策划及撰写历时近四年。在本书撰写过程中得到了来自中国运筹学会排序专业委员会、医疗运作管理分会等的大力支持，特别感谢唐国春、万国华、吴贤毅、沈吟东等在《排序与调度丛书》建设过程中不辞辛劳的精心组织和持续指导，感谢清华大学王凌教授、东北大学刘士新教授百忙之中多次审稿，感谢丛书编委会及调度领域其他老师所给予的支持和帮助。本书所涉各项研究及书稿撰写工作也得到了华中科技大学人工智能与自动化学院各位领导以及费奇、陈学广、王红卫等的长期指导与帮助，在此向他们致以深深的谢意！尽管各项研究和成稿过程历时较长，但家人给予了持续的理解与支持，在此也表示感谢！
本书相关研究先后得到了国家自然科学基金面上项目（71071062）、*留学回国人员科研启动基金项目、中央高校基本科研业务费资助项目（HUST: 2017KFYXJJ178； HUST： 2013TS130）、武汉市第四批“黄鹤英才计划”入选人才项目“慧帮医联网平台构建与智慧健康服务应用”等的资助，在此也要向资助各方表示感谢！另外，感谢《排序与调度丛书》编委会对我的鼓励与认可。后，还要特别感谢清华大学出版社以及本书的责任编辑，是他们的精心策划和耐心帮助促成了本书的顺利出版。
本书的撰写力求理论与实践相结合，一方面能从理论上比较系统地梳理出一套服务系统的多技能人员调度模型与方法，另一方面能从我国各类服务组织中抽取相应的案例来予以辅证。但因为作者水平有限，从撰写组织到编辑出版过程仍觉时间紧迫，有些内容还有待完善和深入研究，对于不足之处，敬请读者批评指正！

作者2018年12月

本书以基于服务任务关联特征的服务分类为主线，分别从项目型服务、独立型任务、同服务对象时序关系型任务等方面，结合实际的信息技术服务、医疗健康服务等服务系统背景，讨论了一系列服务系统中的多技能人员调度问题，从提高服务水平、提升服务效率、降低服务成本甚至提升服务人员的自身价值等多种维度，建立问题的单目标、多目标甚至高维多目标模型，提出优化调度算法，经计算实验设计和实施验证算法的有效性。全书内容的展开遵循理论与实践相结合的原则，从实际应用出发提炼服务系统人员调度的问题要素，站在一般意义的视角提出问题、分析问题、解决问题，从而得出具有现实意义和理论意义的结论。 本书可作为排序与调度、服务运作管理、系统工程、软件工程、卫生服务管理、互联网服务等相关课程的教学参考，也可供各类服务领域的从业者、以服务系统为研究背景或以排序与调度为研究问题的研究者学习参考。

作者于2005年12月取得华中科技大学系统工程专业博士学位，自1998年始在华中科技大学任教，先后主持了多项工程应用研发项目和国家自然科学基金、湖北省自然科学基金、*留学回国人员科研启动基金、图像信息与智能控制*重点实验室开放基金、华中科技大学自主创新基金等基础研究项目。获2项国家科技进步二等奖、1项全国企业管理现代化创新成果奖和3项省部级科技进步奖、华中科技大学优秀博士学位论文奖、湖北省自然科学优秀论文二等奖，取得软件著作权4项，出版专著2部，在国际国内学术期刊以及重要学术会议上发表学术论文70余篇，SCI、EI收录30余篇。

1.1引言

1.2服务运作管理与人力资源

1.2.1组织与运作管理

1.2.2服务与服务分类

1.2.3资源与人力资源

1.3人员调度问题分类与应用领域

1.3.1人员的技能

1.3.2人员调度问题分类

1.3.3人员调度应用领域

1.4项目调度问题分类与求解方法

1.4.1项目调度问题描述

1.4.2项目调度问题分类

1.4.3项目调度问题的求解方法

1.5本书的篇章结构

第2章多技能人员分配与项目调度

2.1引言

2.2研究现状分析

2.2.1多技能资源项目调度

2.2.2任务可中断项目调度

2.3多技能人员分配与任务不可中断项目调度

2.3.1问题描述

2.3.2问题建模

2.3.3Rollout算法

2.3.4计算实验与分析

2.4多技能人员分配与任务可中断项目调度

2.4.1问题描述

2.4.2问题建模

2.4.3Rollout算法

2.4.4分支定界算法

2.4.5计算实验与分析

2.5本章小结

第3章多目标多技能人员分配与项目调度

3.1引言

3.2研究现状分析

3.3问题描述与建模

3.3.1问题描述

3.3.2问题建模

3.3.3问题实例

3.4基本多目标遗传算法

3.4.1算法流程

3.4.2染色体编码及解码

3.4.3适应度函数

3.4.4选择、交叉及变异

3.5混合免疫遗传算法

3.5.1算法概述

3.5.2算法流程

3.5.3“双岛模型”及接种过程

3.6引入NSGAⅡ选择机制的增强免疫遗传算法

3.6.1NSGAⅡ

3.6.2增强免疫遗传算法

3.7计算实验与分析

3.7.1实验案例

3.7.2结果分析

3.8本章小结

第4章考虑资源转移时间的多技能人员分配与项目调度

4.1引言

4.2研究现状分析

4.3问题描述与建模

4.3.1问题描述

4.3.2问题建模

4.4基于优先规则的启发式算法

4.4.1串行调度算法

4.4.2并行调度算法

4.4.3任务优先规则和资源转移优先规则

4.4.4随机抽样算法

4.5分布估计算法

4.5.1基本原理

4.5.2算法流程

4.5.3染色体编码与相关算子

4.6计算实验与分析

4.6.1实验案例

4.6.2参数设置

4.6.3结果分析

4.7本章小结

第5章多技能主体下的项目调度与协调

5.1引言

5.2研究现状分析

5.2.1软件项目调度

5.2.2基于多主体合作的项目调度

5.2.3基于多主体协调的项目调度

5.3问题描述

5.4基于招投标的MAS调度与协调算法

5.4.1MAS调度与协调

5.4.2多主体系统架构

5.4.3相关定义及算法流程

5.4.4基于招投标的协商过程

5.4.5算法示例

5.5计算实验与分析

5.5.1实验案例

5.5.2结果分析

5.6本章小结

第6章多服务站多技能人员调度

6.1引言

6.2研究现状分析

6.3问题描述与建模

6.3.1问题描述

6.3.2问题建模

6.4多目标进化算法

6.4.1个体表达

6.4.2基本启发式算法

6.4.3经典NSGAⅡ算法

6.4.4两阶段进化算法

6.5计算实验与分析

6.5.1实验案例

6.5.2结果分析

6.6本章小结

第7章服务系统多层级人员调度

7.1引言

7.2研究现状分析

7.3问题描述与建模

7.3.1问题描述

7.3.2问题建模

7.4基本启发式算法

7.4.1算法主框架

7.4.2生成第t天可行方案库

7.5综合单目标模拟退火算法

7.5.1模拟退火算法流程

7.5.2邻域移动规则

7.6高维多目标进化算法

7.6.1算法主框架

7.6.2个体编码

7.6.3交配池构造

7.6.4重组操作

7.6.5选择操作

7.7计算实验与分析

7.7.1实验案例

7.7.2模拟退火算法实验结果分析

7.7.3多目标优化算法实验结果分析

7.8本章小结

第8章任务时序约束的巡访服务人员调度

8.1引言

8.2研究现状分析

8.3无时间窗的巡访服务人员调度

8.3.1问题描述

8.3.2问题建模

8.3.3基本NSGAⅡ算法

8.3.4计算实验与分析

8.4带时间窗的巡访服务人员调度

8.4.1问题描述

8.4.2问题建模

8.4.3嵌入LNS的多向局部搜索算法

8.4.4基本NSGAⅡ算法

8.4.5计算实验与分析

8.5本章小结

参考文献

索引

附录A英汉排序与调度词汇

后记

本书以基于服务任务关联特征的服务分类为主线，分别从项目型服务、独立型任务、同服务对象时序关系型任务等方面，结合实际的信息技术服务、医疗健康服务等服务系统背景，讨论了一系列服务系统中的多技能人员调度问题，从提高服务水平、提升服务效率、降低服务成本甚至提升服务人员的自身价值等多种维度，建立问题的单目标、多目标甚至高维多目标模型，提出优化调度算法，经计算实验设计和实施验证算法的有效性。全书内容的展开遵循理论与实践相结合的原则，从实际应用出发提炼服务系统人员调度的问题要素，站在一般意义的视角提出问题、分析问题、解决问题，从而得出具有现实意义和理论意义的结论。 本书可作为排序与调度、服务运作管理、系统工程、软件工程、卫生服务管理、互联网服务等相关课程的教学参考，也可供各类服务领域的从业者、以服务系统为研究背景或以排序与调度为研究问题的研究者学习参考。

作者于2005年12月取得华中科技大学系统工程专业博士学位，自1998年始在华中科技大学任教，先后主持了多项工程应用研发项目和国家自然科学基金、湖北省自然科学基金、*留学回国人员科研启动基金、图像信息与智能控制*重点实验室开放基金、华中科技大学自主创新基金等基础研究项目。获2项国家科技进步二等奖、1项全国企业管理现代化创新成果奖和3项省部级科技进步奖、华中科技大学优秀博士学位论文奖、湖北省自然科学优秀论文二等奖，取得软件著作权4项，出版专著2部，在国际国内学术期刊以及重要学术会议上发表学术论文70余篇，SCI、EI收录30余篇。

第1章绪论
1.1引言
服务业是国民经济的重要组成部分，服务业的发展水平是衡量现代社会经济发展程度的重要标志。2018年3月发布的我国政府工作报告显示，服务业增加值占GDP比重已经达到51.6%，服务业已成为我国经济增长的主动力［1］。自21世纪以来，信息技术的飞速发展和广泛普及在推动传统行业改造和升级的同时也催生了很多新型服务业态，服务业的广度和深度得到了大大加强，这种日新月异的发展态势在我国社会经济结构中尤其突出。伴随服务业的快速发展和广泛重视，一门新兴科学——服务科学逐步形成，服务资源组织与协调是其中一类关键问题［2,3］。服务系统为了实现其尽可能高的运行效率和服务水平、尽可能低的服务成本，在日常运营中需要着重考虑进行服务资源分配以及服务任务调度问题，而人力资源是其中的核心资源。
当前，伴随信息经济、知识经济的飞速发展，社会经济细分化程度越来越高，各行各业都需要有专门技能或知识水平的“人”以保持核心竞争力，从而得以在社会发展中生存以及进步。可以说，社会经济的发展越来越依赖于“人”，尤其是“人才”的积聚和使用，人力资源是组织的资源。小至一个小微企业、一个社区组织，大至一个跨区域企业、地区政府、一个行业，乃至一个国家，甚至全球，都要关心“人”这一类资源的配置和利用问题。当前社会经济发展形势下，这种问题在作为就业容器的服务型组织中更加受到关注。
本书所讨论的各主题将围绕“多技能人员”这一类资源如何在服务系统中有效利用、高效利用、人尽其才等目标来展开，着眼于服务组织的计划与调度决策，而并不考虑资源规划、获取、开发等传统人力资源管理业务职能中的相关问题。基于此，在讨论资源调度问题的场景下，并不特别区分人力资源、人员、员工、人力、劳力等常见于相关文献的名词。

1.2服务运作管理与人力资源
1.2.1组织与运作管理

组织是由一群有明确的角色分工并且为了实现组织目标而在一起工作的人所组成的。
运作管理是合理配置资源以生产、交付产品及服务为目标的活动。组织的运作职能是整个组织的核心，其原因在于生产、交付产品及服务是一个组织存在的理由，无论是营利性组织还是非营利性组织均是如此。

如图11所示，所有组织的运作系统都是一个“输入转换输出”过程。输入到运作系统中的各类资源，包括未来被转换的资源，如原料、信息、客户等，也包括未来用于进行转换的资源，如设备、人力资源等。这里的人力资源包括运行、维护、计划和管理运营的所有人员，即参与运营职能的各个层次的人员。而整个组织运作系统将由管理者通过组织中人的活动来利用各种输入资源驱动转换系统交付相应的产品或服务，实现组织的目标，由此可见在组织的运作系统中“人”的核心作用。

图11运作系统的“输入转换输出”过程

1.2.2服务与服务分类
服务系统的服务不同于制造系统的产品，是一种顾客作为共同生产者的、随时间消逝的、无形的经历［4］。服务组织的运作系统中的输入既包括顾客，也包括服务组织的人力、物力和资本，其运营特征： 顾客参与服务过程，服务的生产和消费同时发生，能力随时间消逝，具有无形性和异质性。因此，在服务系统的日常运作管理中，需要充分考虑顾客对服务任务的时间、空间、内容甚至对服务人员的偏好等方面的需求特征。
进一步结合服务系统自身的资源配置特征，可以从服务的传递过程(包括劳动力密集程度高或低、交互及定制程度高或低两个维度)、服务活动的性质(包括服务活动的无形或有形、服务的直接接受者为人或物两个维度)、顾客关系(包括服务间断交易或持续传递、服务系统与顾客间为会员关系或非会员关系两个维度)、服务的定制和判断(包括与顾客接触的服务人员为满足顾客需求行使判断的程度高或低、服务特征定制的程度高或低两个维度)、需求和供给的性质(包括供给受限制的程度为需求通常能被满足而没有较大延迟或需求经常超过能力、需求随时间波动的程度大或小两个维度)、服务传递方式(包括服务的可获取性为单一场所或多个场所、顾客与服务企业间是顾客去服务场所、服务人员上门服务或远程服务两个维度)等维度进行服务分类，以便于认识服务系统的特征，从而有效地开展服务运作管理［4］。
本书将要展开的各部分内容是从服务任务关联特征的维度，将服务内容分为三大类，基于不同服务任务关联特征来讨论服务系统中的多技能人员分配与各类任务调度问题。
类服务内容是独立型任务。服务内容结构相对简单，面向各服务对象的服务任务相对独立，任务和任务之间没有内容上的关联，各服务任务由一个或一组具有相应技能的人员在一定服务周期内予以实施。这类服务常见于医疗健康服务、IT运维一线/二线服务、设备安装服务、设备/设施维修服务、家庭服务、养老服务等。
第二类服务内容是项目型服务。服务内容以项目形式呈现，内容结构复杂，包括一系列任务，任务和任务之间存在前后序关系，形成了一个以任务网络(也称为活动网络，以下不做区分)描述的服务项目，项目中各任务的执行需要相应技能的人员，相应人员执行不同任务时因为使用的技能和任务执行位置的不同会存在相应的转移时间(含技能转换过渡时间)。
第三类服务内容是针对同一服务对象形成具有一定时序关系的多个服务任务(以下简称为同服务对象时序关系型任务)。类似于独立型服务任务，各服务对象的服务任务没有关联，服务履行地点不同，而围绕同服务对象可能产生多项服务任务，每项任务需要一位具有相应技能的人员经历其规划的任务路径巡访到场执行，这些服务任务之间可能存在一定的时序关系(如同步、重叠、小时差、时差、混合时差等，比如家庭医生服务中检验服务和巡诊服务须有一定的时间差）。
1.2.3资源与人力资源
1. 资源

从经济学的角度来看，资源是为了创造物质财富而投入到生产活动中的一切要素。从资源的来源来说，可以划分为自然资源和社会资源，自然资源是由自然界提供、具有自然属性特征的资源，而社会资源则具有人为属性，包括劳动力资源以及由人类创造的物质资源和非物质资源。资源也可以划分为人力资源、物力资源、财力资源、信息资源、时间资源等，其中人力资源是一切资源中宝贵的资源。
2. 人力资源
人力资源由管理学大师彼得·德鲁克于1954年在《管理的实践》中首次提出并加以界定，他认为人力资源和其他资源的区别在于人力资源是人，具有其他资源没有的协调、融合等能力，是一类特殊的资源，可以通过有效的机制进行开发和利用，从而为组织带来经济利益。
对于人力资源有多种不同的定义。美国学者伯格认为，人力资源是人类可用于生