A 2-Stage Approach for the Nurse Rostering Problem
In this paper, we are addressing the NP-hard nurse rostering problem utilizing a 2-stage approach. In stage one, Monte Carlo Tree Search (MCTS) and Hill Climbing (HC) are hybridized in finding a feasible solution (satisfying all the hard constraints). We propose a new constant C value (which balance...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022
|
| Subjects: | |
| Online Access: | http://ir.unimas.my/id/eprint/39561/1/A%202-Stage%20-%20Copy.pdf http://ir.unimas.my/id/eprint/39561/ https://ieeexplore.ieee.org/document/9805588 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Universiti Malaysia Sarawak |
| Language: | English |
| Summary: | In this paper, we are addressing the NP-hard nurse rostering problem utilizing a 2-stage approach. In stage one, Monte Carlo Tree Search (MCTS) and Hill Climbing (HC) are hybridized in finding a feasible solution (satisfying all the hard constraints). We propose a new constant C value (which balances search diversification and intensification of MCTS) and tree policy/node selection function in the
selection procedure of MCTS. In stage two, the feasible solution is further improved using Iterated Local
Search (ILS) with Variable Neighbourhood Descent as the local search component. We introduce several unique neighbourhood structures for the ILS. In addition, we propose a novel perturbation strategy to allow the search to escape from local optimum. The proposed methodology is tested on the Shift Scheduling dataset (24 benchmark instances). New best results are reported for seven and two instances for the 10 and 60 minutes run respectively. An in-depth discussion on the attributes of the proposed methodology that lead to its good performance is provided. |
|---|