人员调度问题的研究综述及发展趋势分析

缪 彬，黄梦婷,2

(1.昆明理工大学 管理与经济学院，云南 昆明 650500；2.仰恩大学 管理学院，福建 泉州 362014)

0 引 言

人员调度问题的主要研究内容是如何将多个任务合理地分配给多个员工，通过定义要完成的任务，及其开始时间段、工作持续时间、休息时间间隔等，为每个员工构建工作时间表以满足业务需求[1].该问题的研究始于20世纪50年代，Edie[2]利用启发式算法求解交通收费站员工的排班问题，随后Dantzig[3]对以最大限度减少顾客在收费站等待时间为目标的调度模型，提出了整数线性规划的求解算法.

自Edie和Dantzig的开创性研究以来，人员调度就一直是研究者关注的问题.人员调度作为资源分配的主要任务之一，是组织普遍存在的问题，这就决定了其应用的广泛性：如航空、公交、铁路等运输系统的机组排班研究[4-10]；考虑交叉培训[11]、柔性流水车间[12]等制造业人员调度问题的研究；关于需求波动大的零售业领域员工调度、重调度[13]问题的讨论；顾客随机到达的呼叫中心[14-16]、医疗保健领域[17-18]员工合理调度问题的讨论，以及军事和紧急服务领域[19-20]人员安排问题的探讨等，其应用范围遍及生产、服务、医疗、军事、应急管理等各个方面和领域.

合理的人员调度是企业运营管理成功的关键因素之一，其解决方案必须设法将成本降至最低，同时对人员偏好、任务覆盖、法律以及合同约束等诸多因素进行考虑，在员工之间公平分配班次，满足所有工作条件限制.这些限制增强了模型的多功能性、多目标性、灵活性和实用性，但也极大地增加了求解的复杂性，使其发展为高度约束和复杂的NP难问题.随着企业服务和成本意识的增强，敏捷精益等业务要求的提升，资源、市场等竞争的加剧，对人员调度提出了更高的要求.基于此背景，本文首先对人员调度静态求优和动态求解这两类研究问题进行综述，进而对其相应求解算法进行总结与归纳，最后对该领域未来研究趋势进行分析和展望.

1 调度模型的应用研究

从应用情况看，调度模型的研究可以分为确定性问题求优和随机性问题求解两类.其中，确定性求优主要研究确定性的人员调度问题；随机性求解则主要研究随机因素影响的人员调度问题.这两类问题的研究并非依次进行的，而是一个相互交叉、持续改进过程[21].本节的内容以及归纳思路见图1.

图1 模型应用研究框架Fig.1 Framework of application research on models

1.1 确定性问题求优

早期的人员调度研究大多集中在任务固定、需求确定的情况下做出决策，因此，在研究过程中通常将人员调度看作是一个静态的过程：如Edie和Dantzig[2-3]对收费站所需工作人员排班问题的讨论；Artigues等人[22]对生产车间部分员工的调度；Alfares[23]在只考虑非常有限的可能轮班数量情况下，对某大型石化公司IT服务台呼叫中心的人员进行配置.尽管后来在模型改进研究的过程中，研究者考虑各种混合劳动力的使用(全职和兼职员工)[24]，需求多样性[25-27]、员工的满意度、资质要求、个人偏好以及出差计划[28-30]等更加复杂的约束，但其本质上也都是在确定性需求预测的基础上实现的人员调度.在人员调度过程中，通过对劳动力需求、任务持续时间和员工时间的可分配性做出不同的确定性假设，便能得到组织所需的完整排班计划.然而，由于组织的运作通常是动态决策，这些假设并不能完美地代表班次执行期间的情况，为使模型更加贴近实际，研究者们进一步对人员调度的随机性应用进行研究.

1.2 随机性问题求解

静态的调度模型虽然通过不同的确定性假设，实现了组织内的人员调度，但模型却忽略了需求变化、员工能力差异以及计划外人员缺勤等动态的意外情况.

