護(hù)士排班優(yōu)化問題

2015高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書我們仔細(xì)閱讀了全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽章程和全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽參賽規(guī)則（以下簡(jiǎn)稱為“競(jìng)賽章程和參賽規(guī)則”，可從全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽網(wǎng)站下載）。我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽章程和參賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽章程和參賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）： 我們的報(bào)名參賽隊(duì)號(hào)為（12位數(shù)字組成的編號(hào)）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： （論文紙質(zhì)版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內(nèi)容請(qǐng)仔細(xì)核對(duì)，提交后將不再允許做任何修改。如填寫錯(cuò)誤，論文可能被取消評(píng)獎(jiǎng)資格。） 日期： 年 月 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2015高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：護(hù)士工作時(shí)間的安排摘要當(dāng)前社會(huì)“看病難”成了大中城市的一塊難以根治的頑疾。在城市的醫(yī)院里常常出現(xiàn)患者爆滿、醫(yī)護(hù)人員人手不足的狀況，現(xiàn)有的排班管理辦法難以適應(yīng)當(dāng)前醫(yī)院需求。在這種情況下醫(yī)護(hù)人員工作效率較低，導(dǎo)致醫(yī)院人力資源的浪費(fèi)。為了緩解這一狀況，本文以某醫(yī)院的心腦血管科護(hù)士的工作時(shí)間安排表制定為例，在保證各時(shí)段護(hù)士人員需求下，分成求解最優(yōu)安排方式的兩類問題，即不考慮加班情況下人員規(guī)模最小和人員規(guī)模固定情況下加班人數(shù)最少。針對(duì)問題一，為達(dá)到既滿足工作需要又要盡可能少的人員編制，本文采取0-1整數(shù)規(guī)劃，將護(hù)士1天的8小時(shí)工作分成5個(gè)模式。通過LINGO軟件對(duì)5個(gè)模式進(jìn)行組合分析得到最小人員需求為87人，并將每時(shí)段安排人數(shù)做成EXCEL表格?？紤]到工作時(shí)長(zhǎng)（工作時(shí)段+休息時(shí)段）給護(hù)士生活帶來的影響，刪減掉工作時(shí)長(zhǎng)最長(zhǎng)的模式。隨后對(duì)保留的四種模式進(jìn)行隨機(jī)組合，在所有組合中挑選出所有人數(shù)最少的模式，然后進(jìn)行比較分析，綜合考慮夜班人數(shù)等因素，遴選出最優(yōu)模式組合。具體模式選擇及工作時(shí)間調(diào)度詳見模型求解及附錄。針對(duì)問題二，護(hù)士人員限制為80人，需要部分護(hù)士加班2小時(shí)。本文研究的是如何使得加班護(hù)士人數(shù)最少，并給出最優(yōu)工作安排方案。在問題一的基礎(chǔ)上，增加兩種加班模式，利用LINGO軟件求解得到最少加班人數(shù)為26人。隨后利用EXCEL軟件進(jìn)行分析，在保證加班人數(shù)最少的前提下，綜合夜班人數(shù)等因素選出最優(yōu)安排方式。具體模式選擇及工作時(shí)間調(diào)度詳見模型求解及附錄。關(guān)鍵字：線性規(guī)劃 0-1整數(shù)規(guī)劃 LINGO EXCEL 工作模式一、問題重述某醫(yī)院的心腦血管科需要制定護(hù)士的工作時(shí)間表。在心腦血管科的一個(gè)工作日分為12個(gè)兩小時(shí)的時(shí)段，每個(gè)時(shí)段的人員要求不同。例如，在夜間只要求有很少幾名護(hù)士就足夠了，但在早晨為了給病人提供特殊報(bào)務(wù)，需要很多護(hù)士。表B1列出了每個(gè)時(shí)段的人員需求量。表B1每個(gè)時(shí)段的人員需求問題1： （1）為滿足需求最少需要多少名護(hù)士？這里假定每位護(hù)士每天工作8小時(shí)，且在工作4小時(shí)后需要休息1小時(shí)。 （2）如果滿足需求的排班方案不止一種，請(qǐng)給出你認(rèn)為最合理的排班方案，并說明其理由。問題2：目前心腦血管科只有80名護(hù)士，如果這個(gè)數(shù)目不能滿足指定的需求，只能考慮讓部分護(hù)士加班。如果加班，每天加班的時(shí)間為2小時(shí)，且緊隨在后一個(gè)4小時(shí)工作時(shí)段之后，中間沒有休息。 （1）請(qǐng)給出護(hù)士工作時(shí)間安排的方案，以使需要加班的護(hù)士數(shù)目最少。 （2）如果排班（包括加班）的方案不止一種，請(qǐng)給出你認(rèn)為最合理的排班和加班方案，并說明其理由。二、模型假設(shè)1、不考慮國(guó)家法定假期及護(hù)士年假對(duì)排班的影響2、不考慮護(hù)士因病假、事假換班帶來的影響3、不考慮護(hù)士因個(gè)人問題對(duì)排班的影響4、所有給出的約束條件都真實(shí)、準(zhǔn)確，且醫(yī)院排班嚴(yán)格按照此執(zhí)行三、符號(hào)說明1、i，j:表示第i，j個(gè)工作時(shí)段2、a(i):第i個(gè)時(shí)間段所需護(hù)士人數(shù)3、b(i):第i個(gè)時(shí)間段安排護(hù)士人數(shù)4、z：表示所需最少護(hù)士總數(shù)5、z：表示所需最少加班護(hù)士總數(shù), y：表示加班模式下，正常工作護(hù)士人數(shù)6、start1，start2startn：表示護(hù)士的n種工作模式6、j=i+p-k*limit,取適當(dāng)值kN,使p0,limit,表示為滿足時(shí)段循環(huán)而定義的算法7、T：總工時(shí)（h）8、A:0-6時(shí)段安排加班護(hù)士人數(shù)， B:6-12時(shí)安排加班護(hù)士人數(shù)C:6-12時(shí)段安排工作人數(shù)， D:0-6時(shí)段安排工作人數(shù)9、權(quán)重計(jì)算總分M注：i，j=1、2、312四、問題一的模型建立與求解4.1問題分析此問中首要考慮的是滿足工作需要條件下所需要人員數(shù)量最少，該問題是一個(gè)典型的線性規(guī)劃問題。根據(jù)題目要求，護(hù)士每工作4小時(shí)需要休息1小時(shí)，由于護(hù)士是按工作時(shí)段上崗，休息完1小時(shí)后不能在中間時(shí)刻上崗，因此我們默認(rèn)護(hù)士每工作4小時(shí)休息2小時(shí)?？紤]到護(hù)士工作和休息是兩種狀態(tài)，本文采用0-1整數(shù)規(guī)劃，用1表示工作時(shí)段，用0表示休息時(shí)段，利用集循環(huán)函數(shù)建立相應(yīng)模型完成求解。針對(duì)問題需要，本文引用的集函數(shù)主要為:集操作函數(shù) wrap(index,limit)，集循環(huán)函數(shù) for（setname:expression_list）sum（setname:expression_list）相應(yīng)的等同于：start1模式: 1,1,0,1,1 start2模式: 1,0,1,0,1,1start3模式:1,1,0,1,0,1start4模式:1,0,1,1,0,1start5模式: 1,0,1,0,1,0,1本文假定每個(gè)護(hù)士選擇1種工作方式，由5種模式隨機(jī)組合。每時(shí)段工作的護(hù)士由前幾個(gè)時(shí)段開始工作的護(hù)士和本時(shí)段新增的護(hù)士組成，因此需要解決首尾時(shí)段連續(xù)的影響，為滿足時(shí)段循環(huán)我們定義如下算法:j=i+p-k*limit,取適當(dāng)值kN,使p0,limit利用LINGO軟件進(jìn)行求解得到最小人數(shù)Z=87?？紤]到實(shí)際情況下，五種值班模式排班過于繁瑣，且start5工作時(shí)間過長(zhǎng)，在此不作考慮。對(duì)剩下的4種模式隨機(jī)組合進(jìn)行分析，利用LINGO軟件進(jìn)行求解得到數(shù)據(jù)。再將分析結(jié)果通過EXCEL進(jìn)行整理，從人員需求數(shù)目、夜班人數(shù)等因素進(jìn)行比較排序，得到最優(yōu)結(jié)果。4.2模型的求解4.2.1所提供數(shù)據(jù)分析表1：每個(gè)工作區(qū)間對(duì)應(yīng)的時(shí)間段時(shí)段編號(hào)（i）123456789101112時(shí)段00-0202-0404-0606-0808-1010-1212-1414-1616-1818-2020-2222-24表2：、各時(shí)間段需求護(hù)士人數(shù)時(shí)段編號(hào)（i）123456789101112a（i）1515153540404030313530204.2.2編程求解LINGO（部分）求解結(jié)果如下（代碼見附錄）：本文首先對(duì)五種模式共存的情況用LINGO進(jìn)行求解得到最少需要人數(shù)87人（求解代碼和生成見附錄），并將護(hù)士排班情況繪成EXCEL表格。在表格中，模式5持續(xù)時(shí)間過長(zhǎng)，且工作休息間歇安排極不合理，在后面的分析中不作考慮。隨后，對(duì)另4種模式相互組合的情況分別用LINGO進(jìn)行逐一求解，并將部分模式分析的程序代碼呈現(xiàn)（見附錄）。求解完數(shù)據(jù)后，通過EXCEL軟件對(duì)所有數(shù)據(jù)按所需最少人數(shù)、0-6時(shí)段開始上班人數(shù)、6-12時(shí)段開始上班人數(shù)進(jìn)行排序分析，并用不同的顏色填充符合要求的解。（最優(yōu)的前30%）具體權(quán)衡條件如下：1、以所需人數(shù)最少為優(yōu)先考慮條件2、考慮0-6時(shí)開始上班人數(shù)盡可能少3、要保證護(hù)士人員在6-12時(shí)上班的人數(shù)盡可能多結(jié)論：在每個(gè)護(hù)士每天工作8小時(shí)，且在連續(xù)工作4小時(shí)后至少需休息1小時(shí)的條件下，該醫(yī)院為滿足工作需求至少需要87名護(hù)士，為減少0-6時(shí)段開始上班人數(shù)，將上班時(shí)間集中在6-12時(shí)段，通過對(duì)照分析，模式3（）和模式4（）的組合為最優(yōu)選擇。對(duì)應(yīng)調(diào)度安排見表3：護(hù)士值班安排表-34（問題一）表4：護(hù)士值班安排表1（問題一）注：1.模式組合中的數(shù)字代表不同模式，多個(gè)數(shù)字代表多種模式組合，例如：“123”代表模式1、模式2、模式3的組合2.0-6人數(shù)，6-12人數(shù)分別代表從0:00到6:00以及從6:00到12:00開始上班的人數(shù)五、問題二的模型建立與求解5.1問題的分析此問題整體解題思路與問題一相似，在護(hù)士人員只有80人的前提下要保證工作的完成，且盡可能少的安排加班人數(shù)，這也是一個(gè)典型的0-1整數(shù)規(guī)劃問題。此處新增加約束條件：護(hù)士總?cè)藬?shù)限定位80人，加班人數(shù)最少，加班時(shí)間為2小時(shí)，加班時(shí)段緊隨在正常工作時(shí)長(zhǎng)結(jié)束后，不休息。在此繼續(xù)采用保留的4種正常工作模式，編號(hào)同上。因?yàn)闂l件的限制，且必須滿足護(hù)士工作4小時(shí)后需要休息2小時(shí)，所以只有兩種加班模式符合，用start6和start7表示：start6:1,0,1,1,0,1,1start7:1,1,0,1,0,1,1在用LINGO軟件分析求解之前，先進(jìn)行簡(jiǎn)單數(shù)據(jù)分析。將總工時(shí)與護(hù)士人數(shù)列二元一次方程組，設(shè)需要加班護(hù)士人數(shù)為，正常工作護(hù)士人數(shù)為y。解得=26 y =54由此可見加班人數(shù)最少為26人，在后面的LINGO求解過程中可以此為參考。5.2模型求解LINGO（部分）求解結(jié)果如下（代碼見附錄）：本問首先對(duì)4種正常工作模式與2種加班模式用LINGO程序進(jìn)行求解，得到最少加班人數(shù)為26人，并將護(hù)士排班情況繪成EXCEL表格。（求解代碼和生成見附錄）。在EXCEL表格中對(duì)所有數(shù)據(jù)按所需加班人數(shù)、0-6時(shí)段安排加班人數(shù)（A）、6-12時(shí)段安排加班人數(shù)（B），0-6時(shí)段安排開始上班人數(shù)（C）、6-12時(shí)段安排開始上班人數(shù)（D）進(jìn)行排，并用不同的顏色填充單元格以示區(qū)分（最優(yōu)30%）。具體數(shù)據(jù)及分析結(jié)果見表5。具體權(quán)衡條件如下：1、以加班所需人數(shù)最少為優(yōu)先考慮條件，在人數(shù)相同時(shí)再考慮下述條件2、對(duì)A、B、C、D人數(shù)通過加權(quán)綜合分析，具體權(quán)重計(jì)算如下：A 0，9 B 0，25 C6，27 D34，52（1）由表格數(shù)據(jù)可知A區(qū)間長(zhǎng)度為9，B區(qū)間長(zhǎng)度為25，C區(qū)間長(zhǎng)度為21，D區(qū)間長(zhǎng)度為18（2）0-6時(shí)段，人數(shù)越少越好，系數(shù)取負(fù)；6-12時(shí)段，人數(shù)越多越好，系數(shù)取正；ABCD區(qū)間長(zhǎng)度不同，做系數(shù)調(diào)整，*9=*25=*21=*18（3）對(duì)ABCD不同因素，我們做如下權(quán)重分配：A占36%，B占24%，C占24%，D占16%。加權(quán)值M=0.36*A+0.24*B+0.24*C+0.16*D3.通過分?jǐn)?shù)計(jì)算結(jié)果得到最優(yōu)答案，得分最高的即為最優(yōu)解結(jié)論：在護(hù)士總數(shù)為80人前提下，考慮到護(hù)士每天加班的時(shí)間為2小時(shí)，且緊隨在后一個(gè)4小時(shí)工作時(shí)段之后，中間沒有休息，為保證完成工作需要至少有26名護(hù)士加班?？紤]到加班人員工作時(shí)間較長(zhǎng)，盡可能集中安排在上午（6-12）開始上班；盡量減少加班護(hù)士在凌晨（0-6）上班的情況，同時(shí)也兼顧正常上班護(hù)士的需求，綜合考量，模式1、模式2、模式3、模式6和模式7的組合為最優(yōu)選擇，即正常工作模式：11011、，加班工作模式：、 組合。對(duì)應(yīng)調(diào)度安排見表5：護(hù)士值班安排表-12367（問題二）。表6：護(hù)士值班安排表2（問題二）六、模型的評(píng)價(jià)與改進(jìn)6.1模型優(yōu)點(diǎn)文中采用EXCEL表格處理數(shù)據(jù)，使得工作安排醒目、分析邏輯清楚；在解決兩個(gè)問題的時(shí)候，均采用了基于工作模式的0-1整數(shù)規(guī)劃方式，使得問題分析更簡(jiǎn)單；在權(quán)衡模式選擇的時(shí)候，文中對(duì)各種因素進(jìn)行加權(quán)劃分，結(jié)果更科學(xué)化、人性化。6.2模型缺點(diǎn)由于該模型完全假設(shè)在護(hù)士保證全勤工作能力相同的理想條件下，一些客觀因素考慮不周；在假設(shè)工作模式的時(shí)候，文中假設(shè)每個(gè)護(hù)士只有一種工作模式這在事實(shí)很難做到，而且在這種情況下可能不是最優(yōu)答案。在加權(quán)過程中，所用的加權(quán)方式有一定局限性，對(duì)客觀因素菇?jīng)霾坏轿?.3模型改進(jìn)（1）在模型建立過程中，為將多目標(biāo)規(guī)劃轉(zhuǎn)化為0-1整數(shù)規(guī)劃，在工作模式的選取存在偶然性?，F(xiàn)實(shí)中，考慮到醫(yī)院自己、護(hù)士本身受其他因素的影響，我們應(yīng)該盡可能結(jié)合多種情況建立更多模型求解。（2）在求解完護(hù)士工作的規(guī)劃后，應(yīng)該設(shè)計(jì)一個(gè)影響護(hù)士自身出勤的因數(shù)、以及不同護(hù)士工作能力差別的因數(shù)，并在加權(quán)計(jì)算中體現(xiàn)【參考文獻(xiàn)】1 姜啟源、謝金星、葉俊./ 數(shù)學(xué)模型（第四版）. 北京: 高等教育出版社,2011.1；2 卓金武、李必文、魏永生./MATLAB在數(shù)學(xué)建模中的應(yīng)用（第2版）.北京：北京航空航天大學(xué)出版社3 三峽大學(xué) 2009年三峽大學(xué)數(shù)學(xué)建模熱身賽.網(wǎng)絡(luò)附錄模型一：1、五種模式組合分析Lingo程序代碼如下：model:! start1 11011;! start2 ;! start3 ;! start4 ;! start5 ;sets: times/1.12/: start1,start2,start3,start4,start5,required;endsetsdata: !每時(shí)段所需的最少護(hù)士數(shù); required = 15 15 15 35 40 40 40 30 31 35 30 20; ole(G:/值班.xls)=start1; ole(G:/值班.xls)=start2; ole(G:/值班.xls)=start3; ole(G:/值班.xls)=start4; ole(G:/值班.xls)=start5;enddata!最小化所需安排護(hù)士數(shù);min=sum(times: start1+start2+start3+start4+start5);!人數(shù)取整;for(times:gin(start1);for(times:gin(start2);for(times:gin(start3);for(times:gin(start4);for(times:gin(start5);for(times(J):start1(wrap(J+8,12)+start1(wrap(J+9,12)+start1(wrap(J+11,12)+start1(wrap(J,12)+ start2(wrap(J+7,12)+start2(wrap(J+9,12)+start2(wrap(J+11,12)+start2(wrap(J,12)+start3(wrap(J+7,12)+start3(wrap(J+9,12)+start3(wrap(J+10,12)+start3(wrap(J,12)+start4(wrap(J+7,12)+start4(wrap(J+8,12)+start4(wrap(J+10,12)+start4(wrap(J,12)+start5(wrap(J+6,12)+start5(wrap(J+8,12)+start5(wrap(J+10,12)+start5(wrap(J,12)= required(J);End運(yùn)行結(jié)果：2、四種模式下的隨機(jī)組合例：模式3、4組合Lingo程序代碼如下：model:! start3 ;! start4 ;sets: times/1.12/: start3,start4,required;endsetsdata: !每時(shí)段所需的最少護(hù)士數(shù); required = 15 15 15 35 40 40 40 30 31 35 30 20; ole(G:/值班.xls)=start3; ole(G:/值班.xls)=start4;enddata!最小化所需安排護(hù)士數(shù);min=sum(times: start3+start4);!人數(shù)取整;for(times:gin(start3);for(times:gin(start4);for(times(J):start3(wrap(J+7,12)+start3(wrap(J+9,12)+start3(wrap(J+10,12)+start3(wrap(J,12)+start4(wrap(J+7,12)+start4(wrap(J+8,12)+start4(wrap(J+10,12)+start4(wrap(J,12)= required(J);End運(yùn)行結(jié)果：模型二：1、，6種模式綜合求解model:! start1 11011;! start2 ;! start3 ;! start4 ;! start6 ;! start7 ;sets: times/1.12/: start1,start2,start3,start4,start6,start7,required;endsetsdata: !每時(shí)段所需的最少護(hù)士數(shù); required = 15 15 15 35 40 40 40 30 31 35 30 20; ole(G:/值班.xls)=start1; ole(G:/值班.xls)=start2; ole(G:/值班.xls)=start3; ole(G:/值班.xls)=start4; ole(G:/值班.xls)=start6; ole(G:/值班.xls)=start7;enddata!最小化安排加班護(hù)士數(shù);min=sum(times: start6+start7);!人數(shù)取整;for(times:gin(start1);for(times:gin(start2);for(times:gin(start3);for(times:gin(start4);for(times:gin(start6);for(times:gin(start7);!限定護(hù)士人數(shù)為80;sum(times: start1+start2+start3+start4+start6+start7)=80;for(times(J):start1(wrap(J+8,12)+start1(wrap(J+9,12)+start1(wrap(J+11,12)+start1(wrap(J,12)+ start2(wrap(J+7,12)+start2(wrap(J+9,12)+start2(wrap(J+11,12)+start2(wrap(J,12)+start3(wrap(J+7,12)+start3(wrap(J+9,12)+start3(wrap(J+10,12)+start3(wrap(J,12)+start4(wrap(J+7,12)+start4(wrap(J+8,12)+start4(wrap(J+10,12)+start4(wrap(J,12)+start6(wrap(J+6,12)+start6(wrap(J+7,12)+start6(wrap(J+9,12)+start6(wrap(J+11,12)+start6(wrap(J,12)+start7(wrap(J+6,12)+start7(wrap(J+8,12)+start7(wrap(J+9,12)+start7(wrap(J+11,12)+start7(wrap(J,12)= required(J);End運(yùn)行結(jié)果：2、組合模式隨機(jī)求解例：1、2、3、6、7模式Lingo程序代碼如下：model:! start1 11011;! start2 ;! start3 ;! start6 ;! start7 ;sets: times/1.12/: start1,start2,start3,star