Constructing modified variable neighborhood search approaches to solve a nurse scheduling problem
提出了多种改进的变邻域搜索方法，结合贪心机制解决护士排班问题，通过案例验证能生成最优或接近最优的排班方案，优于其他元启发式算法。
This study proposed multiple revised variable neighborhood search (VNS) approaches applying the greedy concept to solve a nurse scheduling problem (NSP). In this paper, we developed three greedy-neighbourhood-swapping mechanisms (greedy-2-exchange, greedy-3-exchange, and greedy-4-exchange) to conduct local searches based on one-, two-, or three-neighbourhood structures that accounted for constraints imposed by government and hospital regulations. The greedy-neighbourhood-swapping mechanisms were used to identify medical staff members with the highest soft-constraint (e.g. nurses’ preferences) violation weights on a given day who then swapped their shifts with others. To validate the proposed VNS approaches, we also conducted a case study. Based on the testing instances, all of the proposed VNS approaches generated optimal or near-optimal solutions, and the differences between them were small. The optimal number of the neighbourhood structures was determined to be two, confirming that a larger number of neighbourhoods in a neighbourhood structure would not necessarily be associated with more easily escaping local optima. Furthermore, the resulting outcomes supported the conclusion that the proposed modified VNS approaches generated better schedules for the medical staff members of hospitals than the compared meta-heuristic algorithms.