基于Excel和OpenSolver的排班优化教学辅助工具

    郑自然　张鸿雁

    

    

    

    摘 要：为了建立教学环境下简易且独立的教学辅助工具，文章基于Excel平台和OpenSolver插件，建立了一个人员排班问题的模型展示和求解工具。该工具主要包含问题的建模和解的展示界面。教师可以使用该工具较为清晰地向学生展示问题的结构和建模过程。学生可以借助该工具提供的思路和方法建立自己的模型。该工具包含一个具体的源自实际生活中的排班问题，且能够求解较大规模的问题实例，目前已经在山东师范大学的优化相关课程中使用。反馈结果表明该工具能够帮助学生更好地学习和理解排班优化相关知识。

    关键词：人员排班;整数规划;Excel;OpenSolver

    中图分类号：C93-03 ? ? ? 文献标志码：A ? ? ? ? ?文章编号：1673-8454（2021）02-0092-05

    一、引言

    人员排班是一类重要、常见且较为复杂的优化问题，近年来一直受到学术界的关注[1][2]。从教授运筹学和优化相关课程的角度来说，人员排班也是一类具有代表性的优化问题。通过对该类问题的讲授，学生可以了解针对实际问题的建模过程，掌握常见的整数规划约束的建立方法，并进一步学习优化问题的求解方法。

    作為一种复杂的优化问题，对该问题的求解需要用到多个软件平台和工具的组合，例如高级语言集成开发环境、优化求解器、建模工具包及其他相关的工具。在课堂讲授环境中，利用这些软件组合来讲授优化问题具有一定的不便性。首先，大部分软件都不是免费的，有些软件的教育版本学生并不方便申请。其次，这些软件大都建立在高级编程语言基础之上，学生在能够求解和理解问题之前需要具备一定的代码阅读和编程能力，这对于初学者或是没有高级语言背景的学生产生了一定的阻碍。另外，安装和配置相关的软件组合较为复杂，学生和教师在配置的过程中需要花费较多的精力，因而造成无法将主要精力集中在问题的讲述和理解上。因此，独立且轻量级的教辅工具更适合课堂环境的使用。

    Microsoft Excel作为一种常用的表格计算和统计软件，不仅可以作为多功能的表格呈现和计算工具[3-7]，近年来在课堂教学环境中也开始扮演重要角色。越来越多的教育工作者将电子表格软件作为一种轻量级的计算平台进行辅助讲授[8-11]。国内相关研究目前还比较少，如丁以中[12]以赶工问题为实例，探讨了Spreadsheet教学法的优势。作为对于该领域的补充，同时为了解决本单位教学辅助的问题，本研究使用Microsoft Excel 2016及OpenSolver 2.9.0，设计了一个基于电子表格的人员排班优化软件工具，既可以作为实际问题的求解器，同时也能够展示优化问题的模型和建模过程。

    二、排班问题模型描述

    1.排班问题的描述和决策变量

    排班问题形式较多，根据不同的情况有不同的变化。作为教辅工具考虑到问题的一般性和具体性，本工具采用了一个较为简单但扩展性较强的问题进行展示。当学生对该模型熟悉后，可以使用类似的模型来描述更为复杂的问题。假设一个时间段内包含多天，工作单位需要在一天的时间内对不同的员工分配班次。该问题可以用来描述一大类问题，例如护士排班问题、呼叫中心排班问题或者其他种类的多班次的排班问题。这里用I={1，2，…，|I|}来表示员工的集合;K={1，2，…，|K|} 来表示班次的集合;J={1，2，…，|J|}来表示天的集合（其他问题中也可为其他时间单位，例如小时或者周）。则决策变量xijk可以定义如下：

    xijk=1，如果班次k在时间j分配给员工i0，其他

    大部分的人员排班问题具有软约束和硬约束。在优化过程中软约束包含一些来自单位和员工的偏好，这类约束需要尽可能地满足;而硬约束则来自一些资源限制和硬性要求，这类约束需要必须满足，否则解为不可行性解。人员排班问题的建模是围绕不同的软硬约束进行建模。下面介绍这个问题的具体模型，包括约束条件和目标函数。

    2.排班问题的数学模型

    由于在课堂上一般需要介绍具体的问题实例，因此问题的参数采用固定的数值;教师和学生可以进行相应的改变来讲授自己需要的问题实例。模型中用到的符号如下：

    I ?员工的下标集合： I={1，2，…，5}，|I|=5;

    K ?班次的下标集合： K={1（白班），2（晚班），3（夜班），4（休息）};

    J ?时间下标单位集合;这里时间单位采用天，且总时间段为两周： J ={1，2，…，14}，|J |=14;

    dji ? 在第j天需要班次k的数量，即某天的班次需求（具体数值在表格中设置）;

    wmax 在总时间段内为一个员工的总工作天数的上限： wmax= 10;

    nmax ?在总时间段内为一个员工的总夜班天数的上限： nmax= 3;

    问题的数学优化模型定义如下：

    模型中的约束（2-4）为硬约束，（5-6）为软约束。其中，约束（2）要求对于总时间段的某一天，为所有员工分配的班次要满足当天的班次需求。约束（3）确保某个员工在某一天只能被分配一个班次。约束（4）描述了当某个员工被分配到夜班时，下一天则需要分配休息。约束（5）确保了在总时间段内，某个员工的工作天数不能超过工作上限，这里采用了松弛变量将该约束构造成为一个软性约束。约束（6）原理同（5），确保夜班的天数尽可能地不超过上限。约束（7-8）为决策变量和松弛变量的定义域。

    注意到松弛变量si（和ti）刻画的是某个员工实际工作（夜班）天数和规定工作（夜班）天数上限的差，因此，模型的目标函数则定义为尽可能地减少这两个变量的值，即目标函数（1）的定义。

    三、软件使用介绍

    1.OpenSolver简介

    尽管Excel软件中内嵌一个线性规划的求解器，但是该求解器的完整版并不免费。试用版本有变量的限制（可变单元格不能超过200个），这对于稍大规模的问题或者约束为指数级的问题则无法求解。对于上节阐述的问题，仅主要决策變量xijk的数量就为280，因此无法使用自带的线性优化求解器来求解。

    本软件采用了OpenSolver[9]工具箱来代替默认求解器进行排班问题的建模和求解。该工具是一个基于开源求解引擎的Excel第三方插件。该插件开源，免费且易安装，因此较为适合基于Excel的优化问题的展示和求解。由于其使用的求解引擎本身也是免费的，因此理论上并没有变量的限制。图1为该插件的主要操作界面，该界面的结构与Excel默认的求解器结构相似。在图示指示的框中可添加相应的单元格地址来设置模型的目标函数、决策变量和约束。任何具备线性规划基础知识的学生都可以很快熟悉该插件界面的使用。

    2.辅助工具界面描述

    本研究建立的辅助工具界面如图2所示。为了方便构造约束条件，在该区域需要存放相应的表达式单元格。图2中，该区域中sum（k）所在的行，即为j取某个值时，xijk变量基于下标k的加和，也是某个员工在某一天所有班次的和。这个表达式可以通过Excel自带的函数公式表示。该单元格用来构造模型中的约束（3），即某个员工在某一天只能分配一个班次。图3展示了一个该约束构造的示例。

    图3 中，“D3”到“D6”单元格为j=1时的决策变量的值。当构造模型时，OpenSolver可以将已添加的区域进行高亮。单元格“D7”的内容为“=SUM（D3：D6）”，即D7单元格的值为D3—D6单元格值的和。在OpenSolver的界面中，则可以设置单元格“D7”等于1。

    其他的约束类似，均使用表达式单元格来进行描述。例如图2中决策变量下方为人员需求区域。图4为该区域的部分截图，第32、34和36行为在某一天的某个班次k的需求数值，用req.标识。这里我们使用D表示白班，L表示晚班，N表示夜班。如图4所示，在E列，对于白班的人员需求是2。第33、35和37行则计算的是所对应的决策变量的和。利用这个区域可以实现描述模型中的约束（2）。图4中的高亮边界单元格为添加“E32”等于“E33”后的状态。

    在图2的下方是解的显示区域。这里我们用相应的符号来填写排班表的值。该区域同样可以通过Excel的函数来实现。这里我们采用了Choose函数和Match函数结合决策变量的判断来填写排班表。整体的表格建立尽可能地对齐相关的维度以便观察和函数的赋值。图5为添加完所有决策变量，约束和目标函数值后的单元格的示例。能够看出通过OpenSolver的高亮功能，可以较为清楚地观察已经添加的变量和约束及参数之间的关系。

    尽管由于考虑教学的因素采用的问题规模较小，使用者可以根据该结构任意扩冲单元格的数量并添加相应的变量和约束来求解更大规模的问题。另外，由于对问题的表达形式并不唯一，在使用该工具时我们鼓励学生在理解了方法后采用自己的方式来对问题进行单元格的安排和建模。另外，该表格没有用到任何VBA（Visual Basic for Applications）代码，进一步降低了使用该工具的背景知识需求。对于该问题，求解器的求解时间约为0.1秒。

    四、学生对软件的评价调查

    本工具已经被应用到本单位2018—2019学年信息管理本科二年级《大数据概论》与优化相关章节的讲授中。该章节的主要目的为介绍基本和部分高阶的优化领域的理论和算法。在整数规划一节，教师在讲解一些实际生活中的整数规划实例，即这里所提供的人员排班优化问题过程中采用了该工具。该课程大部分的学生具备线性规划的知识背景，但不具备复杂整数规划模型建立的知识，且对于一般优化软件平台并不熟悉。另一个考虑是在该阶段，采用中等规模问题作为过渡能够降低学生接触更为复杂的问题的学习曲线。主要教学方法是当教师讲授完课本数学模型后，辅助使用该工具进行模型的建立和求解。

    为了得到学生对该工具以及相应教学方式的反馈，课后我们对学生进行了问卷调查。问卷包含了10个评价项目，分数范围为1至5。32名学生参与并回复了问卷。由于学生在实验课中也使用过该工具，因此评价项目中也包含对该工具的使用评价。项目的评价平均值见表1。

    问卷10项的整体平均分为4.20，表明了该工具作为一种优化模型辅助工具的易用性和适用性。其中最高分为第8项，即学生认为该工具能够帮助他们理解和学习人员排班问题。最低分是第4项。其主要原因是部分学生没有用过Excel本身的线性求解器，进而对OpenSolver的界面并不熟悉。然后在课堂和课后的实验过程中，经过简单的解释，大部分学生能够很快掌握方法，且所有学生均能够使用该软件完成实验任务。

    其中，项目1至3是关于工具的界面设计，这些项目的分数均高于4分，证明该工具的界面安排合理并易于使用;项目5是关于工具的建模操作，该项目的分数高于4分，证明使用该工具的建模操作步骤易于理解; 项目7是针对约束添加方式，该项目分数相对较低，主要原因在于部分学生是第一次使用Excel表达式的方式对约束条件进行刻画，而对于一些Excel表达式也不够熟悉。另外，该模型涉及一定的0-1规划建模知识，而学生只是具备一般线性规划模型的背景知识。项目8至10是关于该工具对于整体教学效果的评价。项目分数均大于4.30，证明该软件作为辅助教学工具能够帮助学生学习和理解人员排班问题，即一般性的整数规划模型。

    五、结论

    电子表格作为一种学生和教师都比较熟悉且易于获得的软件工具，其较强的计算和可视化功能使其越来越多地在工业应用和教学环境中扮演重要的角色。本研究建立的辅助工具提供了一种教学环境下利用电子表格来呈现和求解整数规划模型的思路和方法。凭借免费的Excel插件OpenSolver，该工具不仅可以更加清晰地呈现建模过程，同时也可以作为求解器来求解实际规模的问题实例。从反馈结果可以看出学生能够接受并肯定其相关的教学方式。该方式不依赖复杂的优化软件平台和软件包，不需要高级语言编程能力，对于非计算机背景的学生或者还不具备高级语言编程的初学者来说，有利于教学活动的开展和相关知识的学习。

    在后续的工作中，笔者拟对以下几个方面进行研究：首先该工具当前的目标主要集中在模型建立方面，而求解方法采用的是默认的整数规划引擎进行求解。对于排班问题目前有更为复杂和高级的算法，例如列生产算法[13]。因此如何使用Excel并结合VBA语言建立更为复杂的算法及展示平台是后续的工作方向之一。其次，针对不同的特点员工排班问题，可以使用多种建模方式进行刻画，例如基于图的方式[14]能够避免较多的约束条件，从而加速求解过程。如何使用该工具实现其他方式的建模并予以展示是另一个研究方向。最后，借助Excel平台实现启发式或者元启发式算法来求解困难的组合优化或离散优化问题，从而建立一个综合性的优化问题求解教辅工具，是后续的主要研究方向之一。

    参考文献：

    [1]Jorne Van den Bergh，Jeroen Beli？觕n，Philippe De Bruecker，et al.Personnel scheduling：A literature review[J].European Journal of Operational Research， 2013，226（3）：367-385.

    [2]Philippe De Bruecker，Jorne Van den Bergh，Jeroen Beli？觕n，et al.Workforce planning incorporating skills： State of the art[J].European Journal of Operational Research，2015，243（1）：1-16.

    [3]喻靖，朱峰，夏瑞杰.基于Excel VBA实现油田报表自动化设计[J].价值工程，2020，39（9）：193-194.

    [4]颜晓佳，张胜.基于Excel软件的成绩管理系统设计与开发[J].教学与管理，2020（7）：15-17.

    [5]李道西，胜志毫.基于Excel规划求解的泵站加压灌溉管网优化设计研究[J].中国农村水利水电，2020（1）：36-38.

    [6]何明宇.EXCEL在配送路徑优化中的应用[J].价值工程，2019，38（27）：216-218.

    [7]G. Erdo ?an. An open source Spreadsheet Solver for Vehicle Routing Problems[J].Computers & Operations Research，2017（84）：62-72.

    [8]John Baker and Stephen J. Sugden. Spreadsheets in education–The first 25 years[J].Spreadsheets in Education，2003（1）：18-43.

    [9]S. Demir，M. Demir，et al.An MS Excel tool for water distribution network design in environmental engineering education[J].Computer Applications in Engineering Education，2018，26（2）：203-214.

    [10]S. Fernandez，J.A. Orosa，J.J. Galan.A new methodology to teach numerical methods with MS Excel[J].Journal of Maritime Research，2012（9）：29-32.

    [11]A.J. Mason.OpenSolver-an open source add-in to solve linear and integer programs in excel[C].Operations research proceedings 2011， Springer，2012：401-406.

    [12]丁以中.在管理科学教学中运用Spreadsheet教学法的探讨[J].上海海运学院学报，2002，23（1）：76-81.

    [13]Jonathan F. Bard and Hadi.W. Purnomo.Preference scheduling for nurses using column generation[J].European Journal of Operational Research，2003，164（2）：510-534.

    [14]D.S.W. Lai，J.M.Y. Leung，W. Dullaert，et al.A graph-based formulation for the shift rostering problem[J].European Journal of Operational Research，2020，284（1）：285

    -300.

    （编辑：鲁利瑞）