用多维穷举法在排班问题中的应用

裴南平+毕传林

摘要：穷举法是一种简单易懂、应用广泛的常用算法，对于较复杂的问题，穷举法的适用性受很多限制，不能有效解决实际问题。因此探索使用多维穷举法来解决实际工作经常遇到的排班问题，并以“蓝桥杯”全国软件专业人才设计与创业大赛全国总决赛中的一道综合编程题为例，解析二维穷举法的求解方法和具体实现。

关键词：算法；多维穷举法；排班

中圖分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）26-0082-02

Abstract： Exhaustive method is a simple and easy to understand and widely used algorithm. For more complex problems， the applicability of exhaustive method is limited， and it can not effectively solve the problems. Therefore， the multidimensional exhaustive method is used to solve the scheduling problem. The question of “Lanqiao” competition as an example， methods for solving two-dimensional analytic exhaustive method and implementation.

Key words： Algorithm； multidimensional exhaustion method； scheduling

排班问题是多年来一直被研究的问题，在学校、机关、企事业单位有着广泛的应用，涉及的人员有教师、机房管理员、医生、乘务人员、飞行员等无固定休息时间的工作人员。对其进行合理的排班。因此排班工作是学校、机关、企事业单位的一项必要的日常工作，又因其限制条件的复杂性，手工安排费时费力，还容易出错，也很难找到最优的方案，合理的排班不仅可以提高效率、降低成本，还可以提高员工工作的幸福感，所以利用计算机进行自动排班的思想自然而生，使得排班系统被引入各行业里面。

目前解决自动排班的算法有基于优先级自动排班算法PCSA的设计与实现方案，回溯算法，基于多目标优化的遗传算法，模拟退火算法等。我们在此采用多维穷举法来解决排班问题。

1 多维穷举的法基本思想

可以把一次多重循环穷举求解问题定义为一维穷举，先后进行二次一维穷举求解问题定义为二维穷举，以此类推，可定义出多维穷举。

为什么要采用多维穷举？有人说，所有的多维问题都可展开成一维，只需要一维穷举就够了。这话不错，只不过穷举法具体编程实现受多重循环层数的限制，例如一个m*n的二维问题，假设m=5，n=6，展开成一维，就是m*n=5*6=30层的问题，30层问题用穷举法需要30重循环，显然难以实现。这时采用二维穷举，先进行一次m=5层的一维穷举，再进行一次n=6层的一维穷举，就把m*n层的问题变成m+n层的简单问题。

当然多维穷举不是简单的一维一维嵌套，而是在每一次一维穷举时，按问题的具体条件排除很多非法的排列组合，下一次一维穷举以此为基础，再按问题的条件排除更多的非法排列组合，所以多维穷举算法的效率要快速得多，而且算法的思路是按问题本身的多维特性对应求解，实现起来简单方便、准确可靠。

下面用“蓝桥杯”全国软件专业人才设计与创业大赛全国总决赛中的一道排日程的综合编程题为例，解析二维穷举的具体实现。

2 排班问题举例

某保密单位机要人员 A，B，C，D，E 每周需要工作5天，休息2天。上级要求每个人每周的工作日和休息日安排必须是固定的，不能在周间变更。此外，由于工作需要，还有如下要求：

1） 所有人的连续工作日不能多于3天（注意：周日连到下周一也是连续）。

2） 一周中，至少有3天所有人都是上班的。

3） 任何一天，必须保证 A B C D 中至少有2人上班。

4） B D E 在周日那天必须休息。

5） A E 周三必须上班。

6） A C一周中必须至少有4天能见面（即同时上班）。

你的任务是：编写程序，列出ABCDE所有可能的一周排班情况。工作日记为1，休息日记为0，A B C D E 每人占用1行记录，从星期一开始。

3 算法分析

这是一个5行7列的二维表格问题，表中共有5*7=35个元素，每个元素只有上班1和休息0二种取值，可以采用35层循环的一维穷举实现，2的35次方的排列组合（相当于10的10次方）在普通电脑运行短时间是出不了结果的。程序编写也比较困难，除非使用回溯法。

二维穷举实现算法如下：

1） 先进行一维的行穷举，将每个人一周所有可能的安排排列组合，也就是从0000000到1111111之间的所有二进制数，筛选出符合一周五天上班二天休息和连续上班不多于三天的排列组合，保存到一个数组中，作为下一维穷举的取值。本维穷举有7层，也就是7重循环，排列组合的个数（循环次数）共有2的7次方128个，筛选后合法的取值只有1110110、1101110、1101101、1011101、1011011、0111011、0110111共7个。

2） 然后进行第二维的列穷举，将A、B、C、D、E五个人所有可能的上班日程（上一维穷举得到的保存在数组中的7个取值）排列组合，筛选出符合所有条件的安排，按格式输出5行7列的周安排表。本维穷举有5层，也就是5重循环，排列组合的个数（循环次数）共有7的5次方16807个，筛选后得到本题的答案只有下面4个：

相比一维穷举需要循环2的35次方（10的10次方）量级；二维穷举只需要2的7次方（128）+7的5次方（16807）=16935次，因此程序很快就出结果。

4 源程序

参考文献：

[1] 李青，张军，张学军.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报， 2003（10）.

[2] 李智敏.浅谈呼叫中心智能排班系统的主要技术[J].电子世界，2017（3）.

[3] 李耀华，谭娜.基于遗传算法的飞机一体化排班优化方法[J].控制工程，2017（2）.endprint