1、基于多條件約束的值班計(jì)劃的一種算法    摘 要：值班規(guī)則的不同，值班計(jì)劃會(huì)有很大的不同，本文針對(duì)多條件約束的值班規(guī)則，首先分析了傳統(tǒng)串行算法的流程，點(diǎn)出了串行算法的邏輯結(jié)構(gòu)復(fù)雜與在較大規(guī)模數(shù)據(jù)上顯出的效率不足，隨后提出了更為高效、準(zhǔn)確的分塊算法，分塊算法是建立在值班日期與值班人員分離的思想基礎(chǔ)之上，分塊算法能夠高效地完成復(fù)雜值班規(guī)則的較大規(guī)模的值班計(jì)劃。關(guān)鍵字：值班規(guī)則；串行算法；分塊算法中圖分類號(hào)：TP302.21 引言現(xiàn)實(shí)生活中的需要制定值班計(jì)劃的很多單位中，根據(jù)自己單位的具體情況，會(huì)制定出適合自己單位的值班的各種規(guī)則，依賴規(guī)則，形成每一次的值班計(jì)

2、劃，但大多數(shù)單位的值班計(jì)劃都是由某位工作人員負(fù)責(zé)，利用EXCEL 或者統(tǒng)計(jì)報(bào)表來手動(dòng)進(jìn)行制定當(dāng)時(shí)的值班計(jì)劃，對(duì)于人數(shù)僅為數(shù)十人的規(guī)模，值班計(jì)劃的制作效率差強(qiáng)人意，當(dāng)值班人員規(guī)模較大時(shí)，則人工制作值班計(jì)劃的模式，不僅效率低，而且由于人為因素的復(fù)雜，容易出現(xiàn)差錯(cuò)。值班在社會(huì)中有著廣泛的使用，如醫(yī)院的24 小時(shí)值班【1-3】，政府部委的辦公室值班工作【4-5】，除了人員值班之外，在高校的課表編排【6-8】，飛機(jī)排班【9-11】等中也能察覺到值班的影像。由于值班計(jì)劃依賴于具體的值班規(guī)則的不同，則構(gòu)造的值班的算法就會(huì)不同。隨著信息時(shí)代的發(fā)展，某單位需要安排值班人員近百人，則不宜采用手工制定值班計(jì)劃的模式

3、，而且該單位要達(dá)到自動(dòng)排班，實(shí)現(xiàn)公平有序，避免人為因素的干擾，值班計(jì)劃按照值班規(guī)則制定方案，要求平均分配各種班次，盡可能使每位值班人員所值班次的種類和數(shù)量相等的目的。2 值班規(guī)則值班計(jì)劃以月為單位，能夠提前了解下一個(gè)月或更多月份的值班計(jì)劃，每班次需要處級(jí)與科級(jí)人員各一人，要求科級(jí)與處級(jí)值班人員性別一致，對(duì)于每月的值班計(jì)劃，都可以事先預(yù)約某日的某班次或者可以剔除某人值班某日的某班次，當(dāng)安排值班計(jì)劃中的非預(yù)留班次時(shí)，都要從相應(yīng)的班次類別下的值班計(jì)數(shù)最少的人員開始排起，若計(jì)數(shù)相同的，按照姓氏拼音順序排列。當(dāng)一組值班人數(shù)少于當(dāng)月計(jì)劃值班數(shù)時(shí)，則將該組所有值班人員進(jìn)行新一輪排列。安排完一個(gè)月的值班計(jì)劃后

4、，更新值班人員在各班次類別上的計(jì)數(shù)。其中班次類別分為三類：法定節(jié)假日值班，周六日值班和工作日夜班。除工作日外，其余班次均有白班和夜班。對(duì)于元旦、春節(jié)、清明、五一、端午、中秋、國慶等假期設(shè)置為不同優(yōu)先等級(jí)。在同一個(gè)月份中，按照節(jié)日的優(yōu)先級(jí)來排序，以防止不同的法定節(jié)假日沖突，值班班次種類劃分為工作日夜班、普通公休日白班、普通公休日夜班、元旦假期白班、元旦假期夜班、春節(jié)假期白班、春節(jié)假期夜班、清明假期白班、清明假期夜班、五一假期白班、五一假期夜班、端午節(jié)假期白班、端午節(jié)假期夜班、國慶假期白班、國慶假期夜班、中秋節(jié)假期白班和中秋節(jié)假期夜班等十七類。-2-3 串行算法如何在上述諸多的約束條件下，找到最符

