基于分治法的多班次考勤管理算法

陆赟

摘要：企业考勤管理系统是中大型企业管理员工的最基本的信息化管理工具，是保证员工工作状态和工作效率的前提。如何及时地、科学地管理企业员工的考勤已经成为中大型企业面临的重要课题。市面上很多考勤系统无法对拥有很多班次的中大型企业进行考勤管理，该文提出了基于分治算法的多班次考勤管理算法，将与员工考勤管理相關因素利用分治的思想，将大问题分解成小问题，最终解决了中大型企业的考勤管理问题。

关键词：考勤管理;分治法;班次

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2020）26-0228-03

1 背景

随着计算机的普及和发展、社会经济的不断进步，各个单位对管理质量的要求越来越高，一个经济、高效的考勤管理系统在企事业单位完善信息化管理起着至关重要的作用[1]。企业为了管理员工考勤，安装了考勤机，如指纹考勤机、人脸识别考勤机等，还购买考勤管理系统来管理企业考勤。对于百人以下的企业，只要在考勤管理系统中进行简单设置就能快速生成考勤报表。但是中大型的企业，尤其是生产型企业，员工众多，还存在轮班制和跨天上下班的情况，甚至对于特殊的岗位需要多时间段的班次，这些情况一般考勤系统生成考勤报表费时间，动辄2个小时以上，而且生成的员工月度考勤报表也不正确，如现在普遍应用的中控考勤系统软件。 这样考勤员就需要人为地将员工的每日排班和指纹记录进行比较分析最终得出考勤统计报表，大大浪费了人力成本。为了弥补考勤系统软件的不足，现在企业考勤管理的需求，尤其是存在很多班次的中大型生产型企业的需求，本文提出了基于分治法的多班次考勤管理算法。实际应用表明，该算法速度快，正确性高，满足中大型企业的一般的考勤需求，实现了考勤管理的目标，使得考勤自动化管理变为现实。

2 考勤管理问题

2.1 考勤管理问题描述

随着公司规模的不断扩大，员工数量及岗位都在不断地增加，为了符合每个岗位的特殊要求，设定的班次也多种多样，一般中大型的生产型企业需要用的班次就有上百种，另外员工排班、请假、指纹或人脸识别等生物识别的考勤记录等都与员工考勤息息相关，统计公司里所有员工考勤，快速正确生成企业员工的月度考勤也变得越来越复杂。本文以指纹考勤机为例，纪录员工每次考勤，利用基于分治法的多班次考勤管理算法来解决复杂的考勤管理问题。

2.2 考勤管理数据结构的定义

定义1  Sum：员工总数

定义2  n0：员工组中员工的个数

定义3  d：考勤天数

定义4  AllPer[Sum*8] ：表示员工的基本信息的Sum*8二维数组，包括：员工号、员工姓名、公司编码、部门、序列、岗位、入职日期、离职日期

定义5  PerArr[] ：表示n0规模的员工号组的一维数组，每个元素用“‘员工号1，‘员工号2，...‘员工号n”表示，便于一次性在数据库中查询或删除n0个员工对应相关信息，其中，◇ 为上取整函数， 为员工组的个数

定义6  PERNRArr[] ：表示n0规模的员工号及指纹编码组的一维数组，每个元素用“select ‘员工号1 as PERNR，‘指纹编码1 as UserID  union all select ‘员工号2 as PERNR，‘指纹编码2 as UserID... ”表示，其中，◇ 为上取整函数，为员工号及指纹编码组的个数

定义7  EX[m*7]：表示n0个员工的请假记录的m*7二维数组，m表示月请假记录数，0～6分别表示员工号、指纹编码、开始日期、结束日期、请假日期、请假标识、请假ID

定义8  MPB[n*10]：表示n0个员工的月排班记录的n*10二维数组， n表示月排班记录数，0～9分别员工号、指纹编码、开始日期、结束日期、上班时间、下班时间、上班有效时长、下班有效时长、班次名称、班次ID

定义9  PB[Pn*9] ：表示n0个员工的日排班记录的Pn*9二维数组， Pn表示日排班记录数，0～8分别员工号、指纹编码、开始时间、结束时间、班次日期、上班有效时长、下班有效时长、班次名称、班次ID

定义10  Start[Pn*4] ：表示n0个员工的日排班记录对应的有效签到记录的Pn*4二维数组，0～4：员工号、上班时间、 签到时间、上班时间差异