1) 需求变化的动态应用.根据业务和环境要求不同，人员调度的需求差异很大.在医院[31]、公共安全和交通运输领域等，一周 7 d、每天 24 h 都需要员工在岗，此类人员调度属于连续调度问题，在调度过程中，任务需求通常以班次表示，并且为应对各种需求的动态变化，会采用年工作时间固定而周工作时间可调整的“年化工作时间制度”来增加员工排班时间表的灵活性.在大型零售店[13]或呼叫中心[16]领域，需求在一天的营业时间内会有很大的波动，此时，需求通常采用每个时段所需的客户服务量来表示，而不是用班次来表示.这类劳动密集型的服务组织，需要对调度时间表进行实时调整，为组织提供更有效的决策.综上，针对不同类型的调度问题，研究者需要对需求做出不同的假设.

2) 人员意外缺勤的研究.目前，研究者主要通过加设缓冲资源来应对计划外人员缺勤这一意外情况.早在1995年Steel和Rentsch[32]就对人员缺勤问题进行了研究.面对人员缺勤这一影响因素，一些研究者在调度问题的研究过程中假定员工有很高的出勤率，而另一些研究者通过提前设置缓冲资源来减少缺勤带来的意外影响，如Easton[33]在任务所需时间基础上加设缓冲时间；Ionescu等人[34]提前设置容量缓冲区来处理计划外缺勤问题，但这些技术并不能很好地解决人员调配不及时或任务需求发生变化时员工时间表的调整问题.并且，利用这种结构性人员过剩的方法对该问题进行预防，虽然能在一定程度上提高人员调度的稳定性，但所需要的缓冲时间或资源容量却很难精准计算，如纳入的缓冲资源越多，人员出现短缺的概率越小，但成本相应会提高，因此需研究如何对二者进行权衡，规划好缓冲容量的大小.

3) 员工能力差异的研究.员工能力是指拥有理论知识、实践技能以及能胜任某项任务的条件[35].Hur和Denkena等人[36-37]研究了员工能力与任务需求之间的匹配程度对组织的服务水平和盈利能力的影响；Van Den Bergh等人[30]在所提的模型中给出了有关服务需求以及员工能力成熟度动态管理制度的假设和预测；Bruecker等人[38]强调在调度过程中，对任务所需技能层次进行正确分类是员工能力与岗位需求成功匹配的首要任务；冯霞等[39]以均衡员工工作时间为目标，将不同资质层次的员工分配至相应的任务班期中.上述各种关于员工岗能力匹配度的研究，都在最大程度上避免了员工能力过剩，把抽象的员工能力/技能层次概念转为具备实际操作意义的模型约束及动态调度管理要求，反映了组织的实际服务需求和员工的可用性.

4) 调度问题的复杂集成.孤立的决策通常导致次优的结果，甚至最终出现无效调度.Maenhout等人[40]将资源规模、人员资质和特定的员工特征(偏好、合同规定等)综合考虑以保证排班质量，提高员工的满意度；Corominas等人[41]提出了一种集成生产、人力资源和资金管理决策的调度计划模型；Smet等人[42]定义了多技能任务调度与人员排班相结合的新型调度组合优化问题；Van Den Eeeckhout和Santos等人[43-44]考虑了人力资源与项目、机器调度等方面的集成研究.上述调度问题的集成研究，考虑了资源、设备、资金等生产要素和调度要求之间的相互作用，使得结果在理论上接近实际最优，但这些要素的动态变化也引发了人员的动态调配，导致调度模型变得更加复杂，求解难度大幅上升.

2 求解算法研究进展

近年来随着工作环境和业务要求的复杂化，对人员进行合理调度的难度大幅增加，其模型变得更加复杂，相应的求解也变得更加困难.尽管在过去几十年，计算机以及计算软件有了长足的发展，但人员调度问题的求解质量和求解效率仍需进一步提升.

相关的研究文献里展示了众多的求解算法，这些方法可以概括为精确算法和启发式算法两大类.本节具体综述脉络见图2.

图2 主要求解算法框架图Fig.2 Block diagram of main solution algorithms

2.1 精确算法