5、合值班規(guī)則的人選，就是值班計(jì)劃中的難點(diǎn)。本文首先提出了串行算法來解決此多約束條件的值班計(jì)劃的制定，其流程圖如圖1 所示：圖1 串行算法串行算法首先將要被值班的日期，首先要對(duì)其包含的班次進(jìn)行循環(huán)，即一天最多包含2個(gè)班次，舉例：法定節(jié)假日白班，法定節(jié)假日夜班，而當(dāng)工作日時(shí)，只有工作日夜班，對(duì)于同一個(gè)班次名稱下，按照值班人員的級(jí)別順序，從高級(jí)別到低級(jí)別進(jìn)行遍歷，其次對(duì)于某一級(jí)別的值班人員的選擇，首先要考慮是否存在預(yù)留值班該班次的情況，若被預(yù)留，則考慮下一個(gè)級(jí)別的人選；若未被預(yù)留，則根據(jù)值班規(guī)則進(jìn)行選人。其中預(yù)定義的規(guī)則為：根據(jù)值班日期，判斷所屬的班次類別，對(duì)班次類別下的所有班次進(jìn)行值班計(jì)數(shù)的統(tǒng)計(jì)，從

6、小到大對(duì)值班人員進(jìn)行排序，如果計(jì)數(shù)相同，則根據(jù)值班人員的姓氏拼音規(guī)則，從小到大進(jìn)行排序。然后對(duì)于已經(jīng)排好順序的值班人員隊(duì)列，依次判斷其約束條件，首先判斷值班人員的可輸入規(guī)則中的禁止值班班次規(guī)則，然后是性別的約束判斷。如有不符合的約束規(guī)則，則輸入隊(duì)列的下一個(gè)人，如果都符合，則進(jìn)入下一個(gè)級(jí)別的值班人員的選擇。最后當(dāng)排完一個(gè)值班人員后，將其放置該班次類別的隊(duì)列的隊(duì)尾。由圖1 可見，串行算法需要對(duì)每一個(gè)具體到某日某班次某級(jí)別的值班人員的各種條件進(jìn)行判斷與遍歷，可見時(shí)間復(fù)雜度很高，雖然循規(guī)蹈矩的串行算法，也能完成值班計(jì)劃的制定，但其邏輯判斷復(fù)雜且相互交織，容易出錯(cuò)，算法效率較低，對(duì)于小規(guī)模的作業(yè)調(diào)度，性

7、能差-3-強(qiáng)人意，不適用值班人員規(guī)模較大的計(jì)算，對(duì)于值班人數(shù)較多的計(jì)劃，難免出現(xiàn)長時(shí)間計(jì)算，甚至死機(jī)的不良現(xiàn)象。也不適合靈活的擴(kuò)展。在串行算法的基礎(chǔ)之上，本文針對(duì)多約束條件的值班規(guī)則，提出了分塊算法。4 分塊算法分塊算法是將值班日期與值班人員隊(duì)列相分離，日期與人員均分類的思想，分塊算法在某種程度也可以認(rèn)為是對(duì)串行算法的細(xì)化，對(duì)值班人員隊(duì)列的構(gòu)造，主要依據(jù)的是以班次類別進(jìn)行的分類，具體為工作夜，周六日，法定節(jié)假日，包含的班次名稱進(jìn)行輸出。分塊算法的整體結(jié)構(gòu)為：日期班次隊(duì)列，值班人員隊(duì)列(有序集)，規(guī)則隊(duì)列。其中，日期班次隊(duì)列是對(duì)一個(gè)月的日期按照班次類別進(jìn)行分類，并對(duì)每一類下包含的班次進(jìn)行遍歷，目

8、前只考慮白班和夜班，不考慮除此之外的其它情況。工作日只有工作夜班，周六日和法定節(jié)假日假期均有白班和夜班。尤其是減少了值班日期的屬性判斷，在分塊算法中，值班日期根據(jù)班次名稱所屬的班次類別的分類，如圖2 所示將每月的值班日期也分成了三個(gè)隊(duì)列，首先按照班次名稱的優(yōu)先級(jí)排列，隨后按照日期從前往后排列，而在每一隊(duì)列中，只需要對(duì)隊(duì)首的日期進(jìn)行屬性判斷，即可獲知隊(duì)列屬性，從而調(diào)用相應(yīng)的值班人員隊(duì)列。跟串行算法比較，大量地減少了比較次數(shù)，提高了運(yùn)行效率。圖2 值班日期、班次隊(duì)列值班人員隊(duì)列，分別有處級(jí)值班人員隊(duì)列和科級(jí)值班人員隊(duì)列，對(duì)于值班人員隊(duì)列的構(gòu)成，根據(jù)班次類別，統(tǒng)計(jì)每位值班人員的值班計(jì)數(shù)，首先依據(jù)計(jì)數(shù)

