基于多條件約束的值班計劃的一種算法

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

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

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

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

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

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

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

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

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

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

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

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