隨機搜索算法在護理實習生排班問題中的研究與應用

張立，忻凌，王麗，馬忻（.安徽中醫藥大學第一附屬醫院，安徽　3003；.安徽財貿職業學院，安徽　3007）

隨機搜索算法在護理實習生排班問題中的研究與應用

張立1，忻凌1，王麗2，馬忻1
（1.安徽中醫藥大學第一附屬醫院，安徽230031；2.安徽財貿職業學院，安徽230071）

0　引言

護理實習生排班問題是一種典型的組合優化問題，其目的是對護理實習生的實習期進行合理的安排［1］。該問題的解決一方面需要滿足實習生的要求，安排他們進入需要學習的科室，實現實習目標；另一方面需要滿足實習科室的要求，使各科室的實習生數量在周期內相對均衡。高質量的排班方案不僅能夠滿足護理實習生的實習需求，還能夠保證醫院各科室正常運作。

護理實習生排班問題是一種關于人員日程自動編排的問題［2］。單個實習生的排班問題相對比較簡單，但面對實習生數量相對龐大，而實習科室的承受能力極其有限的實際情況，實習生排班問題的求解就變得非常困難。對于護理實習排班問題的研究目前在國內并不廣泛，主要集中在排班方法對于教學效果的影響［3-4］上。

傳統的人員日程編排問題是將人員的時間順序看作一條路徑，利用不用長度的日程進行填充，使路徑中的空閑時長最短。目前，國內研究者對人員日程編排問題進行了廣泛的研究：文獻［5-7］提出了帶約束的護士排班模型，并使用一系列變換規則來求解護士排班問題；王超等［8］對變領域搜索算法進行改進，來解決排班問題。此外，一些研究者從管理角度對人員排班工作進行優化，陸蕊君等［9-10］通過調整班次，重新制定和完善崗位職責，改進排班模式，實行彈性工作制，在一定程度上解決了人力資源與病人期望不平衡的矛盾及護士編制不足、護士班次變換頻繁的問題。

護理實習生的排班工作目前仍主要由人工方式完成，工作量很大，而且容易出錯，各科室不同時間人員分布也極不均衡。搜索算法利用計算機的高性能窮舉一個問題部分的或所有的可能情況，從而求解出問題的解。隨機搜索算法實際上是根據初始條件和擴展規則構建一個解答樹，解答樹上的各解結點隨機獲得，最終獲得一個日程編排問題的解。隨機搜索算法能夠有效提高工作效率，避免人工方式產生的錯誤，并通過隨機過程在大數據的環境下平衡科室人數。

本文提出一個求解護理實習排班的隨機搜索算法，利用隨機算法在海量數據分配中的優勢，解決排班方案不均衡的問題。

1　護理實習生排班模型

1.1模型約束條件

護理實習排班問題是指為不同院校的學生在給定的實習時間段內安排實習科室，并使該排班方案滿足各種硬性約束條件，同時盡量滿足各種軟性約束條件。硬性約束條件是指在整個排班方案中必須要滿足的條件，任何違反硬性約束條件的排班方案都是不可行的；軟性約束條件是在排班方案中希望能夠得到最大滿足的約束。主要的約束條件如下：

（1）硬性約束條件：

①學生的每個周次有必須有安排；

②必去科室必須在實習期內出現；

③回避科室在實習期內不能出現；

④學生進入非單周實習科室實習，必須在指定時間；

⑤同類型科室只能去一個；

⑥各科室的人員安排不得超過其最大承受人數；

（2）軟性約束條件：

①實習科室的安排每周人數盡量平穩；

②優先科室盡量靠前安排；

③某大類科室（如內科科室或外科科室）可規定數量選取（最少去1個，最多去N個）；

④科室安排盡量齊整，避免出現斷檔。

上述約束條件是測試數據集中可能出現的約束。對于某一特定院校的數據集來說，并不一定全部出現。因此，這些約束條件能夠較好地反映實際應用的不同要求。

1.2護理實習生排版模型

在本文中，我們將單個實習生的排班模型描述為：從某一個時間點開始 （實習生實習期的開始時間），按照一定規則隨機選取科室對時間序列進行填充。其中，各實習科室有一下特點：①科室分為1周科室、2周科室和3周科室，實習生在其中的實習時間分別為1周、2周和3周，為了便于管理，2周科室和3周科室分別必須在指定的統一時間安排進入；②同類科室需要回避，同一實習生不能重復去2個同類型科室，例如手術室與介入手術室屬于同類科室，腦病1科與腦病2科屬于同類科室；③各科室還可分為大類科室，如心內科、內分泌科、消化內科等屬于內科科室，普外科、骨科、腦外科等屬于外科科室。