9、從小到大排列，弱計(jì)數(shù)相同時(shí)，則根據(jù)值班人員的姓氏拼音規(guī)則的順序默認(rèn)排序，將值班人員的主鍵存儲(chǔ)成有序的隊(duì)列。由于將值班人員進(jìn)行了有目的分類，所以能夠有效的處理較大規(guī)模的數(shù)據(jù)樣本，而且值班人員分別建成隊(duì)列，更易擴(kuò)展，加入其它級(jí)別的人員進(jìn)入值班計(jì)劃，如局級(jí)，廳級(jí)，值班司機(jī)等等。圖3 是將值班規(guī)則與值班人員隊(duì)列進(jìn)行了連接，確定了預(yù)留值班規(guī)則、禁止值班規(guī)則，性別規(guī)則進(jìn)行了先后執(zhí)行的順序，預(yù)留與禁止值班規(guī)則都需要遍歷數(shù)據(jù)庫的規(guī)則表，規(guī)則表的內(nèi)容是用戶通過頁面進(jìn)行初始化的，而對(duì)于性別規(guī)則，只可以看作是算法的一個(gè)參數(shù)，默-4-認(rèn)是性別一致，但也可以被修改。其中預(yù)留規(guī)則的優(yōu)先級(jí)最高，當(dāng)預(yù)留規(guī)則與性別規(guī)則發(fā)生沖突

10、，則此時(shí)不予考慮性別規(guī)則。對(duì)不同的日期調(diào)用不同的值班人員隊(duì)列，將結(jié)果存儲(chǔ)在數(shù)據(jù)庫中，然后對(duì)于值班計(jì)劃，最后再以值班日期從前往后的順序全部輸出。圖3 值班規(guī)則與人員隊(duì)列如果待選隊(duì)列中，第一個(gè)不符合條件，第二個(gè)才符合條件，只能選中第二個(gè)，再判斷同班次類別的下一個(gè)安排人員，必須繼續(xù)從隊(duì)列的第一個(gè)人開始篩選，而不是原隊(duì)列的第三人。即不符合規(guī)則的人繼續(xù)停留在隊(duì)列中，而符合規(guī)則的人則進(jìn)行輸出，同時(shí)將其后置到隊(duì)列的尾部，繼續(xù)直到完成值班計(jì)劃。5 結(jié)束語對(duì)于復(fù)雜的值班規(guī)則和較大的人員規(guī)模，本文提出的分塊算法有著良好的性能表現(xiàn)，在近百人的值班計(jì)劃，需要運(yùn)行的時(shí)間只有數(shù)十秒，分塊算法提前將值班日期進(jìn)行了分類處理，

11、并對(duì)值班人員構(gòu)建了相應(yīng)的人員隊(duì)列，高效快捷地完成值班計(jì)劃的制定。但諸多的值班規(guī)則存在一定的互斥，本文將做進(jìn)一步研究，也將嘗試值班計(jì)劃類似問題的并行算法處理的模式。-5-參考文獻(xiàn)1木霄挺，楊杰，王曉幸. 排班考勤管理系統(tǒng)在醫(yī)院的開發(fā)與應(yīng)用J. 醫(yī)療裝備. 2006 年 02 期2 劉曉榮，顧仁萍. 護(hù)士排班決策支持系統(tǒng)J. 解放軍護(hù)理雜志. 2006 年 01 期3 任小英，趙光紅. 改進(jìn)護(hù)士排班的研究與實(shí)踐A. 全國護(hù)理行管理學(xué)術(shù)交流暨專題講座會(huì)議論文匯編C2002 年4 趙建明，孫青. 節(jié)假日值班應(yīng)注意和把握的幾個(gè)環(huán)節(jié)J. 辦公室業(yè)務(wù). 2008 年 09 期5 趙建明，梁建軍，蔣平.著力改

12、進(jìn)值班工作J. 創(chuàng)造性地構(gòu)建值班服務(wù)新格局辦公室業(yè)務(wù).2005 年 04 期6袁宏武，薛模根. 基于規(guī)則的個(gè)性化課表生成算法J. 計(jì)算機(jī)工程2006 年 04 期7蘭懷玉，馬若飛. 一個(gè)自動(dòng)編排課表系統(tǒng)的設(shè)計(jì)與開發(fā)J. 中央民族大學(xué)學(xué)報(bào)(自然科學(xué)版)2002 年02 期8崔雪梅，樸勇軍，金哲學(xué). 自動(dòng)排課算法的設(shè)計(jì)J. 延邊大學(xué)學(xué)報(bào)(自然科學(xué)版) 2000 年 03 期9于海波. 飛機(jī)排班算法的研究與實(shí)現(xiàn)D.南京：南京航空航天大學(xué)，200710孫宏. 航空公司飛機(jī)排班問題：模型及算法研究D.成都：西南交通大學(xué)，200411李麗娟. 飛機(jī)排班模型及算法研究D.南京：南京航空航天大學(xué)，2009An

13、 Algorithm of Multi-Constraint Duty PlanLi Jiasen, Zhang XiaoyanSchool of Software Engineering of BUPT, Beijing (100876)AbstractDifferent rules on duty, different duty plans. With Multi-Constraint rules, first this article analyses theprocess of traditional serial algorithm then points out the complexity of logical structure and inefficienton large-scale data, second, the article proposes block algorithm with more efficient and accurate,which based on separation of duty dates and duty persons. The bloc