一种排班约束模型诊断及边界求解方法、装置和存储介质与流程

摘要: 本发明涉及计算机辅助排班领域,特别涉及一种排班约束模型诊断及边界求解方法、装置和存储介质。背景技术:1、在需要按照日期、班次、人员资格、休息周期和岗位需求进行人...
一种排班约束模型诊断及边界求解方法、装置和存储介质与流程

本发明涉及计算机辅助排班领域,特别涉及一种排班约束模型诊断及边界求解方法、装置和存储介质。

背景技术:

1、在需要按照日期、班次、人员资格、休息周期和岗位需求进行人员配置的应用场景中,通常需要利用排班系统对参与排班人员进行班次分配。排班系统一般根据人员信息、排班周期、各班次需求人数以及排班规则建立排班模型,并在满足既定约束条件的前提下生成排班结果。

2、在实际应用中,一类问题是排班模型在当前人员规模下无法获得可行排班结果。造成该问题的原因可能是参与排班人员数量不足,也可能是人员状态、请假、禁止排班、固定排班或班次匹配等规则之间无法同时满足。另一类问题是在当前人员规模可以获得可行排班结果时,需要进一步判断在保持排班约束可满足的条件下人员规模能够降低到何种程度。

3、现有的人员规模确定方案中,有的通过仿真器模拟服务过程并结合二分法确定候选人数,有的以任务衔接约束和排班间隔约束建立优化模型,还有的通过排队论、整数规划或遗传算法估算人员数量。上述方式通常侧重于获得一个满足服务水平或目标函数的人数结果,但对于排班模型未获得可行解时是由人员数量不足导致还是由保留的硬约束条件无法同时满足导致,缺少直接基于排班约束模型的诊断机制;同时,仅根据统计估算或非排班约束层面的结果确定人员规模,可能不能保证所得人员规模在全部排班硬约束下仍能够形成可行排班。

技术实现思路

1、本发明的目的在于提供一种排班约束模型诊断及边界求解方法、装置和存储介质,以解决现有排班处理过程中难以基于同一排班约束模型区分人员规模不足与保留的硬约束条件无法同时满足、以及难以进一步确定人员规模边界的问题。

2、为了实现上述目的,本发明提供如下技术方案:一种排班约束模型诊断及边界求解方法,由电子设备执行,包括:获取目标排班周期对应的排班数据,所述排班数据包括参与排班人员数据、班次需求数据以及排班约束数据;基于所述排班数据构建排班约束满足模型,并通过调整所述排班约束满足模型中的班次需求人数约束和求解目标,得到排班诊断模型,所述排班诊断模型保留所述排班约束满足模型中的其余硬约束条件,并以缺人量最小作为求解目标,所述缺人量表征目标排班周期内具有班次需求下限的各日期和班次对应的班次需求未满足量的累计值;对所述排班诊断模型进行约束求解,获取模型求解状态,并在所述排班诊断模型获得最优解或可行解时获取所述缺人量;根据所述模型求解状态,并在所述排班诊断模型获得最优解或可行解时结合所述缺人量,确定当前人员规模下的模型状态;基于所述模型状态确定是否执行人员规模搜索,并在确定执行人员规模搜索时确定人员规模搜索方向,沿所述人员规模搜索方向调整候选人员规模,并对各候选人员规模对应的排班诊断模型进行求解,根据对应的求解结果确定人员规模边界。

3、进一步地,所述排班数据还包括台架配置、排班周期参数以及班组规则参数;所述参与排班人员数据包括人员标识数据、人员类别数据、人员状态数据以及人员可参与排班时间数据;所述班次需求数据包括不同班次对应的需求人数;所述排班约束数据包括人员状态约束、班次需求约束、排班周期约束、班次连续性约束、人员与班次之间的匹配约束以及班次人数平衡约束;在构建所述排班约束满足模型之前,根据所述排班周期参数生成排班日历,对所述参与排班人员数据进行人员分类,并根据所述台架配置和所述班组规则参数确定所述班次需求数据。

4、进一步地,对所述班次需求人数约束的调整包括:针对具有班次需求下限的日期与班次组合设置整数型缺人变量,所述整数型缺人变量的取值范围为零至对应班次的需求人数;将对应日期内被分配至对应班次的人员数量与对应的整数型缺人变量之和约束为对应班次的需求人数;对各所述整数型缺人变量进行累计得到所述缺人量;其中,仅具有班次人数上限且不具有班次需求下限的日期与班次组合不设置所述整数型缺人变量。