用于求解人员调度问题的精确算法有常见的规划算法、列生成算法、分枝定界算法等.精确算法改进的目的在于不断提高其求解效率，通常用求解代价对算法的性能进行衡量.下文是对一些常见的求解调度问题的精确算法进行介绍：

1) 规划算法

运用规划算法对人员调度模型进行求解的研究始于Dantzig[3]，该算法在调度领域的首次应用，使其在探索问题的求解算法方面具有重要的理论价值.基于上述理论认识，使用规划算法求解调度问题的研究不断涌现[45-47]，如Topaloglu[47]提出采用多目标规划来制定员工每月轮班时间表等.但由于各行业人员调度的现实需求不同、目标函数多样、约束条件复杂，线性规划算法很难满足人员调度的实际要求，于是有研究者运用非线性整数规划来模拟和求解两阶段救护人员调度问题[48]、两阶段呼叫中心人员的调度问题[49]、以及飞机和机组人员的调度问题[4].

由于规划算法对数据的准确性要求高，且计算量大，在实际求解应用过程中还会将规划算法与其他算法相结合.如He等人[50]使用结合列生成算法的混合约束规划(CP-CG)来求解护士排班问题，CP-CG算法结合了线性规划有效松弛的优点和约束规划对复杂逻辑约束建模的强大表达能力，但该算法只能得到与最优解有一定差距的整数解.

从上述算法的研究脉络可以得知，在该领域规划理论的研究已经相当成熟，能够解决不同行业领域需求较为确定的人员调度问题.

2) 列生成算法

由于规划算法求解大规模调度问题时，通常数据处理时间长且难以得到最优结果，于是适应大规模问题求解的列生成算法脱颖而出.Barnhart等人[51]最早对机组人员调配问题中的列生成算法进行了介绍；Santosa等人[5]提出混合列生成算法来解决公交公司的乘务人员调度问题，结果证明在获得最优解时，混合列生成算法比改进前的算法求解效果更好； Restrepo等人[52]在列生成算法中定义了一个基于约束网络的辅助问题，辅助问题的网络结构允许构建模型时加入复杂约束，并配合具有资源约束的最短算法来生成列，能够在更长的计划周期内找到最优的调度方案；Lin等人[53]摒弃传统以每天、每周为顺序的启发式三阶段人员调度求解方法，使用基于列生成方法的滚动水平法来求解月度排班问题，在更少的计算时间内获得更高质量的解.由于列生成算法求解思路源于单纯形法，区别是列生成算法不需要计算验证原问题所有的检验数，通过“减少”变量个数来提升求解效率，因此能够高效地解决大规模人员调度问题.

3) 分枝定界算法

20世纪60年代，Land Doig和Dakin提出适用于组合优化问题求解的分枝定界算法.分枝定价算法则是在分枝定界框架中，使用列生成算法来求解每个分枝节点的算法.不同的分枝规则与定界方法，会形成求解同一问题的不同分支定界算法，Maenhout等人[54]利用详细的计算实验来评估不同的分枝规则和剪枝策略；Klabjan等人[55]提出强分枝定界和时间线分枝规则的算法，其中的时间线分支规则源自最早Beale和Tomlin[56]提出的SOS分支思想，而强分枝是一种选择特定分枝的方法，其目的是尽可能增加子节点的下限，快速找到一个好的整体解；Quesneld等人[57]利用一个寻找上界的可行性启发式算法和一个改进下界计算的列生成分支价格方案对机组排班模型进行求解.上述学者在分枝规则和定界方法的研究上都取得了一定的成果，同时促使人们根据他们的研究结果进一步开发、改进和增强分枝算法，寻找更优的分枝规则和定界方法，使其在调度的管理实践中体现更实用的价值.

虽然众多精确算法对较小规模的调度问题能够在短时间内找到最优解，但由于在获取最优解时对计算要求高，面对大规模的人员调度问题，便无法在可接受时间内产生最优解.因此大规模人员调度问题求解复杂程度和求解难度的增大，促进了启发式算法的发展.

2.2 启发式算法