定义11  End[Pn*4] ：表示n0个员工的日排班记录对应的有效签退记录的Pn*4二维数组， 0～4：员工号、下午时间、签退时间、下班时间差异

定义12  biaoshi[32] ：表示员工的月考勤标识的一维数组，1～31分别存储当月1日到31日的考勤标识，如果当月只有30天，则biaoshi[31]为”/”

定义13  arrb[22] ：表示员工考勤异常情况的统计的一维数组，1～21：员工事假、病假、婚假、迟到、早退、旷工等各类考勤异常情况的统计值

定义14  KQReport[n0*61] ：表示n0位员工的月度考勤汇总的n0*64二维数组， 0～5：AllPer[0]-[5]员工号、员工姓名、公司编码、部门、序列、岗位， 6：strYear年，7：strMonth月，8～38：biaoshi[1]-[31]考勤标识，39-59：21个考勤异常统计，60：出勤天数

3 考勤管理问题的分治思想

3.1 分治法基本思想

分治法的基本思想是将一个难以直接解决的大问题，分解成一些规模较小的相同子问题，以便各个击破，分而治之[2]。

分治法通常用于求解具有以下特征的问题，一般来说，是否满足这几个特征，是问题能否用分治法求解的基本要素：

1）小规模可解易解：问題的规模缩小到一定程度，即可以直接求解;

2）最优子结构：原问题可以分解为若干个互相独立且是原问题较小模式的子问题，这是分治法的前提;

3）解可以合并：如果子问题可解，那么原问题也可解，并且原问题的解可以由各个子问题的解合并得到，这是能否使用分治法的关键要素。

分治法在实际工作中主要是通过解决与原问题密切联系且覆盖原问题的子问题来解决约束复杂难以直接解决的组合问题。但是在使用分治算法的时候递归算法也容易同时在设计中，给程序带来运行效率低，耗时多并大量的占用存储空间等一系列问题。文献[3-5]提出了一种消除递归的新方法，在分治算法的基础上实现非递归，实现在计算机处理某些比较复杂的问题时，减少某些程序的反复执行，进一步节约空间和减少时间复杂度。

因此如果待解决的问题完全具备分治法求解的3个要素就可以利用分治法求解，并且可以利用消除递归的方法设计算法提高算法的执行效率。

3.2 考勤管理与分治思想

解决考勤管理问题是生成一个满足约束条件的，将员工信息、员工排班、请假记录、指纹记录组合分析的考勤统计报表，即包含每个员工每个月每天的考勤状态，以及整个月考勤异常和出勤天数的汇总。无疑此类问题是个难以直接解决的规模较大的问题，并且完全具备用分治法求解的3个基本要素。因此，本文依据中大型生产型企业考勤管理的要求，在充分研究和优化考勤管理问题及其约束条件的基础上，提出了考勤管理的分治算法，并且利用消除递归的方式实现了非递归，算法总体采用分治法思想如下：

1）首先将公司所有员工的月考勤管理问题分解为员工组所有员工的月考勤管理问题。这样可以按员工组查询员工组所有员工的请假记录、排班记录、指纹记录，减小查询的规模;

2）员工组所有员工的月考勤管理问题，分解为员工组内每个员工的月考勤管理问题;

3）某个员工的月考勤管理问题，可以分解为这个员工的每日考勤管理问题;

4）某个员工某日考勤管理问题，可以分解为该日各个时间段的考勤管理问题;

5）分别对这个员工的该日各个时间段的考勤进行分析求解，然后将各个时间段考勤的标识进行合并得到该日的考勤标识。

6）分别对这个员工的每日的考勤进行分析求解，然后将每日考勤的标识进行合并统计出每个员工的各考勤异常的值，这样由这个员工的员工信息、每日考勤标识、考勤异常统计值组成的考勤统计报表即完成了对该员工的月考勤管理;

7）分别完成对员工组内每个员工的考勤的分析求解，即完成了对该员工组员工的月考勤管理;

8）分别完成对所有员工组员工的考勤的分析求解，即完成了对所有员工的月考勤管理。

4 多班次考勤管理的分治算法

4.1 算法的主要步骤

根据考勤管理的分治思想设计分治算法，具体步骤如下：

1）查询当月在职的员工基本信息，赋值给二维数组AllPer[Sum*8];

2）将Sum个员工根据设定的标准规模n0进行分组PERNRArr[]，以便按规模读取员工的指纹用户信息、请假记录和排班记录、指纹记录;