5、进一步地,对所述排班诊断模型进行约束求解,包括:采用基于约束传播和布尔可满足性技术的cp-sat求解器对所述排班诊断模型进行求解;设置单轮求解的时间上限,并基于不同随机种子执行多轮独立求解;从获得最优解或可行解的各轮独立求解中选取缺人量最小的求解结果作为目标求解结果;在任一轮独立求解得到的缺人量为零时,停止后续轮次的求解;在任一轮独立求解被判定为无可行解时,停止后续轮次的求解,并将所述模型求解状态确定为无可行解状态。

6、进一步地,所述当前人员规模下的模型状态的确定包括:在所述排班诊断模型获得最优解或可行解且所述缺人量为零时,确定所述模型状态为无缺人状态;在所述排班诊断模型获得最优解或可行解且所述缺人量大于零时,确定所述模型状态为缺人状态;在所述排班诊断模型被求解器判定为无可行解时,确定所述模型状态为无解状态,所述无解状态表征当前人员规模对应的排班诊断模型不存在同时满足其保留的硬约束条件的可行解,且此时不依据所述缺人量确定所述模型状态;在所述排班诊断模型在求解时间上限内未获得最优解或可行解且未被判定为无可行解时,确定所述模型状态为求解未完成状态;在所述模型状态为缺人状态或求解未完成状态时,确定所述人员规模搜索方向为增大参与排班人员数量的方向;在所述模型状态为无解状态时,确定不执行人员规模搜索;在所述模型状态为无缺人状态时,确定所述人员规模搜索方向为减小参与排班人员数量的方向。

7、进一步地,在确定执行人员规模搜索时,所述人员规模边界的确定包括:根据所述人员规模搜索方向设置搜索下界和搜索上界,并采用二分搜索方式根据所述搜索下界和所述搜索上界确定候选人员规模;按照所述候选人员规模生成候选排班人员数据,对所述候选排班人员数据进行排班数据预处理,并基于预处理后的候选排班人员数据构建和求解对应的排班诊断模型;在对应的排班诊断模型获得最优解或可行解且缺人量为零时,记录所述候选人员规模并减小所述搜索上界;在对应的排班诊断模型获得最优解或可行解且缺人量大于零,或者在求解时间上限内未获得最优解或可行解且未被判定为无可行解时,增大所述搜索下界;在对应的排班诊断模型被求解器判定为无可行解时,确定对应的候选人员规模下的模型状态为无解状态;在对应的候选人员规模下的模型状态为无解状态时,若所述人员规模搜索方向为增大参与排班人员数量的方向,则停止人员规模搜索;若所述人员规模搜索方向为减小参与排班人员数量的方向,则增大所述搜索下界并继续人员规模搜索;重复确定所述候选人员规模以及更新所述搜索下界和所述搜索上界,直至所述搜索下界大于所述搜索上界或达到预设迭代次数时停止,并根据记录的候选人员规模确定所述人员规模边界。

8、进一步地,在所述人员规模搜索方向为增大参与排班人员数量的方向时,将当前参与排班人员数量设置为所述搜索下界,并根据所述当前参与排班人员数量和预设人员增量确定所述搜索上界;按照所述候选人员规模生成所述候选排班人员数据时,保留固定参与排班人员,并按照预设顺序从轮换人员池中选取轮换人员,在所述轮换人员池中的可用轮换人员数量不足以达到所述候选人员规模时,生成合成人员数据以补足参与排班人员数量;其中,所述轮换人员池由所述参与排班人员数据中状态为可参与排班、且非固定参与排班的人员构成,状态为不参与排班的人员不纳入所述轮换人员池;采用二分搜索方式在所述搜索下界和所述搜索上界之间确定候选人员规模,并根据各候选人员规模对应的排班诊断模型的求解结果更新所述搜索下界和所述搜索上界,将获得最优解或可行解且缺人量为零的候选人员规模中的最小值确定为所述人员规模边界;在预设二分搜索迭代次数内未获得缺人量为零的求解结果,且未因对应的候选人员规模下的模型状态为无解状态而停止人员规模搜索时,停止二分搜索并转入线性步进搜索,将候选人员规模的上限扩展至预设最大搜索上界,按照预设步长依次增大候选人员规模,并提高对应的排班诊断模型的单轮求解时间上限;在候选人员规模不大于所述预设最大搜索上界且获得缺人量为零的求解结果时,记录对应的候选人员规模,并根据记录的候选人员规模确定所述人员规模边界;在候选人员规模达到所述预设最大搜索上界时,若对应的排班诊断模型获得最优解或可行解且缺人量大于零,则确定在所述预设最大搜索上界内未获得缺人量为零的候选人员规模,并停止人员规模搜索;若对应的排班诊断模型被求解器判定为无可行解,则将对应的候选人员规模下的模型状态确定为无解状态,并停止人员规模搜索;若对应的排班诊断模型在求解时间上限内未获得最优解或可行解且未被判定为无可行解,则确定对应的候选人员规模下的模型状态为求解未完成状态,并停止人员规模搜索。