下面我們給出一些重要的決策變量和參數：

我們考慮科室的集合D、實習生的集合S和科室負擔的集合B。其中科室Di定義為Di（IDi，ki，class1i，class2i，Ni），其中IDi代表科室唯一ID，表示科室屬于幾周科室，class1i表示科室小類，用于區分同類型科室，class2i表示科室大類，用于區分大類科室，Ni表示科室Di最多可以同時容納的人數；實習生Si定義為Si（starti，endi，ti），其中starti和endi分別表示實習生實習的起止時間，ti表示實習生當前的時間戳；科室負擔Bij定義為Bij（IDi，tj，mij），其中IDi代表科室唯一ID，tj表示科室當前的時間戳，mij表示科室i在時間tj的實際人數，mij必須滿足約束條件mij≤Ni，即科室的實際安排人數不得超過最大人數上限。

2　隨機搜索算法與流程

隨機搜索算法是指每次從科室的集合中隨機搜索一個合適的科室填入實習生的時間序列中，直到所有時間填滿為止。下面詳細描述我們給出的隨機算法：

（1）從實習生集合中獲取一個學生Si（starti，endi，ti），初始ti=starti。針對實習生的實習要求，將科室集合D劃分成必去科室子集D1、回避科室子集D2和其他科室子集D3；

（2）從科室集合中按要求隨機搜索一個科室，并驗證其是否合適。如果合適，則填入實習序列，具體約束如下：

①如果ti%6=0時，首先從必去科室子集D1中以ki∈｛2，3｝為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其它科室子集D3中以為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從必去科室子集D1中以ki=1為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其它科室子集D3中以ki=1為條件進行隨機抽取；如果仍然無法滿足，則當前時間戳ti=ti+1，空閑時間Ti=Ti+1；

②如果ti%3=0時，首先從必去科室子集D1中以ki=3為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其它科室子集D3中以ki=3為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從必去科室子集D1中以ki=1為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其它科室子集D3中以ki=1為條件進行隨機抽取；如果仍然無法滿足，則當前時間戳ti=ti+1，空閑時間Ti=Ti+1；

③如果ti%2=0時，首先從必去科室子集D1中以ki=2為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其他科室子集D3中以ki=2為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從必去科室子集D1中以ki=1為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其它科室子集D3中以ki=1為條件進行隨機抽取；如果仍然無法滿足，則當前時間戳ti=ti+1，空閑時間Ti=Ti+1；

如果ti%3！=0且ti%2！=0時，首先從必去科室子集D1中以ki=1為條件進行隨機抽取；如果所有科室都無法滿足硬性約束的要求，則從其它科室子集D3中以ki=1為條件進行隨機抽取；如果仍然無法滿足，則當前時間戳ti=ti+1，空閑時間Ti=Ti+1；

⑤插入3周科室時，必須遵循條件endi-ti+1＞=3；插入2周科室時，必須遵循條件endi-ti+1＞=2；插入1周科室時，必須遵循條件endi-ti+1＞=1。

（3）安排科室成功后，則重復步驟（2），繼續安排科室，如果ti＞endi，則排班成功，退出循環。

3　實驗結果與分析

針對護理實習生排班問題，本文提出了一個隨機搜索算法。該算法不僅能夠實現護理實習生排班的自動化，而且能夠解決科室人數分布不均衡的問題。下一步將對該算法進行實現，并使用數據對進行檢驗。

圖1　排班時間對比圖

圖2　排班正確率對比圖

（1）排班效率

本文在人工模式排班累計統計了300名護理實習生所消耗的時間，并對比了本文實現同樣人數的排班所消耗的時間，對比結果如圖1所示。

由圖1，發現傳統的排班方式在處理這么大人數的排班消耗的時間遠遠大于本文實現方法，本文的實現方法只需要數分鐘就能一次完成數百名護理實習生的排班。因此，本文的實現方法大大地提高了護理實習生排班的效率。

（2）排班正確率

本文搜集了利用傳統的方式排班300名護理實習生的失誤人數，并對比了本文的實現方法，如圖2所示。

由圖2可知，本文的實現方法的正確率遠遠高于傳統的排班方式。同樣，證明了本文的實現方法的穩定性。

