人员班次安排问题研究现状及展望，本文主要内容关键词为：班次论文,现状及论文,人员论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
一、引言
随着社会的进步和技术的发展，企业之间的竞争也越来越激烈，如何提高企业的竞争力，在社会中占有一席之地，已成为各行各业首要关心的问题。目前国外单位劳动力成本越来越高，因此在安排人员班次时，企业的经营者希望雇佣尽量少的工人来满足市场及顾客的需求，降低劳动力成本，这就促使了许多专家学者对MSP进行研究。最早考虑MSP问题的是G.B.Dantzig，1954年他提出了第一个有关MSP的数学模型，这是人们科学的、系统的求解MSP问题的开端。自那以后，许多数学、 计算机科学、管理方面的学者也进入这一领域，他们针对一些特殊问题建立模型，找到一些最优解或近优解，并在实践中应用了这些研究成果。
二、MSP问题产生的背景
人员班次安排问题有深刻的实际背景。无论在工业生产企业，还是在交通运输以及各种服务行业，只要部门需一周七天连续运作，就会存在MSP问题。有些工业企业或服务性企业，每天都要求有人当班， 有的部门甚至要求一天24小时都有人上班。但按《劳动法》规定，每名职工每周应有休息日，每天工作时间亦不能太长，这就产生了人员班次安排问题的两难性。一方面，企业的经营者希望低成本、高服务水平，即安排尽可能少的工人来满足顾客的需求。另一方面，职工则要求自己的劳动时间不超过《劳动法》的规定，并希望企业满足自己的一些社会要求，如：自己的休息日安排在周末，以便与家人团聚；每周的两天休息日连在一起，以便充分利用自己的休闲时间。上述两方面一方面体现了企业经营者的利益，另一方面体现了企业之本——职工的利益，两方面的利益是相矛盾的。一方利益的满足会以另一方的损失为代价。如何权衡两方面的利益，合理安排工人的班次计划，做到在维持适当服务水平的基础上，在满足职工对休息及工作时间的要求的前提下，使职工数量最少，这就是人员班次安排问题所要解决的问题。
长期以来，我国企业的排班主要靠经验，缺乏深入而细致的科学研究。因为在很多人心目中存在着一种旧的观念，认为我国人力资源丰富，没有必要深入研究充分利用人力资源的人员班次安排问题。然而，我国劳动工时制由每周六天变为五天半，又变为现行的五天工作制，人们对休闲的谈论也多了起来，对某些行业提出了新的课题，人员班次的安排就是其中一个。每周休息两天的工作制已与国际发达国家的劳动工时制接轨，但我国关于MSP的研究却是远远未跟上国际先进水平。 在现行的市场经济体制下，维持一定的服务水平，充分利用人力资源，已是企业在竞争中领先的一种重要策略。相应的，对于人员班次安排问题的理论研究在我国也应提到战略的高度。
三、MSP问题的分类
由于MSP问题的多样性，可以从多种角度对其分类， 基本内容主要包括以下方面：
1.班次计划的特点
根据最后编制的班次计划的特点，班次计划可分为个人班次计划（individual schedule）和公共班次计划（common schedule）。个人作业计划又称为固定或非循环计划（fixed／noncyclical schedule），指在计划 期内每名工人的作业计划一直延用一特定的工作日（班次）或休息日的顺序，与其他工人的作业计划无直接关系。对于有周末休息频率A／B约束的MSP问题，作业计划编制连续B周的即可；否则，只需编制一周的计划。每名工人每隔B周或一周重复自己的计划。 公共计划又称为循环作业计划（rotating／cyclical schcdule），每隔一周期，每名工人的计划就重复一次。完整的计划期为N×B周，在N×B周内，每名工人的作业计划相同。表1为一个五周的循环计划，D代表白班，E 为晚班，N为夜班，H代表休息。刚执行该计划时，A 组的工人被分配第一周的计划，B组为第二周，按A，B，C，D，E的顺序分配1～5周的作业计划。在每周的最后一天，每组被分配下一周的计划，执行第五周计划的组则采用第一周的计划。这样，五周后，每组都经历了一个循环。在该例中，对于五组工人而言，完整的工作计划周期应为5×5＝25周。但只需给出5周的计划，其余周的计划按特定的循环方式就可推出。
表1
周 M T W
Th F Sa
Su 组
1
D D D
H
H EE
A
2
E E H
H
H NN
B
3
N N N
N
H HH
C
4
H H H
D
D DD
D
5
H H E
E
E HH
E
两种班次计划各有优劣。个人班次计划的安排算法比较简单，逢时间人力需求变动时，调整起来较方便，故有较强的灵活性，最大的缺点是不公平性。公共班次计划的优点则是公平性，但灵活性不大。
2.班次的种类
根据每天的班次种类，可分为单班次MSP问题和多班次MSP问题。单班次MSP问题指每天只有一种班次，部门每天都需营业，但不超过10 小时，如储蓄所。多班次MSP问题每天有多班， 一般为两班（如商业大楼）或三班（每班为8小时或10小时，重叠时间应付高峰期， 常见于全天候营业部门）。有的多班次问题中每个班次的时间长度、开始时间、结束时间等可以不同；在当班过程中，工人有规定的小憩时间，其起始时刻亦需计划人员安排。多班次无疑比单班次MSP问题更为复杂， 更具代表性。
3.工人的种类
在某些服务部门，会出现季节性或短期的高峰期，如快餐店、图书馆等，管理人员常采取雇佣临时工或兼职工的方式。这样一来，总人力需求既要考虑一定范围内恒定数量的全职工人，又要考虑需依据实际而雇佣的临时工或兼职工的数量。在另外一些部门，工人可能有多个级别，每个级别的工人有各自的时间人力需求。高级别的工人可以替代低级别工人的话，反之则不允许。所以，根据排班对象的特点，可以将MSP 问题分为全职（单种）工人排班、 全职及兼职排班、 多种向下替代（downward substitutability）排班。最常见的现象为第一种， 最复杂的为第三种。
4.参数的性质
按参数性质的不同，可以划分为确定型MSP问题与随机型MSP问题。所谓确定型MSP问题， 指时间人力需求和其它有关参数是已知的确定的量，而随机型MSP问题的时间人力需求和其它有关参数是随机变量。 确定型的MSP问题与随机型的MSP问题的解决方法有实质上的差别。应该说，在实际生活中，动态的、随机型的占的比重较大，但是， 也有很多MSP问题是确定型的。而且，有很多问题，其中随机因素占的比重很小，用确定型的模型来处理不仅方便，而且足够精确。再者，由于MSP 问题极其复杂，很多确定型问题尚不能很好解决，更何况随机型的MSP问题。
5.目标函数的选择
（1）时间人力需求R（i，j）
以R（i，j）为优化目标的MSP问题，着重于MSP的某些特性， 如短期内工人数量的需求波动大，对人的服务不象生产产品那样可以事先储备。此类MSP问题的模型可以归纳为：
MinR（i，j），R（i，j）≥0，为整数
s.t.1）需求模式
2）工会等方面的协议
3）人力资源限制N
4）其它约束
这类MSP问题优化模型，除了用排队论分析求解外， 必须用线性规划表示。现在尚无解一般型整数规划或整数指数规划的确定方法。实际上，严格的MSP算法都假定R（i，j）已知。
（2）所需劳力成本最小
在已知R（i，j）和其它约束条件下（如周末休息的频率， 连续工作时间的上下限等），使总的劳动成本最小。
（3）其它
在（2）中提到的目标函数为最常见的。 还有一些算法力求将约束条件量化。Miller和Warner在目标函数中量化每名职工对连续工作时间、轮班方式、休息日具体时间的选择等的偏好，力求在满足外界时间人力需求的条件下，排出所有职工满意度和最大的班次计划。Laport则用一个成本函数赋予每种班次计划一个权数，用来区分各班次计划的优劣。显而易见，这类目标函数的求解需要借助计算机及其模拟技术。
可以看出，上述的分类方法中包含了一个MSP 问题的基本构成要素，对于任一个MSP问题，变化其中的任一元素，都会形成一个不同的MSP问题，这充分体现了MSP问题的多样性。
四、单班次MSP问题
单班次人员班次安排问题针对的是需排班部门每天只有一个班次的工人当班，不存在换班的情况。它具有以下几个特点：（1 ）是最简单，也是最基本的排班，一般比较容易找到求解方法；（2）单班次MSP的模型可作为某些特殊的多班次MSP的合理近似。例如，有些多班次MSP问题允许工人固定班次种类，则每种班次的工人看成独立的一组，按照单班次的方法求解；（3）求解单班次MSP问题的思想和方法，虽然不能直接应用于求解一般的人员班次安排问题， 但对于我们建立求解一般的MSP问题的方法能提供一些有益的启示。对单班次MSP问题的研究是更一般、更复杂的人员班次安排问题研究和发展的奠基石。
Bake研究的单班次排班问题只有一个约束条件：满足工人每周连休两天，目标函数是使满足外界人力需求和休息约束而雇佣的工人数目（W）最少。Rothstein求解此类问题使用的是线形规划方法，而Bake使用的是解析构造法。解析构造法在某些方面显著优于线性规划。运用解析法，可以快速计算出W， 使管理人员在需求变动或考虑调整休息及工作规则时，可以很快地评价变化对W的影响。另外， 生成班次计划的过程亦很简单。如果将计算机用来辅助生成班次计划，即使是规模很大的问题，也只需要很少的CPU时间， 而线性规划问题则随规模的增加呈指数型增长。当然，线性规划模型更容易附加一些约束条件而不改变其解题思路，可推广为适宜和范围更广的模型。组合解析法则针对新假设，须谨慎考虑原模型是否可修改后继续适用，逢约束条件增减或改变，一般需要重新建立模型。
Brownell和Lowerre研究了在平日需求N不小于周末需求n 的情况下，每周休息两天、连休及周末休息频率对优化目标，满足外界人力需求和休息约束而最少雇佣的工人数目的影响。Browneel和Lowerre 一共讨论了五种情况：（1）平日有N人，周末n人，每周休息两天；（2）除了保证平日有N人，周末n人当班外，工人的每周休息为连休；（3 ）工人每周的连休日不存在（Fr，Sa）和（Su,Mo）的情况；（4）工人在连续两周内必须有一周在周末休息；（5 ）工人不仅在连续两周内必有一周在周末休息，另外两天也必须是连休。针对这五种情况， Brownell 和Lowerre分别用解析法确定满足约束条件的最少工人数（W），然后给出算法，用这W名工人构造可行的作业计划。
Burns所研究的单班次问题，其约束条件更为复杂。Burns一共讨论了四种情况：（1）平日每天需求人数分别为n[,1]－n[,5]，每两周工作10天，连续工作天数不能超过6天；（2）在（1 ）的条件上加上工人每周应该工作5天；（3）在（1 ）的条件上加上工人每两周的另外两天休息日也应该是连休日，在此又分为两个子问题：周末每天需求人数n[,6]＝n[,7]和n[,6]≠n[,7]；（4）在（1）的条件上加上工人每周的连休日不存在（Fr， Sa）和（Su，Mo）的情况。
Narasimhan研究的问题又有所不同。他假设不同级别的工人薪水不同，因此级别高的工人劳动力成本比较高，另外级别高的工人可以代替级别低的工人，反之不可以，即所谓的多种向下替代排班问题。
五、多班次MSP问题
多班次MSP问题即每天有多种班次的工人需换班，比单班次MSP问题多了换班约束：如规定任意连续两天工作内的班次必须相同。 单班次MSP问题中的作息计划为休息日、工作日在作业计划中的顺序，而多班次作息计划除了确定每名工人休息日、工作日的顺序外，还需确定每名工人在每个工作日的具体班次，因此多班次问题比单班次问题复杂的多。
在研究多班次MSP问题的诸多算法中， 有些算法允许工人固定班次（straight shift）。可以将不同班次的工人分成不同的组，若有J 种班次，则工人分成J组，每组的工人按单班次MSP问题排班方法处理，得到每名工人的单班次作业计划。将第i 组的工人在工作日的班次定为第i种班次，就可得到每名工人的具体班次作业计划。 用这类算法来解决多班次问题的优点是简单，可充分利用单班次MSP问题的算法， 缺点则是对于非白班人员存在一系列生理及社会问题。如果不采取固定班次的方法，则必须满足多班次MSP 问题的一个特殊约束条件：换班种必须是休息某段时间后，如至少休息16小时后，才能从白班换到晚班，这样安排其班次计划的算法就比单班次问题要复杂。Monroe采取试探法，在实际运用中，试探法只能解决比较简单的问题，而且还常常得不到最优解，即在某些情况下会出现某个双休日休息的人数为负值，这显然是毫无意义的，必须进行调整。Monroe提出了三种解决方法：（1 ）适当减少工作人数最多的那一天的人数，增加工作人数最少的那一天的人数； （2）雇佣适当的人数加以补充；（3）让某些工人的连休日断开， 每次只休息一天。但无论那种方法都有一定的缺陷。
Buns和Koop研究的多班次MSP问题，将休息和换班约束、 周末休息约束和工作连续时间的约束同时考虑。根据所处理的不同结构编制了多个[p／q]模块，这些模块是编制班次计划的结构单元。每个模块中的元素有两种：表明休息的符号X和链形代号（Chain symbol）， 链形代号表示班次种类，不同的链可以满足不同的约束条件。他们的算法证明：问题所需的劳动力数目只考虑每天的总需求，用单班次的下限就可以满足多班次MSP问题。当然， 安排每名工人具体班次的算法比单班次要复杂的多。
Tibrewala处理的问题原型为：每周连休、每天的时间人力需求R（i，j）可不等，以周为循环期。其建立的模型使非必须休息日最少，而不是直接以minW为目标函数，模型中的变量均为非负整数，属于整数线性规划问题，用迭代法求最优解，缺陷在于迭代次数是R（i，j ）的函数，当R（i，j）数目较大时，迭代次数增加太多。Mills和Panton描述的问题与以上的有所不同：常备劳动力数量固定，临时劳动力数目可变，目标函数是使临时劳动力数量最少，不必考虑临时工人在休息、工作方面的约束。
Warner等涉及的MSP问题是为医院的护士排班， 其特点是多班次多工种可相互替代，目标是确定每班次每个房间每种护士的人数同时使缺人成本最少。实际上这是一个混整型二次规划问题。传统的解法都不是十分有效，又由于约束的变量太多，Warner等人提出新的算法：首先把原问题进行分解，再对每一个子问题求最优解，最后对原问题求最优解。
Segal以电话接线员的排班问题为实例，研究MSP问题。由于打电话的人随着时间的变化而变化，基本上服从泊松分布，因此每隔半小时就要安排一个班次。就每个接线员来说连续工作8小时， 之间可以有一次半小时休息和两次15分钟换班时间。Segal 给出的数学模型实际是一个线性规划求非负整数解的问题，第一步不考虑休息和换班时间，只安排班次，通过一个网络流图求出使成本最少的每班次人数，第二步加上接线员休息和换班的约束，再通过网络流图使得缺人成本最少，第三步具体安排每个班次内什么时候有多少人休息或换班。
Miller认为由于有许多约束条件，很可能难以找到符合所有条件的可行解，因此他把约束条件分为两类：一类是必须满足的条件，如：每两周工作10天，连续工作时间既不能超过7天，也不能少于2天；另一类是可以不满足的条件，如果不满足某个条件将引起成本的增加。目标函数也分为两部分；一部分是全体职工的成本，一部分是排班计划优劣的成本（优：成本低，劣：成本高）。针对这个模型，Miller提出了循环协调递减算法。先找到一个可行的排班计划，计算出成本，再找到另外一个可行的排班计划，计算出成本和第一个进行比较取其小，就这样依次进行下去，直到最后一个可行的排班计划，最小成本的排班计划为最优排班计划。
Thompson把一个班次分成若干时间段，确定每个时间段的时间人力需求后，安排工人在哪个时间段开始时上班、哪个时间段结束时下班以及上班期间什么时间休息、 休息多少时间等等。 针对这个问题， Thompson提出了一个双隐形整数规划班次安排模型（DISSM）算法， 此算法至少在三个方面优于Bechtold和Jacobs提出的BJSSM算法：（1）产生作业计划时间短；（2）能够解决更大型的问题；（3）不会产生最优但不可行的解。Beaumont把一周分成了504个20分钟时间段， 提出一个混整型算法，其目标函数是使劳动力成本和顾客等待成本最少，从而确定雇佣工人数以及每天各个班次的开始时间和每个班次所需的工人数。
一般排班问题，工人只涉及两种状态：当班或休息， 而Wermus 和Pope所研究的给领港员安排班次的问题提出了第三种状态即在家待命，以应付突发事件。目标函数也不是通常的雇佣人数最少或每班次时间人力需求最少，因为领港员人数是固定的，并且三种状态的人数之比也是固定的。其优化目标是：（1）每个工人的作业计划是公平和稳定的； （2）尽可能使连续休息时间最长。
Hung和Emmons研究的是3—4压缩工作周多班次人员班次安排问题。所谓3—4压缩工作周作业计划就是在任意连续两周内，每名工人一周工作4天，休息3天，而另一周工作3天，休息4天，即在任意连续两周内每名工人工作7天，休息7天。Hung和Emmons提出了两种优化算法，一种优化算法是针对休息频率小于等于1／2， 另一种算法针对休息频率大于1／2。这两种算法都存在着一些明显的缺陷：（1）每名工人固定了班次，即1至m号全上白班，m到w号工人全上晚班，排出的计划不公平；（2 ）每天每班次的工人数固定，这在实际情况中出现的机会比较少。
六、研究现状总结
1980年前对MSP问题的研究，主要是将MSP问题作为组合优化问题来研究，故有关的模型大部分是以整数规划形式出现。在实际应用中，有时会涉及成千上万个整数变量，即使用计算机来辅助安排工作计划，花费的时间也很多，有时还不一定能得出可行解。时间决定了一个算法能否在实际中的应用，从这个意义上讲，只要能求得最优或近优解，花费时间越少的算法就越有效。八十年代至今，更多的人开始研究一些有特殊结构的MSP问题，提供的算法操作较简单。 虽然它们往往只适用于有限的情况，但可以作为一般问题的近似算法，或提供某种思路。针对实际的具体问题， 抽象出有特殊结构的模型并提出相应的算法是现在MSP问题的主要研究方向。
虽然国外研究MSP问题的文章很多，算法和模型也各异， 但是很多学者都想寻求一种通用步骤，综合Lau和Thompson 所提出的一般步骤可归纳出常用求解框架如下：（1）估计时间人力需求R（i，j）；（2 ）明确R（i，j）和其它约束条件后，确定总的人力需求N；（3 ）确定在计划期I天内（I一般是7的倍数），每种休息方式的工人数目；（4）给阶段（3）中的各休息方式排序，使之能组成I天的可行作业计划，换句话说，就是为N名工人确定工作日及休息日的顺序；（5）在满足每个班次、任何时间的人力需求及换班约束等条件下，用N×I矩阵表示每名工人在I天内的具体班次计划。这五个步骤较全面的概括了MSP问题所涉及的内容，并提供了一种常用求解人员班次问题的顺序。
国外对MSP问题的研究不仅仅停留在理论上， 在实际中也得到了广泛的应用。有的为航空公司的人员安排作业计划，有的为医院护士安排作业计划，有的为报话员安排作业计划，有的为兼职实验室助理安排作业计划，还有的为港口领港员安排作业计划，这些针对某个特殊问题提出的算法在实践中产生了很大的效益。如Holloran和Byrn给美国联合航空公司设计的人员排班系统投入使用后，带来了一系列效益，其中包括：（1）降低雇佣人员数6%；（2）每年节省600万美元的劳力成本（包括直接工资、相关福利、管理费用等费用）；（3 ）提高了职工的满意度；（4）增加了顾客的满意度。
七、研究展望
由于现实生活中班次安排问题形式多种多样，所以就有许许多多尚未解决的问题有待今后去研究：
1.管理人员的工作比一般工人的工作灵活性更强，如何测定管理人员的时间人力需求（与管理人员的工作能力、职责范围有关），给他们安排作业计划，同时根据管理人员和工人对不同休息策略或不同约束条件所赋予的权数，建立模型找出总体目标最优的策略及对应的算法。
2.在以往的研究中，目标函数各异，如何把这些不同的目标转换成一种通用的目标，以便提出更通用的算法。
3.在以往的研究中，绝大多数都是针对服务性企业，如何给制造性企业安排人员作业计划，以及要考虑哪些约束条件。