9、进一步地,在所述人员规模搜索方向为减小参与排班人员数量的方向时,根据所述班次需求数据确定日需求人数,根据所述日需求人数与固定参与排班人员数量确定轮换人员的日需求数量,并根据所述轮换人员的日需求数量以及轮换人员每周可参与排班天数确定理论人员规模下限,并将所述理论人员规模下限与预设的最低可排班人数阈值进行比较,取较大者作为最终的理论人员规模下限;将所述理论人员规模下限设置为所述搜索下界,并将当前参与排班人员数量设置为所述搜索上界;按照所述候选人员规模生成所述候选排班人员数据时,保留固定参与排班人员,并按照预设顺序从当前轮换人员池中选取与所述候选人员规模相匹配的轮换人员;在当前参与排班人员数量大于所述理论人员规模下限时,采用二分搜索方式在所述搜索下界和所述搜索上界之间确定候选人员规模,并根据各候选人员规模对应的排班诊断模型的求解结果更新所述搜索下界和所述搜索上界,将获得最优解或可行解且缺人量为零的候选人员规模中的最小值确定为所述人员规模边界;在当前参与排班人员数量不大于所述理论人员规模下限时,停止对所述人员规模边界的搜索,并将所述理论人员规模下限确定为所述人员规模边界。

10、本发明还提供一种排班约束模型诊断及边界求解装置,包括:排班数据获取模块,用于获取目标排班周期对应的排班数据,所述排班数据包括参与排班人员数据、班次需求数据以及排班约束数据;排班诊断模型构建模块,用于基于所述排班数据构建排班约束满足模型,并通过调整所述排班约束满足模型中的班次需求人数约束和求解目标,得到排班诊断模型,所述排班诊断模型保留所述排班约束满足模型中的其余硬约束条件,并以缺人量最小作为求解目标,所述缺人量表征目标排班周期内具有班次需求下限的各日期和班次对应的班次需求未满足量的累计值;约束求解模块,用于对所述排班诊断模型进行约束求解,获取模型求解状态,并在所述排班诊断模型获得最优解或可行解时获取所述缺人量;模型状态确定模块,用于根据所述模型求解状态,并在所述排班诊断模型获得最优解或可行解时结合所述缺人量,确定当前人员规模下的模型状态;人员规模搜索与边界确定模块,用于基于所述模型状态确定是否执行人员规模搜索,并在确定执行人员规模搜索时确定人员规模搜索方向,沿所述人员规模搜索方向调整候选人员规模,并对各候选人员规模对应的排班诊断模型进行求解,根据对应的求解结果确定人员规模边界。

11、本发明还提供一种计算机可读存储介质,所述计算机可读存储介质中存储有计算机程序,所述计算机程序被处理器执行时,实现上述任一种排班约束模型诊断及边界求解方法。

12、本发明通过在原有排班约束满足模型的基础上调整班次需求人数约束和求解目标,在保留其余硬约束条件的情况下构建排班诊断模型,并在获得最优解或可行解时利用缺人量表征当前人员规模对班次需求的满足程度,同时结合模型求解状态确定当前人员规模下的模型状态。进一步地,通过根据模型状态选择人员规模搜索方向,并结合二分搜索、候选人员数据重构以及排班诊断模型重复求解确定人员规模边界;对于候选人员规模对应的排班诊断模型被判定为无可行解的情况,统一将对应的候选人员规模下的模型状态确定为无解状态,并根据人员规模搜索方向执行停止搜索或搜索下界更新,从而避免在减小人员规模过程中因候选人员规模对应的无解状态而提前终止搜索,提高排班约束诊断及人员规模边界确定结果的可靠性。