（3）排班均衡問題

關于排班均衡的問題，并沒有一個嚴格的標準來衡量，但從本文方法實施之后的反饋來說，科室的護理實習生基本上達到均衡，護理實習生實習的科室也比以前豐富，而且實習的效果也比以前好。這側面反映了本文實現方法基本上解決了排班不均衡的問題。

4　結語

本文根據護理實習的約束條件提出了護理實習生的排班模型，并將隨機搜索算法應用到護理實習生的排班中，實驗結果表明本文的護理實習生的排班相比較于傳統的排班模式，在排班效率、排班的準確率上都有很明顯的提升，并解決了排班的均衡問題。但本文的方案是針對于護理實習生的排班，對于其他護士的排班是否有同樣的效果并沒有驗證，因此，本文的下一步研究方向是提出針對所有護理人員的排班實現與改進。

［1］謝屹紅.護士排班方式與護理人力資源的合理利用［J］.中國實用護理雜志，2004，20（4）：65-65.

［2］BRUCKER P，QU R，BURKE E.Personnel scheduling：models and complexity［J］.European Journal of Operational Research，2011.467-473.

［3］黎建敏，林婉萍.APN排班工作職責作為實習目標的臨床護理教學效果初探［J］.國際醫藥衛生導報，2011，17（1）：120-122.

［4］史愛玲等.一對一帶教與排班制帶教在護理實習生中的教學效果比較［J］.齊魯護理雜志，2014，（8）：12-13.

［5］沈吟東，陳名暉，鄧婕.利用矩陣向量化變換求解護士排班問題［C］.中國控制與決策會議論文集，2008：1019-1022.

［6］柯彩霞，謝文，劉曉華，等.護士排班模式改革與效果［J］.中國護理管理，2008，8（11）：38-40.

［7］馮艮嬌，盧海濤.護理排班模式改革探討［J］.南方護理學報，2002，9（4）：67-68.

［8］王超，董興業.求解護士排班問題的變領域搜索算法［J］.計算機應用，2013，33（2）：338-341，352.

［9］陸蕊君，鮑學英，王惠芬.護士排班方法的改進與實踐［J］.當代護士：綜合版，2007（2）：23-23.

［10］唐富琴，張琳.人性化管理在護士排班中的運用［J］.護理學報，2009，16（16）：18-19.

張立，男，安徽合肥人，初級工程師，研究方向為計算機技術

忻凌，男，安徽合肥人，工程師，研究方向為人工智能

馬忻，女，安徽合肥人，副教授，研究方向為護理學及其管理

王麗，女，安徽合肥人，講師，研究方向為信息管理

Nursing Practice；Random Algorithm；Scheduling

Research and Application of Stochastic Search Algorithm in the Scheduling Problem of Nursing Interns

ZHANG Li1，XIN Ling1，WANG Li2，MA Xin1
（1.The First Afflicted Hospital of Anhui University of TCM，Anhui 230031；2.Anhui Finance&Trade Vocational College，Anhui 230071）

1007-1423（2015）23-0035-04

10.3969/j.issn.1007-1423.2015.23.008

2015-05-12

2015-08-05

臨床護理教學是各教學醫院的一項重要工作。目前，各醫院多采用人工方式完成護理實習生排班工作，但由于實習生數量較大、進崗時間不一、實習大綱要求復雜等原因，使實習生排班工作出現工作量大、易出錯、科室分配不均衡等問題。提出將隨機搜索算法應用在護理實習生排班中，并從排班效率、排班正確率以及排班均衡問題上對比傳統的排班方式。實驗結果表明：將隨機搜索算法應用于護理實習生排班中，發現排班效率、排班準確率高，而且可避免排班不均衡的問題。

護理實習；隨機算法；排班

安徽中醫藥大學臨床科研基金（No.2012LC1-026B）

The clinical nursing teaching is an important task in the teaching hospitals.At present，most hospitals manually finish scheduling work of nursing interns，but with large quantities of interns，different time of punching in the post，complex requirements of guideline for internship and other reasons，there are many problems existed in the scheduling work，such as heavy workload，error-prone problems，and the uneven distribution of the department.Presents the random search algorithm applied in nursing interns scheduling，and makes comparison with traditional scheduling methods in view of the efficiency，accuracy and equilibrium of scheduling.The experimental results show that，when the random search algorithms is applied to the nursing trainee scheduling，efficiency and accuracy rate are higher，and the problem of unbalanced scheduling are avoided as well.