3）分析AllPer中第count个员工的月度考勤报表，初始count=0;

4）判断count是不是n0规模员工组的第一个员工，即count%n0是否为0。如果是，则跳转到步骤5，如果否，则跳转到步骤10;

5）如果员工组的第一个员工，则读取当前n0规模员工组的指纹用户信息;

6）根据当前n0规模员工组的指纹用户信息读取当月请假记录EX[m*7];

7）根据当前n0规模员工组的指纹用户信息读取当月排班记录，将月排班记录分解成日排班记录PB[Pn*9]（某日的排班记录以申请日期最晚一次为准）;

8）根据当前n0规模员工组的日排班记录中班次的上班时间及上班有效时长读取有效签到指纹记录及上午时间差异等Start（Pn*4），与日排班记录一一对应;

9）根据当前n0规模员工组的日排班记录中班次的下班时间及下班有效时长读取有效签退指纹记录及上午时间差异等End（Pn*4），与日排班记录一一对应;

10）初始化第count个员工的月考勤标识biaoshi[1]-[31]为“/”，依次分析当月1日到当日前一天（strDay）的考勤状态：①将请假记录EX[m][7]中属于当前员工当日的有效请假记录（某日的请假记录以申请日期最晚一次为准）的请假标识对应到标识中中，如1号请假标识存储到biaoshi[1]中;②如果当日无请假标识且不为旷工，则根据当日班次的各个时间段的上班时间差异和下班时间差异判断考勤标识，并合并到当日的biaoshi中;

11）根据当月每日的考勤标识biaoshi[1]-[31]对考勤异常进行统计，将结果存储到arrb[1]-arrb[21]中，并且算出出勤天数dates;

12）月度考勤统计报表KQReport[count/n0][0]-[5]存储AllPer[count][0]-[5]的员工信息，KQReport[count/n0][6]存储当年strYear信息，KQReport[count/n0][7]存储当月strMonth信息，KQReport[count/n0][8]-KQReport[count/n0][38]存储分析完的月考勤标识biaoshi[1]-[31]，KQReport[count/n0][39]-KQReport[count/n0][59]存储考勤异常的统计值arrb[1]-arrb[21]，KQReport[count/n0][60]存储出勤天数dates;

13）重复执行（4）～ （12）步，直到分析生成所有员工的考勤统计报表。

4.2 算法的优势

由于考勤管理涉及的信息都存储在数据库中，考勤汇总之前需要先从数据库中读取数据存储到计算机内存中。而连接数据库和读取数据表中数据的次数以及数据在内存中的存储关系到计算的时间和空间复杂度。本算法通过分治思想按员工组的规模读取员工对应的排班、请假和指纹记录，对该规模内员工的考勤进行汇总，直到完成对所有员工的考勤汇总。该算法在正確生成考勤统计报表的同时，极大地降低了考勤汇总的时间和空间复杂度。

另外，算法还体现了其他优势：

1）不会因为考勤人员的增多，影响程序整体的运行结果;

2）由于考勤相关的员工信息、排班记录、考勤记录、指纹记录等信息均处理为数组，而基于管理数据库的3种关系（表、查询、视图），其实质就是类似数组的二维表，因此，算法易于在基于数据库的计算机系统中实现;

3）算法的通用性强，对大多数的企业的考勤管理都适用;

4）算法可以推广到各种类似问题的解决。

5 结束语

本文提出的基于分治算法的多班次考勤管理算法能够解决中大型企业考勤管理问题。经实际应用证明，利用该算法编写出的考勤管理系统能够快速并正确地分析出企业员工每日的考勤结果，最终生成考勤统计报表，从而大大地提高了人力资源管理的效率，降低了公司的人力成本。

参考文献：

[1] 梁静. 基于指纹识别的高校考勤系统的设计与实现[D]. 南京： 南京理工大学， 2010.

[2] 王红梅， 胡明. 算法设计与分析[M]. 北京： 清华大学出版社， 2013.

[3] 陈燕晖， 邢晶， 罗宇. 一种消除递归的新方法[J]. 计算机工程与应用， 2006， 42（4）： 73-75， 141.

[4] 汤亚玲. 递归算法设计及其非递归化研究[J]. 计算机技术与发展， 2009， 19（11）： 85-88， 93.

[5] 孙召伟， 赵建利， 朱东生. 数据结构中递归转非递归算法分析及模型设计研究[J]. 河北科技大学学报， 2011， 32（1）： 43-46.

【通联编辑：谢媛媛】