\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem

  • * Corresponding author: Mohammed Abdelghany

    * Corresponding author: Mohammed Abdelghany 
Abstract Full Text(HTML) Figure(8) / Table(6) Related Papers Cited by
  • Nurse Rostering is the activity of assigning nurses to daily shifts in order to satisfy the cover requirements, taking into account the operational requirements and nurses' preferences. The problem is usually modeled as sets of hard and soft constraints with an objective function to minimize violations of soft constraints. The nurse rostering problem is known to be NP-hard. Many metaheuristics were used to tackle this problem. One of the frequently used heuristics is the Variable Neighbourhood Search (VNS). The VNS is usually used as a standalone method or in integration with another exact or heuristic method. In this paper, a new hybrid VNS and Dynamic Programming based heuristic approach is proposed to handle the nurse rostering problem. In the proposed approach, two perturbation mechanisms are adopted simultaneously. The proposed approach is tested on two different benchmark data sets. A comparison with state-of-the-art methods from literature revealed the competitive performance of the proposed approach.

    Mathematics Subject Classification: Primary: 90B35; Secondary: 90C59, 90C39.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Pseudo code for the hybrid VNS-DP approach

    Figure 2.  Pseudo code for VNS algorithm

    Figure 3.  Example for HWCF.1 structure

    Figure 4.  Example for HWCF.2 structure

    Figure 5.  Examples of vertical swaps

    Figure 6.  Examples of horizontal swaps

    Figure 7.  A dynamic programming structure for the nurse rostering problem

    Figure 8.  Pseudo code for the proposed Dynamic Programming based heuristic algorithm

    Table 1.  Benchmark instances main characteristics

    # Days Nurses Shift types Days-off Shifts on/off
    01 14 8 1 8 26
    02 14 14 2 14 62
    03 14 20 3 20 64
    04 28 10 2 20 71
    05 28 16 2 32 106
    06 28 18 3 36 135
    07 28 20 3 40 168
    08 28 30 4 60 225
    09 28 36 4 72 232
    10 28 40 5 80 284
    11 28 50 6 100 336
    12 28 60 10 120 422
    13 28 120 18 240 841
    14 42 32 4 128 359
    15 42 45 6 180 490
    16 56 20 3 120 280
    17 56 30 4 160 480
    18 84 22 3 176 414
    19 84 40 5 320 834
    20 182 50 6 900 2318
    21 182 100 8 1800 4702
    22 364 50 10 1800 4638
    23 364 100 16 3600 9410
    24 364 150 32 5400 13809
     | Show Table
    DownLoad: CSV

    Table 2.  Comparison for the performance of the VNS algorithm using classical and destroy-and-recreate perturbation mechanisms

    Instance Classical mechanism Destroy-and-recreate mechanism
    01 607 607
    02 828 922
    03 1001 1002
    04 1721 1717
    05 1249 1330
    06 2053 2147
    07 1077 1073
    08 1425 1741
    09 449 446
    10 4679 4320
    11 3458 3513
    12 4217 4327
    13 2423 2396
    14 1377 1584
    15 4996 5017
    16 3550 3556
    17 6391 6506
    18 5177 5601
    19 4789 5177
    20 9097 7689
    21 29486 27071
    22 61690 58226
    23 62195 53694
    24 402313 248016
     | Show Table
    DownLoad: CSV

    Table 3.  Comparison between the proposed VNS–DP approach and other methods in literature

    Instance VNS–DP Ejection chain Gurobi Branch & price CP–ILS
    01 607 607 607 607 607
    02 828 837 828 828 828
    03 1001 1003 1001 1001 1001
    04 1716 1718 1716 1716 1716
    05 1237 1358 1143 1160 1147
    06 2141 2258 1950 1952 2050
    07 1080 1269 1056 1058 1084
    08 1452 2260 1306 1308 1464
    09 446 463 439 439 454
    10 4656 4797 4631 4631 4667
    11 3512 3661 3443 3443 3457
    12 4119 5211 4040 4046 4308
    13 2120 2663 3109 2961
    14 1344 1847 1278 1432
    15 4637 5935 4843 4570
    16 3458 4048 3225 3323 3748
    17 6190 7835 5749 6609
    18 5095 6404 4760 5416
    19 4281 5531 5078 4364
    20 7274 9750 3591 6654
    21 26263 36688 132445 22549
    22 56091 516686 265504 48382
    23 51699 54384 38337
    24 226490 156858 177037
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison between the proposed VNS-DP approach and IP-VNS approach

    Instance VNS–DP IP–VNS
    01 607 607
    02 828 828
    03 1001 1001
    04 1716 1716
    05 1237 1143
    06 2141 1950
    07 1080 1056
    08 1452 1344
    09 446 439
    10 4656 4631
    11 3512 3443
    12 4119 4040
    13 2120 1905
    14 1344 1279
    15 4637 3928
    16 3458 3225
    17 6190 5750
    18 5095 4662
    19 4281 3224
    20 7274 4913
    21 26263 23191
    22 56091 32126
    23 51699 3794
    24 226490 2281440
     | Show Table
    DownLoad: CSV

    Table 5.  Comparison between results of the proposed VNS-DP approach and other state-of-the-art approaches tested on the competition instances

    Instance BKS VNS–DP ANS VDS RVNS HHSA
    Sprint_early01 56 56 56 56 56 56
    Sprint_early02 58 58 58 58 58 58
    Sprint_early03 51 51 51 51 51 51
    Sprint_early04 59 59 59 59 59 59
    Sprint_early05 58 58 58 58 58 58
    Sprint_early06 54 54 54 54 54 54
    Sprint_early07 56 56 56 56 56 56
    Sprint_early08 56 56 56 56 56 56
    Sprint_early09 55 55 55 55 55 55
    Sprint_early10 52 52 52 52 52 52
    Sprint_late01 37 37 37 37 37 37
    Sprint_late02 42 42 42 42 42 42
    Sprint_late03 48 48 48 48 48 48
    Sprint_late04 73 73 73 75 73 73
    Sprint_late05 44 45 44 44 44 44
    Sprint_late06 42 43 42 42 42 42
    Sprint_late07 42 47 42 42 43 43
    Sprint_late08 17 17 17 17 17 17
    Sprint_late09 17 17 17 17 17 17
    Sprint_late10 43 44 43 43 43 43
    Sprint_hidden01 32 34 32 32 32
    Sprint_hidden02 32 32 32 32 32
    Sprint_hidden03 62 62 62 62 62
    Sprint_hidden04 66 67 66 66 66
    Sprint_hidden05 59 59 59 59 59
    Sprint_hidden06 130 141 130 130
    Sprint_hidden07 153 153 153 153
    Sprint_hidden08 204 204 204 204
    Sprint_hidden09 338 338 338 338
    Sprint_hidden10 306 306 306 306
    Medium_early01 240 243 240 244 240 243
    Medium_early02 240 241 240 241 240 242
    Medium_early03 236 238 236 238 236 238
    Medium_early04 237 240 237 240 237 240
    Medium_early05 303 303 303 308 303 305
    Medium_late01 157 157 164 187 158 169
    Medium_late02 18 31 20 22 20 26
    Medium_late03 29 29 30 46 30 34
    Medium_late04 35 35 36 49 35 42
    Medium_late05 107 140 117 161 111 131
    Medium_hidden01 111 111 122 117 143
    Medium_hidden02 219 219 224 225 248
    Medium_hidden03 34 34 35 34 49
    Medium_hidden04 78 78 80 79 87
    Medium_hidden05 118 118 120 122 169
    Long_early01 197 197 197 198 197 197
    Long_early02 219 221 222 223 219 226
    Long_early03 240 240 240 242 240 240
    Long_early04 303 303 303 305 303 303
    Long_early05 284 284 284 286 284 284
    Long_late01 235 240 237 286 235 253
    Long_late02 229 229 229 290 229 256
    Long_late03 220 220 222 290 221 256
    Long_late04 221 221 227 280 224 263
    Long_late05 83 89 83 110 83 98
    Long_hidden01 346 346 346 349 380
    Long_hidden02 89 89 89 89 110
    Long_hidden03 38 38 38 38 44
    Long_hidden04 22 22 22 22 27
    Long_hidden05 41 41 45 41 53
     | Show Table
    DownLoad: CSV

    Table 6.  Comparison for number of best known solutions achieved by each approach

    Competition track VNS–DP ANS HHSA
    Sprint (30 instances) 77% 100% 97%
    Medium (15 instances) 60% 33% 0%
    Long (15 instances) 80% 67% 27%
     | Show Table
    DownLoad: CSV
  • [1] M. Abdelgalil, Z. Yahia and A. B. Eltawil, A proposed new dynamic programming formulation for the nurse rostering problem, in Proceedings of 47th International Conference on Computers and Industrial Engineering, 2017, 1–8.
    [2] H. Akita and A. Ikegami, A network representation of feasible solution space for a subproblem of nurse scheduling, Proceedings of the Institute of Statistical Mathematics, 61 (2013), 79-95. 
    [3] G. AlpanR. Larbi and B. Penz, A bounded dynamic programming approach to schedule operations in a cross docking platform, Computers and Industrial Engineering, 60 (2011), 385-396.  doi: 10.1016/j.cie.2010.08.012.
    [4] M. A. AwadallahM. A. Al-BetarA. T. KhaderA. L. Bolaji and M. Alkoffash, Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem, Neural Computing and Applications, 28 (2017), 463-482.  doi: 10.1007/s00521-015-2076-8.
    [5] J. Bautista and J. Pereira, A dynamic programming based heuristic for the assembly line balancing problem, European Journal of Operational Research, 194 (2009), 787-794.  doi: 10.1016/j.ejor.2008.01.016.
    [6] F. BellantiG. CarelloF. Della Croce and R. Tadei, A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153 (2004), 28-40.  doi: 10.1016/S0377-2217(03)00096-1.
    [7] S. Bouajaja and N. Dridi, A survey on human resource allocation problem and its applications, Operational Research, 17 (2017), 339-369.  doi: 10.1007/s12351-016-0247-8.
    [8] J. D. BuntonA. T. Ernst and M. Krishnamoorthy, An integer programming based ant colony optimisation method for nurse rostering, Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, 11 (2017), 407-414.  doi: 10.15439/2017F237.
    [9] E. Burke, P. De Causmaecker, S. Petrovic and G. V. Berghe, Variable neighborhood search for nurse rostering problems, in Metaheuristics: Computer Decision-Making, Springer, Boston, MA, 2003,153–172. doi: 10.1007/978-1-4757-4137-7_7.
    [10] E. K. BurkeT. CurtoisG. PostR. Qu and B. Veltman, A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem, European Journal of Operational Research, 188 (2008), 330-341.  doi: 10.1016/j.ejor.2007.04.030.
    [11] E. K. Burke and T. Curtois, New approaches to nurse rostering benchmark instances, European Journal of Operational Research, 237 (2014), 71-81.  doi: 10.1016/j.ejor.2014.01.039.
    [12] E. K. BurkeJ. Li and R. Qu, A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems, European Journal of Operational Research, 203 (2010), 484-493.  doi: 10.1016/j.ejor.2009.07.036.
    [13] E. K. BurkeT. CurtoisL. F. van DraatJ. Van Ommeren and G. Post, Progress control in iterated local search for nurse rostering, Journal of the Operational Research Society, 62 (2011), 360-367.  doi: 10.1057/jors.2010.86.
    [14] S. Ceschia, N. Dang, P. De Causmaecker, S. Haspeslagh and A. Schaerf, Second international nurse rostering competition, Annals of Operations Research, 274 (2019), 171–186, arXiv: 1501.04177. doi: 10.1007/s10479-018-2816-0.
    [15] T. Curtois and R. Qu, Technical Report: Computational Results on New Staff Scheduling Benchmark Instances, ASAP Research Group, School of Computer Science, University of Nottingham, UK, 2014.
    [16] F. Della Croce and F. Salassa, A variable neighborhood search based matheuristic for nurse rostering problems, Annals of Operations Research, 218 (2014), 185-199.  doi: 10.1007/s10479-012-1235-x.
    [17] J. Van den BerghJ. BeliënP. De BrueckerE. Demeulemeester and L. De Boeck, Personnel scheduling: A literature review, European Journal of Operational Research, 226 (2013), 367-385.  doi: 10.1016/j.ejor.2012.11.029.
    [18] S. C. Gao and C. W. Lin, Particle swarm optimization based nurses' shift scheduling, in Proceedings of the Institute of Industrial Engineers Asian Conference 2013, 2013,775–782. doi: 10.1007/978-981-4451-98-7_93.
    [19] R. A. M. GomesT. A. M. Toffolo and H. G. Santos, Variable neighborhood search accelerated column generation for the nurse rostering problem, Electronic Notes in Discrete Mathematics, 58 (2017), 31-38.  doi: 10.1016/j.endm.2017.03.005.
    [20] M. HadwanM. AyobN. R. Sabar and R. Qu, A harmony search algorithm for nurse rostering problems, Information Sciences, 233 (2013), 126-140.  doi: 10.1016/j.ins.2012.12.025.
    [21] S. HaspeslaghP. De CausmaeckerA. Schaerf and M. Stølevik, The first international nurse rostering competition 2010, Annals of Operations Research, 218 (2014), 221-236.  doi: 10.1007/s10479-012-1062-0.
    [22] F. Knust and L. Xie, Simulated annealing approach to nurse rostering benchmark and real-world instances, Annals of Operations Research, 272 (2019), 187-216.  doi: 10.1007/s10479-017-2546-8.
    [23] Z. Lü and J.-K. Hao, Adaptive neighborhood search for nurse rostering, European Journal of Operational Research, 218 (2012), 865-876. 
    [24] R. M'Hallah and A. Alkhabbaz, Scheduling of nurses: A case study of a Kuwaiti health care unit, Operations Research for Health Care, 2 (2013), 1-19.  doi: 10.1016/j.orhc.2013.03.003.
    [25] N. Musliu and F. Winter, A hybrid approach for the sudoku problem: Using constraint programming in iterated local search, IEEE Intelligent Systems, 32 (2017), 52-62.  doi: 10.1109/MIS.2017.29.
    [26] F. Mischek and N. Musliu, Integer programming model extensions for a multi-stage nurse rostering problem, Annals of Operations Research, 275 (2019), 123-143.  doi: 10.1007/s10479-017-2623-z.
    [27] E. RahimianK. Akartunali and J. Levine, A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems, European Journal of Operational Research, 258 (2017), 411-423.  doi: 10.1016/j.ejor.2016.09.030.
    [28] E. RahimianK. Akartunali and J. Levine, A hybrid integer and constraint programming approach to solve nurse rostering problems, Computers and Operations Research, 82 (2017), 83-94.  doi: 10.1016/j.cor.2017.01.016.
    [29] H. G. SantosT. A. M. ToffoloR. A. M. Gomes and S. Ribas, Integer programming techniques for the nurse rostering problem, Annals of Operations Research, 239 (2016), 225-251.  doi: 10.1007/s10479-014-1594-6.
    [30] A. M. Shahidin, M. S. M. Said, N. H. M. Said and N. I. A. Sazali, Developing optimal nurses work schedule using integer programming, AIP Conference Proceedings, 1870 (2017), 040031. doi: 10.1063/1.4995863.
    [31] P. SmetP. BruckerP. D. Causmaecker and G. V. Berghe, Polynomially solvable personnel rostering problems, European Journal of Operational Research, 249 (2016), 67-75.  doi: 10.1016/j.ejor.2015.08.025.
    [32] I. P. SolosI. X. Tassopoulos and G. N. Beligiannis, A generic two-phase stochastic variable neighborhood approach for effectively solving the nurse rostering problem, Algorithms, 6 (2013), 278-308.  doi: 10.3390/a6020278.
    [33] I. X. TassopoulosI. P. Solos and G. N. Beligiannis, A two-phase adaptive variable neighborhood approach for nurse rostering, Computers and Operations Research, 60 (2015), 150-169.  doi: 10.1016/j.cor.2015.02.009.
    [34] T.-H. WuJ.-Y. Yeh and Y.-M. Lee, A particle swarm optimization approach with refinement procedure for nurse rostering problem, Computers and Operations Research, 54 (2015), 52-63.  doi: 10.1016/j.cor.2014.08.016.
    [35] Z. Zheng and X. Gong, Chemical reaction optimization for nurse rostering problem,, in Frontier and Future Development of Information Technology in Medicine and Education, Springer, Dordrecht, 2014, 3275–3279. doi: 10.1007/978-94-007-7618-0_422.
    [36] Z. ZhengX. Liu and X. Gong, A simple randomized variable neighbourhood search for nurse rostering, Computers and Industrial Engineering, 110 (2017), 165-174.  doi: 10.1016/j.cie.2017.05.027.
    [37] , Instances & Results – Nurse Rostering Competition, (Accessed: April 25, 2019), https://www.kuleuven-kulak.be/nrpcompetition/instances-results.
  • 加载中

Figures(8)

Tables(6)

SHARE

Article Metrics

HTML views(1447) PDF downloads(680) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return