[發(fā)明專(zhuān)利]基于隨機(jī)鄰域搜索算法的實(shí)習(xí)生輪換排班方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202110987313.0
• 申請(qǐng)日: 2021-08-26
• 公開(kāi)（公告）號(hào): CN113743761A
• 公開(kāi)（公告）日: 2021-12-03
• 發(fā)明（設(shè)計(jì)）人: 鄭自然
• 申請(qǐng)（專(zhuān)利權(quán)）人: 山東師范大學(xué)
• 主分類(lèi)號(hào): G06Q10/06
• 分類(lèi)號(hào): G06Q10/06;G06Q10/04;G06N20/10
• 代理公司: 濟(jì)南圣達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 37221
• 代理人: 閆圣娟

本公開(kāi)提供了一種基于隨機(jī)鄰域搜索算法的實(shí)習(xí)生輪換排班方法及系統(tǒng)，包括基于二次整數(shù)規(guī)劃模型構(gòu)建目標(biāo)函數(shù)，并確定實(shí)習(xí)生輪換排班需要滿(mǎn)足的約束條件；隨機(jī)生成滿(mǎn)足實(shí)習(xí)生輪換排班的所有硬性約束的初始解，并將所述初始解作為當(dāng)前最優(yōu)解；基于所述當(dāng)前最優(yōu)解，利用隨機(jī)鄰域搜索算法進(jìn)行迭代求解，直至滿(mǎn)足預(yù)設(shè)迭代條件；其中，所述隨機(jī)鄰域搜索算法具體為：使用搜索算子對(duì)當(dāng)前最優(yōu)解進(jìn)行變換得到臨時(shí)解，若臨時(shí)解的目標(biāo)函數(shù)值小于當(dāng)前最優(yōu)解，則利用臨時(shí)解替換當(dāng)前最優(yōu)解。所述方案針對(duì)同時(shí)帶有連續(xù)性約束和休息需求的排班問(wèn)題，提出一種隨機(jī)鄰域搜索算法，基于該模型對(duì)上述問(wèn)題提供了一種可行的解決方案，提高了實(shí)習(xí)生輪換排班的效率及準(zhǔn)確性。

技術(shù)領(lǐng)域

本公開(kāi)屬于排班優(yōu)化技術(shù)領(lǐng)域，尤其涉及一種基于隨機(jī)鄰域搜索算法的實(shí)習(xí)生輪換排班方法及系統(tǒng)。

背景技術(shù)

本部分的陳述僅僅是提供了與本公開(kāi)相關(guān)的背景技術(shù)信息，不必然構(gòu)成在先技術(shù)。

人員排班問(wèn)題是一類(lèi)較為復(fù)雜的人事組織規(guī)劃問(wèn)題。為了完成基本的工作任務(wù)、提高組織的整體效率、降低人員成本、更好平衡作息、提高實(shí)習(xí)生的滿(mǎn)意度以及提高各方面的表現(xiàn)，單位或公司需要在滿(mǎn)足一系列復(fù)雜約束的情況下將實(shí)習(xí)生分配到某種工作任務(wù)中。在當(dāng)今社會(huì)人員排班問(wèn)題的規(guī)模越來(lái)越大，使用傳統(tǒng)的手工排班或者基于經(jīng)驗(yàn)的排班已經(jīng)無(wú)法生成高質(zhì)量甚至是可行的排班，因此使用計(jì)算機(jī)程序和算法來(lái)進(jìn)行輔助排班是較為普遍的做法。對(duì)于人員排班問(wèn)題，人們通常將其建模為優(yōu)化問(wèn)題并使用相關(guān)的優(yōu)化進(jìn)行求解，從而幫助管理人員自動(dòng)生成高質(zhì)量的排班。人員排班問(wèn)題在最近的十幾年中一直一來(lái)都是運(yùn)籌學(xué)中的熱點(diǎn)研究領(lǐng)域。