启发式算法的实际优势在于其有效性和普适性.有效性体现在有限的运行时间内产生可行解[32]，普适性则是它与其他算法能很好的兼容.对于大规模人员调度问题，需要数小时计算求得的最优解，通常不如启发式算法快速求解的次优解有价值[58].

1) 局部搜索算法

支持局部搜索的模拟退火[59]、禁忌搜索、变邻域搜索算法等常被用于求解各种人员调度问题.苏宙行等人[60]运用整数规划精确算法配合禁忌搜索算法将调度问题解决至接近最佳状态，结果显示，尽管禁忌搜索具有超越局部最优的能力，但良好的初始解决方案异常重要.Tassopoulos等人[61]提出两阶段变量邻域搜索算法，他们通过护士调度实例验证了该算法改进初始解的有效性.Liu等人[62]提出将模拟退火算法在局部搜索和遗传算法框架内混合，利用扩展的随机排序方法对护士调度问题进行初步求解，结果表明该方法用于寻找初始解有较好的效果.近几年，研究者们还从算法的收敛概率、搜索/求解效率等不同方面，对求解人员调度问题的变邻域搜索算法进行改进，相继提出能自动切换搜索策略的自适应变量邻域搜索[63]、与精确算法结合的混合变邻域搜索[64]，以及使用随机组合算子就能迭代搜索的随机变量邻域搜索算法[65].从上述研究脉络可知，研究者利用不同的局部搜索算法很好地解决了各种调度问题，也对提高初始解质量方面做了很多探索性研究，但目前对于求解初始解，并没有一个较为高效统一的算法，需继续对其进行研究改进，以此保证更加快速地获得高质量的人员调度方案.

2) 全局搜索算法

遗传算法和粒子群算法是求解人员调度问题最常用的一种全局搜索算法.由于经典的遗传算法范例，并不能很好地处理人员调度模型各约束之间的冲突，为克服该问题，Aickelin和Dowsland[66-67]曾通过对违规行为设置适应性惩罚来解决规范遗传算法中目标与约束的冲突问题，也曾引入混合交叉算子和边界条件来缩小解的空间，进一步加快求解速度.近年，Demirel等人[68]提出了一种基于改进的动态遗传算法的启发式算法，使得配对搜索最小化，结果显示文中所提遗传算法求解得到的机组排班方案质量较高.Tam等人[69]提出了多目标规划和遗传算法相结合的方法，用来寻找具有多个硬约束和软约束员工调度问题的最优排班计划，有效提高了算法的求解效率.

粒子群算法作为常用的全局搜索的算法之一，能提高搜索过程迭代解的质量，丰富启发式算法对非线性人员调度问题的求解研究.Altamirano等人[70]用粒子群算法很好地解决了护士员工的公平/平衡时间表问题，但由于该算法的“粒子”是一个折衷的选择，求解的结果只是最优折衷解.贾宝惠等[71]提出的交叉粒子群算法是一种改进的粒子群算法，改进算法参考了遗传算法的交叉操作和变异操作，高效解决了航班机组人员调度问题.

两种算法在解决调度问题时各有优缺点，在算法的收敛速度上，粒子群算法优于遗传算法；而在稳定性上，遗传算法则优于粒子群算法，粒子群算法的最终收敛结果容易受初始解的影响[72].

3) 基于学习机制的算法

研究者们对蚁群算法、差分进化等基于学习机制的算法在人员调度领域的求解应用也进行了有意义的探索.关于蚁群算法，早期张毕西等人[73]考虑中小手工制造企业员工的“学习性”，提出了适合求解非流水线手工生产人员分配的改进蚁群算法，但其调度时效性还有待进一步完善；近年研究者们提出了不同的改进蚁群算法，如Engin等人[74]提出一种求解无等待流水车间调度问题的混合蚁群优化算法；王东先等人[75]以总交路时间最小为求解目标，引入“均衡因子”概念构建模型并利用改进的蚁群算法对其进行求解，结果显示该算法求解效率较高，对问题求解具有强适应性.虽然各种改进的蚁群算法在一定程度上提高了问题的求解效率和质量，但研究结果均采用仿真求解，缺乏实例验证.

