應用有區域搜尋與修復機制之混和基因與粒子群優化演算法於護理偏好排程

Abstract

護理人員的排程規劃問題是一個複雜且具有大量限制的NP-hard問題，其目的是要規劃一定週期內護理人員的工作班次與休假日。近年來的研究，逐漸將護理人員選擇喜歡工作班次與休假日的權益納入排班時的考量，目的是盡可能讓每位護理人員都可以分配到喜歡的工作班表。然而，在計算護理人員喜歡的工作班次與休假日的對工作班表喜歡程度時，都只利用在當期工作班次偏好與休假日偏好在班表滿足的次數作為評比的依據，卻忽略工作班次與休假日兩者滿足次數是不相同的，且當護理人員發生偏好相同的工作班次或休假日的衝突時，也沒有一個可以決定優先順序的方法，去解決指派工作班次與休假日給誰的問題。同時，因為護理排程問題的多種限制下，在演算法的執行過程中也容易產生了大量違反班表限制的解，使得不易找出符合班表限制且符合全體護理人員偏好的解答。因此，本文重新提出一個改良的適應值函數與一個含有修復違反班表排程限制結果的機制的混和基因-粒子群優化演算法，應用於有指派優先順序的護理偏好排程問題上。混和基因-粒子群優化演算法為一個結合粒子群優化演算法中鳥群的飛行溝通的行為與基因演算法中能進行交換突變產生多樣化的特性概念的混合演算法。此外，本研究針對演算法於護理排程問題，設計兩種不同的區域搜尋方法，並使用動態機率調整機制來選擇合適的區域搜尋。最後，在班表總滿意度最大的目標下，與有動態機率調整機制的基因演算法進行實驗與比較。實驗結果顯示，有動態機率調整機制與修復機制之混和基因-粒子群優化演算法表現比相同條件的基因演算法來的更好，且求解出的班表可以在符合班表的限制下，可以公平地去滿足護理人員偏好的工作班次與休假日。

Nurse scheduling problems are highly constrained and complex NP-hard problems which aimed to determine the work shifts and days-off of each nursing staff member within the planning schedule period (a week or a month generally). In the recent works to take into consideration the nursing staff’s preferences in planning the schedule of work shifts and days-off. When evaluated the preference of the work shifts and days-off at the current schedule period, however, the previous studies only focused on the times of satisfied preference at the current schedule period but ignored the times of satisfied preference between the work shifts and days-off are not equally. And when nurses had conflicted on the same work shifts or days-off at the current schedule period, there were not any priority to determine which one should be assigned. Because of the highly constrained of the problem it would be easy to generate infeasible solutions frequently during the computational process. Therefore, this paper proposes an improved fitness function and a hybrid GA-PSO algorithm that incorporates the recovery scheme. A hybrid GA-PSO algorithm is combined the concept of diversity in genetic algorithm and the concept of society communication in particle swarm optimization. Furthermore, nurse scheduling problem is solved by a hybrid GA-PSO algorithm with a dynamic local search selection scheme and recovery scheme. Finally, the experiments which compared to genetic algorithm with dynamic local search selection scheme for the case in a real hospital showed that our proposed algorithm not only better and fairly accomplishes the assignment of most nursing staff members to their preferred work shifts and days-off, but also satisfies all constraints.