×

Harmony search with novel selection methods in memory consideration for nurse rostering problem. (English) Zbl 1309.90023

Summary: The selection methods of population-based metaheuristics provide the driving force to generate good solutions. These selection methods select the individuals with a higher fitness to be members of the population in the next iteration correspond to the natural rule of Darwin’s principle survival-of-the-fittest. Harmony search algorithm is a population-based metaheuristic, which mimicking the musical improvisation process where a group of musicians play the pitches of their musical instruments seeking for a pleasing harmony. It improvises the new harmony based on three rules: memory consideration, random consideration, and pitch adjustment. In this paper, we investigate the replacement of the original random selection of memory consideration with a set of selection methods in order to speed-up the convergence. These selection methods include tournament, proportional, and liner rank of Genetic Algorithm, and Global-best of Particle Swarm Optimization. The proposed harmony search with the different memory consideration selection methods evaluated using standard dataset published in the first International Nurse Rostering Competition INRC2010. Nurse rostering problem is a combinatorial optimization problem tackled by assigning a set of nurses with different skills to a set of shifts over predefined scheduling period. Experimentally, the tournament memory consideration selection method achieved the best rate of convergence as well as the best results in comparison with the other memory consideration selection methods.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/j.amc.2011.11.095 · Zbl 1246.65021 · doi:10.1016/j.amc.2011.11.095
[2] DOI: 10.1016/j.amc.2013.04.053 · Zbl 1298.90131 · doi:10.1016/j.amc.2013.04.053
[3] DOI: 10.1109/TSMCC.2011.2174356 · doi:10.1109/TSMCC.2011.2174356
[4] DOI: 10.1016/j.amc.2010.03.114 · Zbl 1193.65094 · doi:10.1016/j.amc.2010.03.114
[5] DOI: 10.1007/s10462-010-9201-y · doi:10.1007/s10462-010-9201-y
[6] DOI: 10.1007/978-3-642-27242-4_4 · Zbl 06066218 · doi:10.1007/978-3-642-27242-4_4
[7] DOI: 10.1007/978-3-642-34481-7_45 · Zbl 06265077 · doi:10.1007/978-3-642-34481-7_45
[8] DOI: 10.4018/jncr.2012040102 · doi:10.4018/jncr.2012040102
[9] DOI: 10.1016/j.jksuci.2012.10.004 · doi:10.1016/j.jksuci.2012.10.004
[10] DOI: 10.1016/j.ejor.2012.11.029 · Zbl 1292.90001 · doi:10.1016/j.ejor.2012.11.029
[11] DOI: 10.1007/s10479-010-0804-0 · Zbl 1251.90116 · doi:10.1007/s10479-010-0804-0
[12] DOI: 10.1016/0377-2217(94)00063-I · Zbl 0915.90169 · doi:10.1016/0377-2217(94)00063-I
[13] DOI: 10.1016/j.ejor.2007.04.030 · Zbl 1149.90346 · doi:10.1016/j.ejor.2007.04.030
[14] DOI: 10.1057/jors.2009.118 · Zbl 05799648 · doi:10.1057/jors.2009.118
[15] DOI: 10.1023/B:JOSH.0000046076.75950.0b · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b
[16] DOI: 10.1007/3-540-48873-1_25 · doi:10.1007/3-540-48873-1_25
[17] DOI: 10.1016/S0377-2217(99)00391-4 · Zbl 0952.90007 · doi:10.1016/S0377-2217(99)00391-4
[18] DOI: 10.1016/S0377-2217(03)00021-3 · Zbl 1045.90027 · doi:10.1016/S0377-2217(03)00021-3
[19] DOI: 10.1016/S0377-2217(97)00281-6 · Zbl 0991.90055 · doi:10.1016/S0377-2217(97)00281-6
[20] DOI: 10.1016/j.cma.2008.02.006 · Zbl 1194.74243 · doi:10.1016/j.cma.2008.02.006
[21] DOI: 10.1016/j.comcom.2008.03.019 · Zbl 05398220 · doi:10.1016/j.comcom.2008.03.019
[22] DOI: 10.1007/11539902_92 · doi:10.1007/11539902_92
[23] DOI: 10.1016/j.amc.2007.09.049 · Zbl 1146.90501 · doi:10.1016/j.amc.2007.09.049
[24] DOI: 10.1177/003754970107600201 · doi:10.1177/003754970107600201
[25] DOI: 10.1016/j.amc.2010.09.049 · Zbl 1206.90220 · doi:10.1016/j.amc.2010.09.049
[26] Goldberg D., Complex Systems 3 pp 493– (1989)
[27] DOI: 10.1016/j.cor.2005.03.018 · Zbl 1120.90019 · doi:10.1016/j.cor.2005.03.018
[28] J. H. Holland, Adaptation in Natural and Artificial Systems 2 (The University of Michigan Press, Ann Arbor, 1975) pp. 10–15.
[29] DOI: 10.1007/978-3-642-00185-7_2 · doi:10.1007/978-3-642-00185-7_2
[30] DOI: 10.1016/j.compstruc.2009.01.003 · doi:10.1016/j.compstruc.2009.01.003
[31] DOI: 10.1016/j.cma.2004.09.007 · Zbl 1096.74042 · doi:10.1016/j.cma.2004.09.007
[32] DOI: 10.1016/j.ejor.2011.12.016 · Zbl 06066902 · doi:10.1016/j.ejor.2011.12.016
[33] DOI: 10.1016/j.amc.2006.11.033 · Zbl 1119.65053 · doi:10.1016/j.amc.2006.11.033
[34] DOI: 10.1016/j.engappai.2013.05.008 · doi:10.1016/j.engappai.2013.05.008
[35] DOI: 10.1016/S0377-2217(97)00006-4 · Zbl 0955.90027 · doi:10.1016/S0377-2217(97)00006-4
[36] DOI: 10.1016/j.amc.2007.09.004 · Zbl 1146.90091 · doi:10.1016/j.amc.2007.09.004
[37] DOI: 10.1016/j.ijepes.2010.12.031 · doi:10.1016/j.ijepes.2010.12.031
[38] DOI: 10.1016/j.eswa.2008.11.049 · Zbl 05857033 · doi:10.1016/j.eswa.2008.11.049
[39] DOI: 10.1016/j.ejor.2011.12.042 · Zbl 1244.90104 · doi:10.1016/j.ejor.2011.12.042
[40] DOI: 10.1016/j.cie.2011.02.013 · doi:10.1016/j.cie.2011.02.013
[41] DOI: 10.1007/3-540-61794-9_51 · doi:10.1007/3-540-61794-9_51
[42] DOI: 10.1016/j.eswa.2010.09.120 · doi:10.1016/j.eswa.2010.09.120
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.