关于差分进化算法的研究，目前主要集中于工程、物理、计算机科学以及数学应用领域[76]，在人员调度领域的应用也在逐步探索.张守旭[77]曾将差分进化算法简单的应用于话务员排班分配系统中，而黄秀彬等人[78]通过对算法的变异率和交叉率进行自适应调整，平衡了算法在解决大规模调配问题时求解速度和精度问题之间的矛盾，有效实现客服中心人员的调度优化.

蚁群算法的并行性使其能够快速发现较好的解，但收敛速度较慢且易陷入局部最优[79]；而相较于蚁群算法，差分进化算法操作更简单、鲁棒性高，反复运算都能收敛至同一解，但目前在人员调度领域的研究成果数量方面却远不及蚁群算法.

3 研究趋势分析与展望

调度模型的应用研究，考虑了各种可变性因素以及不同资源之间的相互作用，因此能够在一定程度上正确反映实际的服务需求和员工的可用性，使调度结果在理论上接近实际最优.而求解算法的不断改进，则提高了调度模型的求解质量及应用价值.

虽然最新研究成果已经被应用于人员调度的各个领域中，但仍有很多问题未能得到解决:如现有调度模型大多根据案例自身约束和特征进行设计，想要应用其解决不同行业人员调配问题时往往需要进行重大修改；多数改进的混合求解算法都只是算法间的简单“拼凑”,并未实现真正意义上的互补，求解效率没有得到明显提升；多数文献缺少对所提算法进行有效性的实例验证等.综上，人员调度问题仍有许多待解决的难题，如图3所示.

图3 全文脉络框架图Fig.3 Diagram of text context frame

3.1 研究存在的难点

人员调度问题的研究开始较早，且已取得了一系列的成果，但从调度模型的实际应用和求解方法的研究进展来看，该领域仍然存在一些研究难点.主要包括以下几点：

1) 复杂调度的求解效率

针对人员调度问题，研究者们逐渐对员工偏好、员工出差/加班/休假、需求不确定性、混合劳动力等各种可变性因素进行考虑，对不同资源之间的相互作用进行集成研究，使得模型能正确反映实际的服务需求，但模型的复杂性大幅上升，因此,对其求解算法的创新以及求解效率的提高仍是目前研究的难点.

2) 模型及求解算法的通用性

目前多数人员调度模型都是根据其案例自身的约束和特征进行设计，系统的算法是定制的，因此当模型和算法要应用到不同的人员调度领域时，或者为适应组织自身的内部变化时，通常需要进行重大修改.如何基于传统调度理论，提出更加通用的调度模型，从而减少应用时的重大修改，扩大其应用领域，是人员调度研究未来需要解决的问题.

3) 求解算法的有效性验证

在文献的梳理过程中，发现多数文献的求解方法倾向于规划算法和启发式算法，行文结构多为问题提出、模型构建以及模型求解三部分，缺少对模型求解算法的有效性证明和评价模块.未来研究可以增加所提算法与分支定界、遗传等典型求解算法的实验比较模块，以此来验证其有效性.

4) 求解方案的鲁棒性提升

除1.2节所描述的在调度模型中对需求不确定、人员缺勤以及员工能力差异等随机因素进行整合以提升模型的现实意义外，更重要的是还应进一步研究如何提升其解决方案的鲁棒性，如通过模拟需求、工人可用性等的随机行为来对方案进行改进.但事实上，很少有文献对此进行专门分析，因此，缺乏对求解方案鲁棒性提升的研究也是目前存在的问题之一.

3.2 研究趋势展望

结合上文研究存在的难点进行分析，本文从“需求拉动”、“技术推动”和“理论推动”这三个角度对人员调度问题未来的研究趋势进行展望，具体未来发展方向归纳如下.

3.2.1 基于需求拉动

人员调度是一个高度约束和复杂的问题，该问题需要组织特定的劳动力，降低相关人员成本，同时建立合理的员工时间表以提高人员的满意度，且随着研究的不断深入、调度的规模不断增大，使得该问题的应用和求解困难.基于上述这些研究需求的拉动，未来可能在以下几个方面对人员调度问题做进一步研究：

