用多維窮舉法在排班問題中的應用

裴南平+畢傳林

摘要：窮舉法是一種簡單易懂、應用廣泛的常用算法，對于較復雜的問題，窮舉法的適用性受很多限制，不能有效解決實際問題。因此探索使用多維窮舉法來解決實際工作經常遇到的排班問題，并以“藍橋杯”全國軟件專業人才設計與創業大賽全國總決賽中的一道綜合編程題為例，解析二維窮舉法的求解方法和具體實現。

關鍵詞：算法；多維窮舉法；排班

中圖分類號：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