在繁多的人員排班問(wèn)題中輪換排班問(wèn)題是一大類(lèi)較為常見(jiàn)和重要的問(wèn)題。該問(wèn)題刻畫(huà)了在一定的時(shí)間范圍內(nèi)，實(shí)習(xí)生需要完成一定數(shù)量的任務(wù)(即輪班)，同時(shí)需要滿(mǎn)足一定的約束條件。例如某個(gè)單位對(duì)新實(shí)習(xí)生進(jìn)行的集中時(shí)間或地點(diǎn)的崗前培訓(xùn)活動(dòng)。該培訓(xùn)的總時(shí)間內(nèi)，每個(gè)實(shí)習(xí)生都要完成某個(gè)所有的培訓(xùn)活動(dòng)，這里將某個(gè)活動(dòng)稱(chēng)之為一個(gè)輪班。其他例子包括即將畢業(yè)的實(shí)習(xí)醫(yī)生或者護(hù)士的醫(yī)院轉(zhuǎn)科活動(dòng)。在半年或者一年的時(shí)間內(nèi)，需要對(duì)醫(yī)院的所有科室進(jìn)行幾個(gè)周時(shí)間的實(shí)習(xí)。其他例如對(duì)博覽會(huì)項(xiàng)目的參加的規(guī)劃等等都可以歸納為該類(lèi)問(wèn)題。

本公開(kāi)所關(guān)注的問(wèn)題是一種較為具體的輪班排班問(wèn)題。該問(wèn)題需要考慮的約束為：1.輪班連續(xù)性；2.不同輪班人數(shù)的穩(wěn)定性；3實(shí)習(xí)生的休息需求。其中連續(xù)性指的是對(duì)于某個(gè)輪班，一個(gè)實(shí)習(xí)生一旦開(kāi)始就需要該實(shí)習(xí)生在接下來(lái)的時(shí)間持續(xù)該輪班，直到要求的時(shí)間長(zhǎng)度完成。例如某個(gè)輪班需要3天的時(shí)間，一個(gè)實(shí)習(xí)生如果選擇在周一開(kāi)始，那么周二和周三則必須也要執(zhí)行該輪班。輪班人數(shù)的穩(wěn)定性是指對(duì)于整個(gè)培訓(xùn)活動(dòng)某個(gè)輪班在所有時(shí)間的參加人數(shù)變動(dòng)不能太大，否則會(huì)引起相應(yīng)成本或資源的波動(dòng)從而對(duì)整體排班帶來(lái)復(fù)雜性。例如某個(gè)輪班在周一的參加人數(shù)為20人而在周二為50人，則培訓(xùn)師、場(chǎng)地或者其他資源則會(huì)出現(xiàn)較大的變化，從而增加管理或組織的難度。實(shí)習(xí)生的休息需求是指在某個(gè)時(shí)間內(nèi)，實(shí)習(xí)生可以提出不參加任何輪班活動(dòng)，即排班者盡量不要在某個(gè)已經(jīng)提出休息申請(qǐng)的時(shí)間內(nèi)給該實(shí)習(xí)生安排輪班。但由于第一個(gè)約束是必須滿(mǎn)足的，因此該需求有可能無(wú)法滿(mǎn)足，因此一般在模型中將該約束建模為軟性需求。發(fā)明人發(fā)現(xiàn)，該類(lèi)問(wèn)題雖然可以建模為二次整數(shù)規(guī)劃模型，但是由于問(wèn)題規(guī)模通常較大，且二次整數(shù)規(guī)劃的求解較為困難，即便是使用商業(yè)求解器也無(wú)法在可接受的時(shí)間內(nèi)求得高質(zhì)量的解甚至可行解。

發(fā)明內(nèi)容

本公開(kāi)為了解決上述問(wèn)題，提供了一種基于隨機(jī)鄰域搜索算法的實(shí)習(xí)生輪換排班方法及系統(tǒng)，所述方案針對(duì)同時(shí)帶有連續(xù)性約束和休息需求的排班問(wèn)題，提出一種隨機(jī)鄰域搜索算法，基于該模型對(duì)上述問(wèn)題提供了一種可行的解決方案，提高了實(shí)習(xí)生輪換排班的效率及準(zhǔn)確性。

根據(jù)本公開(kāi)實(shí)施例的第一個(gè)方面，提供了一種基于隨機(jī)鄰域搜索算法的實(shí)習(xí)生輪換排班方法，包括：

基于二次整數(shù)規(guī)劃模型構(gòu)建目標(biāo)函數(shù)，并確定實(shí)習(xí)生輪換排班需要滿(mǎn)足的約束條件；

隨機(jī)生成滿(mǎn)足實(shí)習(xí)生輪換排班的所有硬性約束的初始解，并將所述初始解作為當(dāng)前最優(yōu)解；