1) 算法效率提升

对于需求确定的小规模的人员调度问题，利用规划、分支定界等经典精确算法就能准确求解.但当调度规模较大时，就会出现计算速度慢、求解质量低等问题，目前一些常用的算法就是将原有大规模问题分解成几个研究阶段的小问题，按照迭代策略进行求解，以此得到原调度问题的近似最优解.但原问题分解方法的确定，以及迭代策略的选择是此类算法求解效率提升的关键，因此,需要基于此思路对现有的求解算法进行改进以提高其求解效率.

2) 模型及算法泛化

人员调度模型和相应求解方法的泛化也是需要进一步研究的重要领域.关于该领域的研究可参考Chaouch等人[80]提出不涵盖各种特殊情况的通用数学模型，研究者可以在此模型的基础上，构建特定条件下的不同适用模型，同时该模型允许开发适用于特殊情况的一般启发式算法.未来可以在这些已有研究基础上，进一步对应用理论进行探索，提出更加普适性的人员调度模型及求解算法.

3) 中断恢复研究

由于在实际人员调度过程中，存在诸如能力、需求和到达不确定性因素，这通常会导致员工时间表的中断.为了恢复人员调度计划的可行性，并在调整过程中尽量减少不必要的人力浪费，就应对人员的重调度过程进行深入研究.作者通过对人员调度相关文献的整理分析后发现，目前已有研究者对调度的中断恢复进行研究[13,55,81]，但文中所考虑的人员重调度，处理的是短期决策问题，即只考虑当前的中断，而没有预测未来的中断，所以在往后的中断恢复调度研究中需要对未来中断的进行预测.

3.2.2 基于技术推动

智能化人员调度系统的研究.随着智能技术、设备的开发和使用，从人机交互角度对人员调度的研究逐渐增加，如现有许多调度问题的研究目标转变为：为不同组织提供调度支持工具，以此来减少人工构建时间表的需要，能够满足需求动态变化情况下，对员工时间表的实时调整.如广泛应用智能体进行仿真的各种机器[82]、生产[83-84]、订单[85]、项目[86]、车辆调度[87-88]研究.目前对智能化人员实时调度系统也已经有了初步的探索，但主要集中在医疗保健领域[89-91]，该项技术在人员调度领域的研究，无论在理论层面还是应用方面均处于探索阶段，在业务量和劳动力预测，以及排班过程自动化等方面均不成熟，但这也正是未来创新和拓展智能化调度的重要研究方向.未来对人员的智能调配也可参考上述各领域的调度经验，利用物联网和云技术等构建人员调度的智能体系统，引入智能体的混合行为(如人的行为因素)，逐步实现和完善人员智能化调度.

3.2.3 基于理论推动

行为运筹学相关理论的引入.人员调度是以“人”为中心的调度问题，其行为的最基本特征就是“有限理性”，因此，经典的运筹学优化理论并不能完全适应此类问题的求解.在众多已有的人员调度研究文献中，员工偏好是最常被考虑的人员行为软约束，此类调度模型多以提高人员满意度为目标，但类似于员工对现状的偏见、从众现象等有限理性心理却并未在模型中被考虑.因此，未来可以考虑研究、分析和量化这些行为因素对人员调度的影响，并基于已获得的人员行为特征，建立更加符合实际的调度模型来改善调度结果.

4 结束语

本文对人员调度问题的相关研究成果进行了综述.首先从应用层面上，将人员调度问题大致分为确定性问题求优和随机性问题求解两类，并分别对其研究脉络进行梳理；在此基础上对求解模型的精确算法和启发式算法进行归纳；最后根据综述的分析结果，提出人员调度目前存在的难点和问题，以及未来可以进一步研究的方向.由于人员调度工作在企业运营管理中发挥愈来愈重要的作用，受随机因素、人员行为因素影响的大规模的人员调度将会得到更加广泛的应用和发展，因此，研究者在将来将结合生产、服务和管理的实际情况来开展人员调度的应用、理论研究，进一步丰富这一领域的研究成果.