Int ern at i onal  Journ al of Ele ctrical  an d   C om put er  En gin eeri ng   (IJ E C E)   Vo l.   11 ,  No.   1 ,  Febr uar y   2021 , pp.  471 ~ 480   IS S N: 20 88 - 8708 ,  DOI: 10 .11 591/ ijece . v11 i 1 . pp471 - 480          471       Journ al h om e page :  http: // ij ece.i aesc or e.c om   A  n ovel  popu lation - bas ed  l ocal  s ea rc h    for  n urs e  rosteri ng p roblem       An m ar  Ab u h amdah 1 ,  W ad i i B ou li la 2 ,  G h aith M . Jar adat 3 ,  A na s  M.  Qut ei sh at 4 ,    Mutase m   K.   Alsma di 5 ,  Ibr ah im   A.   Alm ar as hde h 6   1 MIS   Depa rtment,   Fa cul t y   of  Bus ine ss   Adm ini stra ti on,   Taiba h   Uni ver sit y ,   Saudi   Arabi a   2 IS Depa rtment ,   Coll ege of   Com pute r  sc ie n ce   an d  Engi n ee ring ,   T ai bah   Univer sit y,   Saudi   Arabi a    2 RIAD I  La bora t or y ,   Nat ional  Sc hool  of  Com puter Sci en ce,  Mano ub a  Univer si t y ,   Tuni sia   3 Depa rtment of  Com pute r  Scie n ce ,   Facu lty   of   C om pute r  Scie n ce a nd  In form at ion   Technol og y ,   Jer ash  Univer sit y ,   J orda n   4 Depa rtment of  Com pute r  and   Network  Eng ineer ing,   Fa cul t y   of E ngine er ing  T ec h nolog y ,     Al - Bal qa a  Ap plied  Univer si t y ,   Jordan     4 El e ct ri ca l   and   C om pute r  Engi n e eri ng,   Facu lty   of   Engi n ee ring ,   So har   Univer si t y ,   Om an   5 ,6 MIS   Depa rtment,   Co ll eg e  of   A ppli ed   Studie s  a nd  Com m unity   Servic e ,     Im am Abdulra hm an  Bin  Faisa l U nive rsit y ,   Saud i  Arabi a       Art ic le  In f o     ABSTR A CT    Art ic le  history:   Re cei ved   Ma y   17 , 20 20   Re vised  Jun   3 0 ,   20 20   Accepte d  Aug 5 , 2 0 20       Populat ion - bas e d  appr oa che s  re gula rl y   are  bett er  th an  singl e  base d  (lo ca l   sea rch )  appr oaches  in  expl or ing   the   sea rch   spa c e.   How eve r ,   th e  dra wbac k  of   popula ti on - b ase d  appr oac h es  is  in  expl oiting  the   sea rch   spac e.   Se ver al   h y bri d   appr oac h es  hav e  prove n  the ir   eff icien c y   thr ough  diffe r ent   dom ai ns  of   opti m iz ation  pr oble m s  by   in c orpora ti ng  and   int egr a ti ng  the  strengt h  of  popula ti on  and  loc a l  sea rch   app roa che s.  Me anwhil e ,   h y br id  m et hods  have    a  dra wbac k  of  i ncr ea sing  th e  pa ramet er  tun ing.   Rec en tly ,   popu l at ion - b ase d   loc a l  sea r ch   was   proposed  for   a  unive rsit y   cour s e - ti m etabli ng   pr oble m   with   fewe r  par amete r s  tha n  ex isti ng  a pproa che s,   the  p roposed  appr oa c h  prove s  it s   eff ective n ess.  T he  proposed  app roa ch  emplo y s  t wo  oper at ors  to  i nte nsif y   and   dive rsif y   the   se a rch   spac e .   The   f irst  oper at or  is  appl ie d  to  a  singl e  soluti on ,   while   th e  sec on d  is  appl i ed  for  al l  solut ions.  Th is  pape r  a ims   to  inve stig ate   the   per fo rm anc e   of  population - base d  local  se a rch   for  th e  nur se  roster ing   proble m .   Th e  IN RC2010  databa s e  with   a  d ataset   compos e d  of  69  insta nc es  is   used  to  te st  the  per form anc e  of   PB - LS.   A  com par ison  was  m a de  bet wee n     the   p erf orm anc e   of  PB - LS  and   othe r  exi sting   a pproa che s  in  th e  l it er at ur e .   Result s  show   good  per form ances  of  proposed  appr oac h  compa red   to  oth er  appr oac h es,   where   population - base d  loc a l  sea r ch  provide d  bes t  result s  in     55  ca ses   over   69   insta n ce s used   i n  exp er iments .   Ke yw or d s :   Dive rsificat ions    Gr a vitat ion al   e m ula ti on   Local  s ea rch  a ppr oach es   Nurse  r ost erin g  p r oble m   Popu la ti on - b as ed  a ppr oach es   This   is an  open   acc ess arti cl e   un der  the  CC  BY - SA   l ic ense .     Corres pond in g  Aut h or :   An m ar F a khri  Abu ham dah ,    MIS  Dep a rtm e nt,  Fac ulty  of   Business  Adm i nistrati on ,   Tai bah Unive r sit y ,   Jana dah Bi n U m ay ya h  Road   Tay ba,  Me din a  4235 3,   Saudi  Ar a bia .   Em a il :  aabu ha m dah @tai bahu .edu.sa   ;   anm ar_ 81 @hotm ail.co m       1.   INTROD U CTION     Nurse  r os te ri ng  pro blem   (N RP)  invol ves  assigni ng   a  se t  of   nurse s  to   diff e ren t  s hift s  su bject   to     a  var ie ty   of   c onstrai nts  unti l  a  co m plete   ro ste r  is  const ru ct ed  [ 1 ,  2].  Co nst raints  in  the  NRP  pr ob le m   can  be   cat egorized  as   hard  a nd  s of t   [3 - 5].  T he  m ai n  goal ,  w he n  al locat in g  nurses   to  va rio us   s hifts  is  t o  fu l fill    the  ha rd   c onst rains  (i.e.  feasible  r os te rs )  an d  try   to  m ini m iz e  the  soft  co ns trai nts  as  m uch   a s  possi ble  with   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 870 8   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    47 1  -   480   472   pen al iz at io n  (in  orde r  to  pro duce  a  high - qu a li ty  nu rses  s hif ts).  The  sm al ler   value  in dicat es  a  bette r  qu a li ty  of  nurse  r os te ri ng  sh ifti ng.  NRP   is  an  NP - hard   pr oble m   du e  to  the  diff ic ulty   of   fin ding  optim al   sh ifts  [3 ,  4].   Howe ver, f i nd i ng a  ro ste rin g wit h  a  good  nu rse qu al it y reli es on t he  a pproach  us e d durin g  the  searc h [ 3 - 5] .   Re centl y,  seve ral  m et ho ds   ha ve  bee n  ap pl ie d  to  so lv e  NRP  [ 6 - 18] .  Jarad at   et   al .  [ 6]  propose d    the  hybri d  el it ist - ant  syst em   a lgorit hm .  The  pro po se d  al go r it h m   aim s  to  increase  t he  div ersit y  of  the  searc h  sp ace i n  the   el it ist - ant syst em   al gorithm  b y i nteg r at ing i t wi th ex te rn al  m em or y.    Ra j eswa ri  et   al .  [7 ]   us e d  a  m od i fied  ne lder - m ead  m et ho d  i n  the  bee  col ony  optim iz ation   al gorithm   for  m ulti - ob j ec ti ve  m a the m at i cal   program m i ng.  T he  m et ho do l og y  is  a  c om bin at ion   of  s pecific  local   s earch ,   honeybee  deci sion   m aki ng,  and   m ulti - age nt  par ti cl e  en vi ronm ent  syst e m .  Aw adall ah   et   al .  [8 ]   pr opose d    a h ybrid - har m on y sea rc h  al gorithm  w it h  hil l cl i m b ing  f or increasi ng  the e xp l oitat ion  m e chan ism . Th e authors   m od ifie d  the  m e m or y  to  ac cel erate  the  c onve r gen ce   rate   by  us in g  t he  global  s war m   op ti m iz ation   c on ce pt.   Santos  et   al .  [9 ]   us e d  int eger - pr ogram m ing   te chn i ques  of   the  c om pact  and   m onolit hic  form ulati on.     The  pro posed   te chn iq ue  is   di stribu te d  into   two  po ols,  th e  first  one  im pro ves  the   du al   bounds  f or  rapi d  so luti on  pro duct ion   to  l ow e r   the  opti m a l  so luti on,  w hile  the  sec ond  is   us e d  to  s pee d - up  the  pro duct ion    near - opti m al .  Aw a dalla h  et   al .  [ 10 ]   re plac ed  the  be e  op erator   i n  the  arti fici al   bee  colo ny  al gorithm   b y    the  hill - cl i m bin g  optim iz er  to  pro po se  a h y bri dizat ion   t hat ex pl oit s  the  se arch   s pace f or g oo d  s olu ti on q ualit y.   Burke  a nd  Cu rtois  [11],  pro po s ed   ne w  a ppr oac hes  for  branc h  a nd  pr ic e  al gorithm   and   a n  e j ect io n  chain ,   wh e re  they   int egr at e d  both  al gorithm s  by  us ing   the  dynam i c  program m ing   m et ho d.   L ü  a nd   Ha o  [ 5]  pro po s e d  an  a d aptive   ne ighbor hood  s earch   by  us in g  tw o  dif fer e nt   neig hborh oo d  m ov es  a nd  adap ti vely   al te rati on s   betwee n  thre e   intensific at io n  an d  di ver s ific at ion   searc h  strat egies  r efer rin g  to  the  searc h  hi story .     Bi lgin  et   al .  [ 12]   prese nted  a   gen e ral  hype r - heurist ic   ap pro ach  t hat  can   w ork  i nto   t wo  di ff ere nt  ti m et a blin g  healt hcar e  pro blem s ( i.e. p at i ent ad m issi on  an d nurse roste rin g)  and pr ov i ded  a set o f  a low - le vel h e ur i sti c fo r   each  prob le m .  Valo ux is  et   al .   [13]  pr opos e d  a  strat egy  bas ed  on   phases  t o  produce  a   good  qual it y  so luti on.   The  first  phase   deals  with   eac h  nurse   an d  ea ch  day  of  the  week  a nd  the  s econd   deals   wi th  a  s pecific   al locat ed   daily   sh ift.  N onobe  [ 14 ]   us e d  m et aheu risti c  base d  on  th e  co ns trai nt - op tim iz at ion   pro b le m   to  find  s uitable   values   to   va riables  that   ha ve  const raint  vio l at ion s’   weig ht.   The   a uthor   a dopted   the   ta bu  sea rc h  to   im pro ve     the  pe rfo rm ance  of  c on tr olli ng  dynam ic al l y  the  ta bu  te nu re .  He   us e d  c ons trai n  weig hts  to  e xam ine  so luti ons  durin g  t he neig hborh ood sea rc h.   Most  of   these  appr oach es  a re   hybr i dizat ion   betwee n  popul at ion - base d  an d  local - base d  appr oach es .   In   ge ner al ,   the   m a in  ad van ta ge  of   popula ti on - based  ap proach e s  is  their   abili ty   to  exp l or e  t he  researc h  s pace ,   wh e reas  l ocal - searc h  a ppr oa ches  a re  m o re  ada pte d  to   ex plo it   the  r esearch   spa ce   [19 - 35 ] .   T he refor e ,  com bin ing   the   popula ti on - ba sed  an d  local - searc h  ap pro aches  will   hel p  ta king  ad va ntage  of   thes e  tw o  appr oach es  a nd  pro du ce s  a  good  ap proach  fo r  s olv in g  NRP.  H oweve r,   com bin in g  these  two  a ppr oach e s   involves  c on si der i ng   a n  inc reasin g  num ber   of   par am eter s.  T his  cons ti tutes  a  new   chall eng e  f or   m os t   hybri dizat ion   appr oach es .  H ence,  m os t  re searche s  m ov e  towa rd   pro posing   oth e r  a ppro ac hes  with  f ew e r   par am et ers’   tu ning  f or  NRP .   The  m ai n  co ntributi on  of  t his   pa pe r  is  to   us e  popula ti on - base d  local   search    (P B - L S)   [ 36 ] ,   wh ic h  is  ap pl ie d  in  an oth e r  opti m iz at ion   prob le m   (i.e.  Course  ti m e t abling)  to  t he   nurse   ro ste rin g  pro bl e m .  PB - LS  ha s  pro ved   it s  e ff ic ie ncy  with   few e r  pa ram et ers;  hen ce ,  it   can  be  ap pli ed  to     the   NR P, w hich has  dif fer e nt  neig hborh ood  structu res.   Our  w ork  ai m s   to  stud y  the  pe rfor m ance  of   PB - LS  ov e r  th e  nurse  r os te ri ng   pro blem .  T he  pro pos e d  appr oach  will   help   to  obta in  a  good  qua li ty   so luti on   f or   nurs e  r os te rin g  s hiftin g.   In   orde r  t o  e valuate     the  e ff ic ie ncy  of   PB - LS,  we  com par e  the  pe rfor m ance  of   PB - LS  with  oth er  a ppro ac hes   app li ed  to  N RP  in     the li te ratur e . Si xty - nin e  d at as et s w ere  used  a nd r es ults in dic at e that PB - L S  can  pro du ce  go od r es ults.   Fo ll owin g  the  introd uction,  the  pa per   is  str uctu red   as  f ollow s .  Sect io n  2  pr ese nts  a  de scriptio n  of     the  dataset   us e d  in  this  pap e r .  Sect ion   3  de ta il s  the  pr opose d  m et ho do l ogy.  Sect ion   4  pr ese nts  the  re su lt s   ob ta ine d  by  ap plyi ng   PB - LS  to  the  co ns ide r ed  dataset   an d  discuss   it s  fi nding s .  Finall y,  Sect ion   5  co nc l ud e s   the p a pe r  a nd di scusses pe rsp e ct ives for  the  pro posed  wo rk.       2.   DA T AS ET   D ESCRIPT IO N   A  69  sta nd a r d  NRP  ben c hma rk   dataset s  ar e  us e d  to  te st  t he  pe rfo rm ance  of   t he  propo sed  m et ho d.  Dataset s  we re   ob ta ine d  f r om   PA TAT  2010,  i nter national  nurse  r os te rin g  c omplet ion   (INR C201 0,   https:/ /ww w.k uleu ven - ku la k.be/n rp c om petition /i ns ta nces )   [ 37 ]   a nd  a nothe r  ver si on  intr oduce d  i n  [ 38 ].  NRC2 010  dataset s  are  cl assif ie d  into  four   gro ups,  toy;   spri nt;  m edium   an d  lo ng   i ns ta nc es.  Toy  insta nc es  are   pro vid e d  f or  te sti ng   pur po se s,  w he re  the  ot her   t hr ee  s pri nt;  m ediu m   and   lo ng  insta nc es  are  pro vid e d  f or   com petit ion  pu rpose, an d use d by resea rc hers   to e valuate t he ir appr oac hes.    Each  dataset   of  the  t hr ee   co m pet it ion   data set s  co ntains  t hr ee   gro ups  of  instances ,  the   early ,  la te ,     and  hi dd e n  i ns t ance g r oups.  L at er  on,   an  up da te   with  e xtra  gro up   a dde d  to   them   na m ed  as  hin t g rou p.   T able 1  su m m arizes t he  dataset s th at   are  us ed  in  t his  p a per.    Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A novel   popula ti on - based  loc al se ar ch  for  nu rse r os te ri ng  pr oble m  ( An m ar   A buha mda h)   473   Table  1.   IN RC 2010  dataset s s umm arizat ion   Ins tan ces   Ear l y  ins tan ces   Hid d en  ins tan ces   Hin t ins tan ces   Late  in stan ces   Sp rint run   10   10   3   10   Mediu m   run   5   5   3   5   Lon g  r u n   5   5   3   5       3.   METHO DOL OGY   In  this  pa per,  a   popula ti on - ba sed  l ocal  sea rc h  a ppr oach  ( P B - LS)  is  pro posed  [ 36 ]   for  nu rse  ro ste rin g  pro blem s   (N RP).  PB - LS  is  assem bled  of   gr avita ti on al   em ulati on   local   s earch  ( GE LS),   based   on   the  natu ral  pr i nciple  of  gr avita ti on al   at tract ion   [ 39 ] .  P B - LS  is  pro po sed  to  ov e rc om e  so m e  of   the  po pu la ti on   base d   appr oach es  li m it at ion s su c h as  [ 36 ]:   -   Using  a  popula ti on   of  so luti on s  in  local   se arch   to  inc reas e  the  capab il it y  of   the  intens ific at ion   proce ss  and   to  ov e rc om e  the  weak ne ss  of   the   intensific at io n  process ,  w hich  le ads  to   non - si gn ific a nt   i m pr ovem ents.   -   Using  Me m or y  Gu ide  with  el it e  so luti on s   fo r  us e fu l  in f or m at ion   (in  de scen ding  ord er)   to  ov e rc om e     the  lim i ta ti on   of   the  a ppro a c hes  that  did   not  e m plo y  m e m or y  gu idanc e  fo r  the  sea r ch.   I n  ad diti on,    this  al lows   overco m ing   the  d epe ndency  on  rand om iz ati on   that  re qu i r es  a  rep ai r  m echan ism   to  be  eff ic ie nt i n  c onstrai ned pr ob le m s an d  overc om ing  the iss ue of  r a ndom ly  u pd at in g  t he p opulati on.   -   Less  par am et erized and  syst em ic al l y updati ng the  popula ti on.   PB - LS  pro ves  it s  eff ic ie ncy  over  a n  NP - ha r d  op ti m iz a ti on   pro blem   of   un i ver sit y  co urse  tim e ta bling  pro blem   [ 36 ] .  This  m otivated   us   to  us e  th is  m et ho d  f or   NRP  by  us i ng  diff e ren t  nei ghbo rho od   str uc tures.    PB - LS  sta rts  with  an  init ia l  popula ti on   a nd  trie s  to  m ini m iz e  so ft  con s trai nts  it erati v el y  by  exp lo ring   t hei r   neig hbor  s olu t ion s .  T hese  s olu ti ons  a re  obta ined   by  usi ng   one  or  m or e   nei ghbor hood  struct ur e s   over     the  current  so l ution.  For  m or e  detai ls  abo ut   the  con strai nts  Hint,  Hard  a nd   S of t  prese nt ed  in  the  IN R C201 0  dataset s  an d  th ei r  m a the m a ti c al   fo rm ulati on s ,  rea der s  ca n  re fer   to  [ 5].   As  i n  [ 6],  f our  gro up s   of  nei ghbo rho od  structu res  a re  use d:   -   Sing le   sh ift  pe r  d ay   neig hborh ood  st ru ct ur e  a sso ci at ed wit h har d  c onstrai nt .   -   Week e nd,   pe rs on al   re qu est ,  a lt ern at ive  qu al ific at ion s,   over tim e,  and   unde r  ti m e  are  the  m os t  vio la te d  const raints as s ociat ed wit h  s oft  constrai nts.   -   Shuffle , gree dy  sh uffle , c or e  sh uffle  to  s wa p l arg e  secti ons  of p e rs on al  sc he du le s .   -   Sh a ke  a  sh ift ,   week e nd, a nd t wo p e ople  for  so luti on s ha king .   PB - LS  cal c ula te s  the  gra vitat ion al   f orce  value  ( F,  as su m ing   m ini m iz at ion   prob le m )  by   cal culat ing   the  diff e re nce  betwee n  two  obj ect s;  the  tria l  so luti on s  obj ect iv e  functi on   values  (i.e .   Ts)  and   the  c urren t   so luti on  obj ect ive fu nction va lue ( i.e . Cs) as  pr ese nted  in  ( 1 ) .     F= Cs   -   Ts   (1)     Fig ure   1  s how s  the  ps e udo - c od e   f or  the   PB - LS  a ppr oac h  for  NRP.   Be lo w  the   de scri ption  of  s om e   te rm s that are u se d  in  Fig ure   1.   -   In it ia l   so luti on :   Si ;  an d   t he q ua li ty  o f  Si  deno te d  by  f( Si)     -   Be st ob ta in ed  s olu ti on: S b  a nd the  qu al it y o f Si  d e no te d by f (S b)   -   The  m axi m u m  n um ber   of it er at ion s  de no te d by N .m ax   -   Nu m ber   of it er at ion s t o  re set  the s olu ti on  dir ect ion s t o upda te  d en oted  b y   R.it er   -   Fo r ce  value fo r  gravity  d e note d by  force     -   N th   vel ocity  v e ct or  m e m or y t o pro vid e  direc ti on   value de note d by  VV n   -   Nu m ber   of s ha king  neig hborh ood   de no te d b y  Nsn   The   PB - LS  al gorithm   sta rts  with  a  zero   di rec ti on   val ue  (i.e.  zero   velocit y)  that  init ia li zes  t he  searc h,  and   the n  this   value  is  upda te d  thr oughout  the  searc h  process .  For  bette r  sh ifti ng,   the  search  s pace  i s   adm inist e red   by  the  force  value  ( us in g  ( 1 ) ),   an d  the n  the  search  s pace  is  intens ifie d  us in g  an y  local     search  al gorithm .  PB - LS  use s  the  MPC A - AR DA   al go rithm   [ 36 ]   as  a  local   search  du e  t o  it s  abili ty   of     com ple m entary  exp lo rati on  and   e xploit at io n.   MPC A - AR DA   is  pro po s e d  in  [ 40 ]   as  hy br idiza ti on  be tween  m ul ti - neighb orhoo d partic le  c olli sion  al gorithm  an d  a dap ti ve ran dom iz ed  d esce nt alg or it hm .   In   ste p  1  (i.e.  In it ia li zat ion   phase) ,  we  init ia li ze  al l   the  req ui red   par am eter s  m entioned   in  Table  2.   The n,   t he  init ia l  so luti on   for  the   m e m or y  of  the   ve loci ty   vector  vv   i s  ge ner at e d  by   app ly in g  s ha king   neig hborh oods.  I niti al ly ,  so lu ti on s  (vv 1 , …,  vv N )  ar e  produ ced  base d  on  the  nu m ber   of  neig hborh oods  a nd   their  directi ons  are  set  t o  ze ro  in the  vv   m e m o ry.     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 870 8   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    47 1  -   480   474         Figure   1. Pse udoc ode  for  PB - LS a ppro ac h [ 36 ]   over  nurse   ro ste rin g prob l e m       Table  2 .  Param et ers  use d i n P B - LS  for NRP   Para m eter   Valu e   N.ma x    Ter m in atio n  Criter ia ( m ax i m u m  ite rat io n s) equ al to 1 0 0 , 0 0 0   R. iter   Iter atio n s n u m b er  t o  r eset o r  to   retun e  the  d irection s eq u al to1 0   Nsn   Sh ak in g   n eig h b o rh o o d   stru ctu res   Lo ca l Sea rch   MPCA - ARDA  (ite ration s n u m b er  eq u al to1 0 )       In   ste p   2  (i.e.   I m pr ovem ent  ph ase ),   vv   m e m or y  is  reo r der e d  in  dec re asi ng   order   ba sed  on  their  directi on  value s.  T he  s olu ti on s ar e c om par ed  b ase d on their   directi on  value s,  an d  t he  s olu t ion   with t he high e st  directi on  value  is sele ct ed fo r furt he r  im pr ove m ent p ri or  t o othe r  s olu ti ons  in  vv .   a.   In  s te p  2.1 ,  if   al l  directi on  values   are   dif f eren t,   we   sel e ct   the  highest  so luti on  direct ion   val ue  a nd  set   S i =vv 1 ,  the n  M PCA - ARD A  is   app li ed  to  ge ner at e  S i *   unti l  the  stoppin g  crit eria  are  m e t.  MPC A - AR DA  us es  dif fer e nt  s hak i ng  nei ghbo r hood .  Lat er,  the  f or ce   val ue   is  cal culat ed  usi ng   ( 1 )   (i.e.   Cs  =  S i  an d   Ts= S i * )   and   is  a dded  ( neg at ive  or  po sit ive)  to  the  s tore d  directi on  value  of   vv 1 .   The  best  so l ut ion   (i.e .  Sb )  i s  updated  with  S i *   in  case  of   f( S i * )  (i.e.   the  qu al it y  of   S i * )   is  bette r  than   f( Sb )   (i.e.   the  qu al it y  of   S b).     If   the  qu al it y  of   S i *   is  bette r   than  S i ,  we  r eplace   vv 1   with  S i * .  Otherwi se,  the  unim pr ov e d  c ounter  i s  increase d  ( UnImpr ove 1 )  by  on e  for  the  s el ect ed  so luti on.  I n  case  U nImprove 1   is  equ al   to  pr e - s et   un im pr ove d  it erati on s  (i.e.  R .it er ),   the  directi on   of   vv n   is  returne d  to  zer o  a nd   vv 1   so l ution  is  change d  wi t h  the  best  neig hbo r  s olu ti on  ge ner at e d  f ro m   Sb   ra ndom   neig hbo r s   (i.e .  S b* )  by  s hak i ng  th e  neig hborh oo d s .  This  pr act ic abi li ty  tr ie s to  escape  from  local op ti m a and  att e m pts to  e xp a nd the  searc h sp ace.   b.   In   ste p  2.2,  i f  the  dir ect ion  va lues  are   sim ilar  f or  al l  vv   s olu ti ons,  ste p  2.1.a  is  e xec uted  to   disti ngui s h    the s olu ti ons  of sim i la r  direct ion   value s.  T hi s tries to  preser ve  a  set   of  div e rse  s olu ti ons.       4.   RESU LT S   The  pro pose d  appr oach   is  ex per im ented  for   25   r uns  (as  s ugge ste d  in  [ 6])   throu gh   69   in sta nces  that   wer e  a nnounc ed  in  I NRC2 010  ( https:/ /w ww.kuleu ve n - ku la k.be/n rp c om pet it ion /i ns ta nces)   for  10 0,000   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A novel   popula ti on - based  loc al se ar ch  for  nu rse r os te ri ng  pr oble m  ( An m ar   A buha mda h)   475   it erati on s.  T he   m achi ne  us e d  is  an  I ntel  Co re  i5  3.2   G Hz  proce ss or,  8   G B  RAM,  an d  t he  co de  im plem ented   us in g  j ava   la ng uag e   over   Net Be ans  I DE  v  8.2.  As  sta te d  in I NRC2 01 0,   the   instances   re quire  a  so l utio n  withi n  appr ox im at ely  10  seco nds  for   the  s pr int  i ns t ances,  10  m inu te s  f or  the  m edi um   instance s ,   an d  10  ho urs  f or     the lo ng insta nc es.    Howe ver,  dif fe ren t  fact or s  a ffec t  the  per f or m ance  of   the  m achine  su c h  as  m e m or y,  clo ck  s pee d  an d  the  op e rati ng  s yst e m .  Ther e f or e ,  the   res ults   of  the   r uns  a r e  obta ine d  at   diff e re nt  ti m es .  A s  dep ic te d  i n  [ 5],  si m ulati on s  in  our  a ppro ac h  a re  pe rfor m ed  unde r  rela xing  t i m eou t  conditi on s ,  a nd   we  e m plo y  10 00  se conds   for  t he  s pr i nt  instance s,  50 00  sec onds  f or  the   m edium  instance s  a nd  20  hours  f or  the  l ong  inst ances.     As  s how n  i n  T able 2, PB - LS   e m plo ys f our p aram e te rs:   a.   The   te rm inatio n  crit eria  ( N. ma x ),   w hich  i s  pr e sente d  in   [6 ]   a nd   ta kes   into  c onsider at ion   the  rel a x  tim eou t co nd it ion.   b.   Iterati on   num ber  to  r eset   (or r et un e )  the  d i re ct ion s  ( R.it er ) , whic h  is  pr e se nted  i n [ 2 ].   c.   Sh a king -   nei gh bo r hood  str uct ur es  ( Ns n ) , whi ch  is  pr e sente d i n [6 ] ;    d.   Iterati on   num ber   f or   t he  loc al   search  (in  t his  case,  MP CA - ARD A  use d  as  a  l ocal  search   with  10   it erati on s) , whi ch  is  pr e sente d i n [ 36 ] .    In  ord er   to  e va luate   the  pe rfo rm ance  of  PB - LS,  a   c om par ison  is  m ade  bet ween  PB - LS   pe rfor m ance   and   re su lt s  of   si m il ar  m et ho ds  based   on  thei r  publishe d  w orks .  Table  3  shows  a  com par ison   base d  on   s pr i nt  instances, Ta bl e 4  show s a c om par ison  b ase d  on m ediu m  i ns ta nces a nd Tab le  5  sho ws  a com par ison   ba sed  on   long in sta nces.   In  Tables   3 - 5,  the  be st  res ult  ob ta ine d  by  P B - LS  (d e note d  as  Best )   a nd  the  rank  of  PB - LS  ( de nted  a s   Ra nk )  are  il lust rated  an d  com par e d  to  the  ot her   a ppro ac hes .  The  best  res ul ts  so   far   are d e picte d  by  bold co lo r.   Me anwhil e,  in   T ables  3 - 5,  th e  e m pty  cel ls  with  a  sym bo l  ( - )  de no te   tha t  the  al go rithm   is  no t  ap plied   to  the  corres pondin g  instance,  f or  exam ple,  R4,  R6,  R7,  R9  a nd  R10   did   no t  a pp ly   their  al go rithm s  to  the  9  hin t  instances,  and  R6,  R 8  a nd R1 0 did n ot apply  their al gorith m s to  the 20  hid de n  i ns ta nces .       Table  3.   C om par iso n betwee n PB - LS  a nd sim il ar  m et ho ds   in the li te ratu re  u si ng sprint i nst ances   Dataset   PB - LS   R1   R2   R3   R4   R5   R6   R7   R8   R9   R1 0   Ran k   Bes t   sp rint_ early _ 0 1   8   57   57   56   58   56   56   56   56   57   56   56   sp rint_ early _ 0 2   Sa m e   58   59   59   64   58   58   58   58   59   58   58   sp rint_ early _ 0 3   Sa m e   51   51   51   59   51   51   51   51   51   51   51   sp rint_ early _ 0 4   Sa m e   59   59   59   67   59   59   59   59   60   59   59   sp rint_ early _ 0 5   Sa m e   58   58   58   63   58   58   58   58   58   58   58   sp rint_ early _ 0 6   2   54   54   53   58   54   54   54   54   54   54   54   sp rint_ early _ 0 7   Sa m e   56   56   56   61   56   56   56   56   56   56   56   sp rint_ early _ 0 8   Sa m e   56   56   56   58   56   56   56   56   56   56   56   sp rint_ early _ 0 9   Sa m e   55   55   55   61   55   55   55   55   55   55   55   sp rint_ early _ 1 0   Sa m e   52   52   52   58   52   52   52   52   52   52   52   sp rint_ h id d en _ 0 1   Sa m e   32   32   32   46   32   32   -   32   -   33   -   sp rint_ h id d en _ 0 2   Sa m e   32   32   32   44   32   32   -   32   -   32   -   sp rint_ h id d en _ 0 3   Sa m e   62   62   62   78   62   62   -   62   -   62   -   sp rint_ h id d en _ 0 4   Sa m e   66   66   66   78   66   66   -   66   -   67   -   sp rint_ h id d en _ 0 5   Sa m e   59   59   59   69   59   59   -   59   -   59   -   sp rint_ h id d en _ 0 6   Sa m e   130   130   134   169   130   130   -   130   -   134   -   sp rint_ h id d en _ 0 7   Sa m e   153   153   153   187   153   153   -   153   -   153   -   sp rint_ h id d en _ 0 8   Sa m e   204   204   204   240   204   204   -   204   -   209   -   sp rint_ h id d en _ 0 9   Sa m e   338   338   338   372   338   338   -   338   -   338   -   sp rint_ h id d en _ 1 0   Sa m e   306   306   306   322   306   306   -   306   -   306   -   sp rint_ h in t _ 0 1   2   75   78   73   90   -   75   -   -   78   -   -   sp rint_ h in t _ 0 2   2   46   47   43   56   -   46   -   -   47   -   -   sp rint_ h in t _ 0 3   2   50   50   49   69   -   50   -   -   57   -   -   sp rint_ late_ 0 1   Sa m e   37   37   37   52   37   37   37   37   40   37   37   sp rint_ late_ 0 2   2   42   42   41   56   42   42   42   42   44   42   42   sp rint_ late_ 0 3   2   48   48   45   60   48   48   48   48   50   48   48   sp rint_ late_ 0 4   2   73   73   71   95   73   73   75   73   81   75   76   sp rint_ late_ 0 5   Sa m e   44   44   46   57   44   44   44   44   45   44   45   sp rint_ late_ 0 6   Sa m e   42   42   42   52   42   42   42   42   42   42   42   sp rint_ late_ 0 7   Sa m e   42   42   44   55   42   44   42   42   46   42   43   sp rint_ late_ 0 8   Sa m e   17   17   17   19   17   17   17   17   17   17   17   sp rint_ late_ 0 9   Sa m e   17   17   17   17   17   17   17   17   17   17   17   sp rint_ late_ 1 0   Sa m e   43   43   43   54   43   43   43   43   46   43   44   No te:   R1 :  Hy b rid  Elitist - An t  S y ste m   [ 6 ],   R2 :  Directe d   Bee  Co lo n y   Op ti m izatio n   Alg o rith m   [ 7 ],   R3 :  Hy b ridizatio n   o f   h ar m o n y   se arc h   with   h ill - cli m b in g   [ 8 ],   R4 :  Integ er  p rog ra m m in g   tech n iq u es  [9],  R5 :  A  h y b rid  artif icial  b ee  c o lo n y   [ 1 0 ],   R6 :  New  ap p roach   f o r  b ranch   an d   p rice  alg o rith m   an d   an   ejecti o n   ch ain   [11 ],   R7 :  Ad ap tiv e  n eig h b o rhood   search  [ 5 ],   R8 :  Hy p er - h eu ristic  ap p roach   [ 1 2 ],     R9 : A  syste m atic  t wo - p h ase app roach  [ 1 3 ]  an d  R1 0 : A  g en eral  co n strain t  o p ti m iz atio n  [ 1 4 ].     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 870 8   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    47 1  -   480   476   Table  4.  C om par iso n betwee n PB - LS  a nd  sim il ar  m et ho ds   in the li te ratu re  u si ng m ediu m  instances   Dataset   PB - LS   R1   R2   R3   R4   R5   R6   R7   R8   R9   R1 0   Ran k   Bes t   m e d iu m _ earl y _ 0 1   Sa m e   240   241   245   280   240   245   244   240   242   240   241   m e d iu m _ earl y _ 0 2   Sa m e   240   241   243   281   240   245   241   240   241   240   240   m e d iu m _ earl y _ 0 3   Sa m e   236   236   239   287   236   242   238   236   238   236   236   m e d iu m _ earl y _ 0 4   Sa m e   237   237   245   278   237   240   240   237   238   237   239   m e d iu m _ earl y _ 0 5   Sa m e   303   303   310   330   303   308   308   303   304   303   304   m e d iu m _ h id d en _ 0 1   Sa m e   111   111   143   410   111   155   -   117   -   130   -   m e d iu m _ h id d en _ 0 2   Sa m e   220   220   230   412   221   254   -   220   -   221   -   m e d iu m _ h id d en _ 0 3   Sa m e   34   34   53   182   34   54   -   35   -   36   -   m e d iu m _ h id d en _ 0 4   Sa m e   78   78   85   168   78   94   -   79   -   81   -   m e d iu m _ h id d en _ 0 5   Sa m e   119   119   182   520   119   177   -   119   -   122   -   m e d iu m _ h in t_ 0 1   2   42   42   42   64   -   48   -   -   40   -   -   m e d iu m _ h in t_ 0 2   Sa m e   91   91   91   133   -   94   -   -   91   -   -   m e d iu m _ h in t_ 0 3   2   140   140   135   187   -   140   -   -   144   -   -   m e d iu m _ late_ 0 1   2   161   161   176   234   157   174   187   164   163   158   176   m e d iu m _ late_ 0 2   Sa m e   18   18   30   49   18   31   22   20   21   18   19   m e d iu m _ late_ 0 3   Sa m e   29   29   35   59   29   38   46   30   32   29   30   m e d iu m _ late_ 0 4   Sa m e   35   35   42   71   35   48   49   36   38   35   37   m e d iu m _ late_ 0 5   Sa m e   107   107   129   272   107   137   161   117   122   107   125       Table  5.  C om par iso n betwee n PB - LS  a nd sim il ar  m et ho ds   in the lit eratu re  u si ng lo ng  inst ances   Dataset   PB - LS   R1   R2   R3   R4   R5   R6   R7   R8   R9   R1 0   Ran k   Bes t   lo n g _ early _ 0 1   2   197   198   194   339   197   197   198   197   197   197   197   lo n g _ early _ 0 2   Sa m e   219   220   228   399   219   229   223   222   220   219   219   lo n g _ early _ 0 3   Sa m e   240   240   240   349   240   240   242   240   240   240   240   lo n g _ early _ 0 4   Sa m e   303   303   303   411   303   303   305   303   303   303   303   lo n g _ early _ 0 5   Sa m e   284   284   284   383   284   284   286   284   284   284   284   lo n g _ h id d en _ 0 1   Sa m e   346   346   389   4466   346   400   -   346   -   363   -   lo n g _ h id d en _ 0 2   Sa m e   89   89   108   1071   89   117   -   89   -   90   -   lo n g _ h id d en _ 0 3   Sa m e   38   38   48   163   38   51   -   38   -   38   -   lo n g _ h id d en _ 0 4   Sa m e   22   22   27   113   22   29   -   22   -   22   -   lo n g _ h id d en _ 0 5   Sa m e   41   41   55   139   41   56   -   45   -   41   -   lo n g _ h in t_ 0 1   2   40   40   40   126   -   42   -   -   33   -   -   lo n g _ h in t_ 0 2   2   28   28   29   122   -   30   -   -   17   -   -   lo n g _ h in t_ 0 3   Sa m e   55   55   79   278   -   83   -   -   55   -   -   lo n g _ late_ 0 1   Sa m e   235   235   249   588   235   257   286   237   241   235   235   lo n g _ late_ 0 2   Sa m e   229   229   261   577   229   263   290   229   245   229   229   lo n g _ late_ 0 3   Sa m e   220   220   259   567   220   262   290   222   233   220   220   lo n g _ late_ 0 4   Sa m e   221   221   257   604   222   261   280   227   246   221   221   lo n g _ late_ 0 5   Sa m e   83   83   92   329   83   102   110   83   87   83   83       As  s how n  in   Table s   3 - 5,   resu lt s  in dicat e  that  PB - LS   pro du ces  ve r y  good   qual it y  so luti ons.     The  pro pose d  appr oach   rea c hes  55  opti m a l  so luti on s  ou t   of   69  instanc es.  Wh il e  in  oth er  instan ces  PB - L S   ob ta ine d  t he  se cond ra nk ex ce pt in o ne  in sta nc e (i.e.  sprint _e arly _01).    Desp it e  that  PB - LS  has  obta ined   seco nd  place  i n  s om e  instances,   it   ou tpe rfo r m ed  the  sam e   appr oach es  in  oth e r  dif fer e nt  instances.  F or  exam ple,  PB - LS  ob ta ine d  the  ei gh th  rank  in  sp ri nt_ ea rly _01  an d  ou t perform ed  R2,  R4,  R5 ,  R6,  R7,  R 9  and  R10 .  I n  ad diti on ,  P B - LS  ou tperfo rm ed  R2  in  sp rint _ear l y_02,     R4  in  m ediu m _h i dd e n_02,  R 5  in  s pr int _late _07,   R 6  in  m edium _ear ly _01,   R7  i n  m edi um _h idd e n_01 ,  R9  i n  sp ri nt_hid den_ 01,  R1 0  in  sprint_lat e_ 05.  More ov e r,   PB - LS  outpe rfo r m ed  R1  in  sprint_ea rly _02,  R3  in  sp ri nt_ ea rly _02,   a nd  R8   in  s pri nt_ ea rly _02. Re su lt s  ind ic at e  that  PB - L S outpe rfor m ed  al l  appro ac hes   in   so m e   instances  a nd  ob ta ine d  sim ilar  pe rfor m anc es  to  ot her   a ppr oac hes  in  s om e  cases.  This   confirm s  that  PB - LS  can b e  c onside red  as  a   go od  a ppr oach  f or  N RP.  To   bette r  e val uate  t he  perform ance  of  th e  pro posed   a ppro ac h,   Fig ure   2  de picts  a  com par is on  betwee n  PB - L S  an d  oth e r  a ppr oac hes  ref e r eei ng   t o  the   nu m ber   of   best  r esults  (optim a l solution s ) o btained   ov e r  t he 69 i nst ances.   Figure   2  sho w s  the  num ber   of  best  resu lt s  obta ined   ov e r  69  dataset s  for  t he  pro posed   a ppr oach  an d  the  consi dered   existi ng   w ork s.  The  pr opos e d  ap proac h  obta ined  55  be st  op ti m al   so luti on s  over  69   in sta nces .   R4  com es  in  t he  seco nd  rank  with  52  be s t  op tim al   so luti on s.  R3  c ome s  in  the  la st  rank  with  on l y  on e     o ptim al  so luti on .   Figure   3  de picts  furthe r  a nal ysi s  by  com par in g  sim i la r,   worse  a nd  bette r  res ults  of   t he  pro po s e d  appr oach  ove r  the  69   instan ce s  to  t he  oth e r  c on si der e d  ap proach e s.  In  the   le gend,  the  blue   col or   de no te s   that   the  pro pose d  a ppr oach   has  t he   sam e  nu m be r  of  bette r  res ults  than   the  e xisti ng   a ppr oa ch.   T he  or a ng e  colo r   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A novel   popula ti on - based  loc al se ar ch  for  nu rse r os te ri ng  pr oble m  ( An m ar   A buha mda h)   477   represe nts   the  nu m ber   of  tim es  that  the  pr opose d  ap proac h  has  the  best   resu lt s.  The  gray   color   re pr esents     the  num ber   of  tim es  that  the  existi ng  ap pro ach  has  t he  be st  res ults.  F or  exam ple,  the  pro posed   ap pr oa ch  a nd   R1  ob ta in ed  62  si m il ar  nu m ber   of  best  sol ution s .  Howe ver,  the  pro posed  ap proac h  ou t perform ed  R1  in     7  cases .  I n  a ddit ion ,   in  al l  cases,  PB - LS  ob ta ine d  se ve r al   bette r  res ul ts  gr eat er   tha n  the  ot her  exi sti ng   appr oach es  ( orang e  ba r  agai nst   gr ay   ba r).   T able   6  s umm ar iz es  exp e rim en ta l  resu lt s  achi eved   by  PB - L S  over   sp ri nt insta nce s,  Ta ble 7 f or the m edium  instances,  a nd Ta ble 8 f or the l ong i ns ta nces.           Figure   2. Com par is on of t he nu m ber   of b e st res ults  obta ine d ov e r  t he 69 i ns ta nces           Figure   3. The   nu m ber   of sim i la r,   worse a nd  bette r  re su lt s c om par ed  t o  the  prop os ed  app r oach       Table  6.  E xper i m ental  r esults  for our a ppr oa ch on I NRC2 010 o ve r  s pr i nt instances   Dataset   Bes t   av g   σ   Ti m e   sp rint_ early _ 0 1   57   5 8 .7   1 .8   4*   sp rint_ early _ 0 2   58   5 8 .6   1 .0   3*   sp rint_ early _ 0 3   51   5 1 .8   0 .7   7*   sp rint_ early _ 0 4   59   6 0 .1   0 .8   4*   sp rint_ early _ 0 5   58   5 8 .2   0 .4   6*   sp rint_ early _ 0 6   54   5 4 .2   0 .4   3*   sp rint_ early _ 0 7   56   5 6 .6   0 .5   3*   sp rint_ early _ 0 8   56   5 6 .4   0 .4   4*   sp rint_ early _ 0 9   55   5 5 .5   0 .7   4*   sp rint_ early _ 1 0   52   5 2 .5   0 .4   6*   sp rint_ h id d en _ 0 1   32   3 3 .9   1 .2   68   sp rint_ h id d en _ 0 2   32   3 3 .5   1 .1   86   sp rint_ h id d en _ 0 3   62   6 3 .5   1 .9   6*   sp rint_ h id d en _ 0 4   66   6 7 .2   0 .7   24   sp rint_ h id d en _ 0 5   59   5 9 .6   0 .6   8*   sp rint_ h id d en _ 0 6   130   1 3 3 .4   2 .4   48   sp rint_ h id d en _ 0 7   153   1 5 6 .1   3 .7   5*   sp rint_ h id d en _ 0 8   204   2 0 5 .8   1 .6   71   sp rint_ h id d en _ 0 9   338   3 4 0 .2   2 .8   34   sp rint_ h id d en _ 1 0   306   3 0 6 .6   1 .9   7*   sp rint_ h in t _ 0 1   75   7 7 .2   5 .4   44   sp rint_ h in t _ 0 2   46   4 9 .2   2 .9   26   sp rint_ h in t _ 0 3   50   5 4 .7   6 .7   35   sp rint_ late_ 0 1   37   3 8 .3   1 .1   23   sp rint_ late_ 0 2   42   4 3 .7   1 .5   18   sp rint_ late_ 0 3   48   5 0 .2   0 .9   8*   sp rint_ late_ 0 4   73   7 6 .6   2 .4   28   sp rint_ late_ 0 5   44   4 5 .1   0 .8   6*   sp rint_ late_ 0 6   42   4 2 .5   0 .6   9*   sp rint_ late_ 0 7   42   4 3 .9   0 .9   8*   sp rint_ late_ 0 8   17   17   0   5*   sp rint_ late_ 0 9   17   17   0   4*   sp rint_ late_ 1 0   43   4 5 .2   1 .2   10*       Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 870 8   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    47 1  -   480   478   Table  7.   E xper i m ental  r esults  for our a ppr oa ch on I NRC2 010 o ve r  m edium   instances   Dataset   Bes t   av g   σ   Ti m e   m e d iu m _ earl y _ 0 1   240   2 4 1 .6   1 .7   957   m e d iu m _ earl y _ 0 2   240   2 4 1 .5   1 .1   567*   m e d iu m _ earl y _ 0 3   236   2 3 8 .6   1 .2   921   m e d iu m _ earl y _ 0 4   237   2 3 8 .7   1 .4   249*   m e d iu m _ earl y _ 0 5   303   3 0 5 .3   1 .8   353*   m e d iu m _ h id d en _ 0 1   111   1 2 0 .8   3 .8   2153   m e d iu m _ h id d en _ 0 2   220   2 3 3 .7   8 .2   4370   m e d iu m _ h id d en _ 0 3   34   3 5 .9   1 .9   705   m e d iu m _ h id d en _ 0 4   78   8 2 .4   2 .5   2081   m e d iu m _ h id d en _ 0 5   119   1 2 9 .3   5 .4   4429   m e d iu m _ h in t_ 0 1   42   5 1 .8   4 .6   1505   m e d iu m _ h in t_ 0 2   91   1 0 5 .3   7 .6   2453   m e d iu m _ h in t_ 0 3   140   1 5 1 .1   8 .7   2691   m e d iu m _ late_ 0 1   161   1 7 2 .6   6 .3   3553   m e d iu m _ late_ 0 2   18   2 1 .8   2 .3   2417   m e d iu m _ late_ 0 3   29   3 2 .9   2 .2   583*   m e d iu m _ late_ 0 4   35   3 6 .8   0 .7   1108   m e d iu m _ late_ 0 5   107   1 1 6 .7   6 .8   4230       Table  8.  E xper i m ental  r esults  for our  a ppr oa ch on I NRC2 010 o ve r  lo ng in sta nces   Dataset   Bes t   av g   σ   Ti m e   lo n g _ early _ 0 1   197   2 0 1 .4   3 .7   1 1 1 1 4 *   lo n g _ early _ 0 2   219   2 3 1 .3   6 .3   1 2 0 2 1 *   lo n g _ early _ 0 3   240   240   0   3 0 4 1 *   lo n g _ early _ 0 4   303   3 0 4 .9   0 .7   5 1 1 2 *   lo n g _ early _ 0 5   284   2 8 5 .6   1 .2   8 3 9 2 *   lo n g _ h id d en _ 0 1   346   3 5 5 .9   5 .4   2 1 2 9 7 *   lo n g _ h id d en _ 0 2   89   9 1 .6   2 .8   1 8 8 4 4 *   lo n g _ h id d en _ 0 3   38   4 0 .1   1 .2   1 4 9 4 7 *   lo n g _ h id d en _ 0 4   22   2 4 .9   1 .5   2 4 6 6 3 *   lo n g _ h id d en _ 0 5   41   4 5 .2   2 .7   2 6 6 9 0 *   lo n g _ h in t_ 0 1   40   4 2 .8   1 .8   1 5 0 6 0 *   lo n g _ h in t_ 0 2   28   3 0 .2   1 .1   1 4 2 5 1 *   lo n g _ h in t_ 0 3   55   5 7 .5   1 .5   3 1 6 9 4 *   lo n g _ late_ 0 1   235   2 3 9 .2   2 .7   2 4 8 1 1 *   lo n g _ late_ 0 2   229   2 3 0 .8   1 .2   1 6 9 6 6 *   lo n g _ late_ 0 3   220   2 2 2 .1   1 .0   2 4 0 3 5 *   lo n g _ late_ 0 4   221   2 2 4 .3   2 .4   1 5 4 0 6 *   lo n g _ late_ 0 5   83   8 4 .9   0 .7   2 0 4 3 4 *       In   Ta ble s   6 - 8,   the  best  r esult  ob ta ine d  over  25   r un s  is  de note d  by  Best ,  t he  ave ra ge  res ult  is  denoted   by  av g ,   the   sta nd a r d  dev ia ti on  is  de no te d  by   σ ,  an d  t he  c om pu ta ti on al   t i m e  of   the   be s t  resu lt   is  de note d  by   Time   ( wh e re   *  is  the  ti m e  lim i t  in  IN RC 20 10).   Fo r  e xam ple,  in  Table  6,  the  PB - LS  achieve s     a  value  of   57   as  the  best   re s ult  (over   25  r uns)  for  s pr i nt_e arly _01  insta nce  in  4  seco nds,  with  an  a ve rag e  of  58.7   a nd  a  sta nd a r d  de viati on  of  1.8 .  Ta bles  6,   7,   a nd   8  il lustrate   that  P B - LS  obta ins  43   out  of   69  instance s   within t he  ti m e  lim i t (which  m ark ed  as  *) of INRC 20 10.   Re su lt s  in  Tabl e s   3 - 5,  a nd  a na ly sis  in  Fig ure   2  a nd  Fig ure  3  co nf irm   that  the  pro po se d  a ppr oac h  ca n  pro du ce   go od  qual it y  so luti on s   f or  the   NRP  c om par ed  to   ot her  ex ist ing   a ppro a c hes  i n  the   li te ratur e .     In   a ddit i on ,  re su lt s  in  Ta bles   6 - 8  s how  t hat  the  pro pose d  app r oach   r un s  in  a  go od   m ann er  for  al l  inst ances   with  instance s  of  d ive rsity .   A s  a  perpecti ve  to  this  w ork   wil l  be  to  ap ply  the  propose d  ap proac h  in  the  c onte xt   of  rem ote  sens ing   big  data  [ 41 - 4 4 ] ,  t o  e xp lore   t he  c on te xt  of   ca se - bas ed  reasonin g  usi ng  ‘ hype r - he ur ist ic ’   [45,  4 6 ] , a nd to  ev al uate  the e f fect o f un ce rtai nty i n  the  pr oc ess of sea rc h  f or nur s e r os te ri ng pr ob le m  [ 4 7 - 49 ] .        5.   CONCL US I O N     In  this   pa per,  we  pro po se d  a  popula ti on - bas ed  l ocal  searc h  ap proac h  (P B - LS)  f or  the   nur se  r os te r i ng   pro blem .   The  popula ti on - bas ed  is  m otivate d  by  a  gr a vitat ion al   em ulati o n  local   search  al gorithm   to  intensify  the  searc h  spa ce  and   by  a n  MPC A - AR DA   t o  di ver si fy  the  s earc h.  A  com par iso n  is  m ade  betwee n    the  pe rfo rm ance  of  the prop ose d  a pproach  a nd p er form ances  of  ot her  exiti ng  ap proac hes  in  the  li te ratu re   over   69   dataset s.  I n  this  pa pe r,   te n  existi ng  ap proac hes  are  consi der e d  f or   com par ison.  Re su lt s  ind ic at e  that    the pr opos e d  a ppr oach p rod uc es a  good  qu a li ty  so luti on  c om par ed  to t he e xisti ng appr oa ches.     Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A novel   popula ti on - based  loc al se ar ch  for  nu rse r os te ri ng  pr oble m  ( An m ar   A buha mda h)   479   Our  a ppr oach   ob ta ine d  55  optim a l  so luti ons   over  69  cases ,   an d  it   is  ra nk e d  fi rst  w hile  c om par ing   it   to  oth e r  ap proach e s  accor di ng   to  the  nu m ber   of   op ti m al   so luti on s.   Additi on al ly ,  resu lt s  ind ic at e  that    the  pro posed  appr oach   ou t pe rfor m ed  al l  t he  existi ng  ap proac hes  w hile  com par ing   t he  num ber   of  bette r   so luti ons  to  t he   nu m ber   of   worse  s olu ti on s.  Thes e  res ults  confirm   the  good  pe rfo rm a nce  of  the  pro po s ed   appr oach f or  s olv in g  t he pr ob lem  o f  nurse ro ste ring .   As  f utu re  wor k,   we  pr opos e   to  us e  m or e  case  stud ie s  to  te st  the  per f or m ance  of   th e  pr op os e d  appr oach   a nd   t o  ap ply  it   in  con te xt  of   rem ote  sensing   big   data .  A dd it io na ll y,  in  this  pap er ,  we  us e  a  sing le   heurist ic   ap pro ach  wit h  di ff e r ent  nei ghbor hoods  over  a  popula ti on  of  s olu ti ons;  w hic h  is  ch os e n  ba sed  on   gr a vity   form ul a.  A no t her   c ha ll eng in g  to pic  to  be  e xplore d  i s  the  stu dy  of   t he  case - base d  reasonin g  m eth od  to   al low  us in g  of   ‘h y per - he uri sti c’.  T his  will   he lp  to  deter m i ne   the  bette r  he ur ist ic   f or   a  gi ven   popula ti on,  a nd  hen ce  avoidi ng  so l ving  prob le m s f ro m  scr at ch.       REFERE NCE S     [1]   P.  Brucke r ,   et   a l . ,   “ Personnel  sc hedul ing:   m ode l s  and  complexi t y , ”   Eur opean   J ournal  of   Oper ati onal   R es earc h,   vol.   210 ,   no .   3 ,   p p.   467 - 473 ,   201 1.   [2]   M.  Dorigo  and  T.   Stütz l e,   “ Ant  col on y   op ti m iz a t ion:   over vie w  an d  rec ent   adv anc e s, ”   Handbook  of  Meta heur isti cs ,   Springer,   pp .   22 7 - 263,   2010 .   [3]   I .  I .  I.   B art hold i,   “ A gua ran te ed - a cc ura c y   round - o ff  al gorit hm   for c y cl ic   sche du li n g  and  set  cove r in g, ”   Oper erati on s   Res earc h ,   vol .   2 9 ,   no .   3 ,   pp .   501 - 510,   1981 .   [4]   H.   H.  Mill ar  an d  M .   Kira gu,   “ C y c li c  and  non - c y clic  sche dul in g  of  12  h  shift   nurses  by   ne twork  progra m m ing , ”   Eur opean   J ourn al  of   Oper ati ona l   R es earc h ,   vol .   104 ,   no .   3 ,   pp .   5 82 - 592,   1998 .   [5]   Z.   Lü   and   H.   K.   Hao,   “ Adapt ive   n ei ghborhoo d  sea rch   for  nu rse  roster ing , ”   Eur opean   J ourn al  of   Oper at ion al   Res earc h ,   vol .   2 18 ,   no .   3 ,   pp .   86 5 - 876,   2012 .   [6]   G.   M.  Jara dat ,   e t   al . ,   “ H y brid  E li t ist - Ant  S y stem  for  Nurs e - Rosteri ng  Problem, ”   Journal  of  King  Sa ud  Univ ersity   –   Computer  and  I nformation  Sc ience s ,  vo l. 31 ,   no.   3 ,   pp.   378 - 384  2019.   [7]   M.  Raj eswari ,   e t  al . ,  “ Dire ct ed  Bee   Colon y   Op ti m iz a t ion  Algorit hm   to  Solve  the   Nurs e  Rosteri ng  Proble m, ”   Comput ati onal   I nte ll ige n ce and   Neurosci ence ,  v ol.   2017 ,   pp .   1 - 2 6,   2017 .   [8]   M.   A.  Aw ada ll a h,   et al. ,  “ H y brid iz a ti on  of  har m o n y   sea r ch  with  h il l  c li m bing  for  highly   const ra in ed  nurse  roster in g  proble m , ”   Neura l  Comput ing   and   Appl ic at ions ,   vo l.   28 ,   no .   3 ,   pp .   4 63 - 482,   2017 .   [9]   H.   G.  Santos,   e t  al. ,  “ Inte ger   p rogra m m ing  te c hnique s  for  th e  nurse  roster ing   proble m , ”   Ann a ls  of   Oper ati ons   Res earc h ,   vol .   2 39 ,   no .   1 ,   pp .   22 5 - 251,   2016 .   [10]   M.   A.  Aw ada ll a h,   et   al. ,  “ A  hy b rid  art ifici al   bee  col on y   for  a  nurse  roster ing  proble m , ”   Appl ied   Soft   Comput ing ,  vol.   35 ,   pp .   726 - 739,   2015 .   [11]   E.   K.  Burke  an d  T.   Curtoi s,  “ New  appr oac he s  to  nurse  roster ing  benc hm ark   insta nce s, ”   Eur opean   J ournal  of   Oper ati onal   Res earc h ,   vo l. 237 ,   no.   1 ,   pp .   71 - 81 ,   2014.   [12]   B.   Bil gin,   e t  al . ,  “ One  hy pe r - heur isti c  appr oa ch  to   two  ti m et abl ing   proble m s  in  hea lt h  ca re , ”   J ourn al  of   Heuristic s ,  vol.   18 ,   no .   3 ,   pp .   401 - 434 ,   2012 .   [13]   C.   Valouxi s,  et   al . ,   “ A  sy st emat ic   two  phase   ap proa ch  for  th e  nurse  roster ing  pr oble m , ”   Eur o pean   J ournal  of   Oper ati onal   Res earc h ,   vo l. 219 ,   no.   2 ,   pp .   425 - 4 33,   2012 .   [14]   K.  Nonobe,   “ INRC2010:  An  appr oa ch  usi ng  a  gen eral   constra in t  op ti m iz ation  solv er, ”   The  F irst     Inte rnatio nal  N urs e  Roste ring  Competi ti on   ( PA TAT - 2010) ,   2010 .  [Online ] .   Avai la bl e:   ht t p:/ /www . kule uv en - kortri jk . be/ nrp co m pet it ion .   [15]   J.   F.  Ba rd  and   H .   W .   Purnom o,   “ Prefe ren c e  sch e duli ng  for   nurse s  using  col um n  gene ra ti on, ”   European  Journal   o f   Operational   Re s earc h ,   vo l. 164 ,   no.   2 ,   pp .   510 - 5 34,   2005 .     [16]   H.   G.  Santos,   e t  al. ,  “ Inte ger   p rogra m m ing  te c hnique s  for  th e  nurse  roster ing   proble m , ”   Anna ls  of  Operations  Re search ,   vol .   2 39 ,   no .   1 ,   pp .   22 5 - 251,   2016 .   [17]   S.  Ceschia,   et   a l. ,  “ Solving  the  INRC - II  nurse  roster ing  prob l emb y   sim ula t ed   anneal ing  b ase d  on  la rg e - sca le  nei ghborhoods, ”   i n   Proce edi ngs   of  the  12th  In t ernati onal   Conf enf ere n ce  on   Pr act i ce   and   Theo ry  of  Aut omat ed  Timetabl ing   ( PA TAT - 2018) ,   2018.   [18]   L.   Antoine,   et   a l. ,  “ A  rota ti on - b ase d  bra nch - and - pric e  app roa ch  for  the nurse  sch edul ing  probl em, ”   Math emati ca l  Program ming  Computati on ,   pp.   1 - 34,   2019 .   [19]   C.   Blum   and  A.  Roli ,   “ Met ahe ur isti cs  in  combinat ori al   opt imizat ion:   over v ie w  a nd  conc ep tual  c om par ison, ”   AC M   Comput ing   Surv eys ,   vo l. 35 ,   no.   3,   pp .   268 - 308 ,   2003.   [20]   D.  y v az,   e t  a l. ,  “ Perform anc e  ev a lua ti on   of  evo lutionar y   heu ristics  in  d y namic   en vi ronm ent s, ”   App l ied   Int el l ige n ce ,    vol.   37 ,   no .   1 ,   pp .   130 - 144 ,   2012 .     [21]   H.   R.   Cheshm ehga z,   et   a l. ,  “ Eff ective   loc a l  evol uti on ar y   se arc hes  distr ibuted  on  an  isla n d  m odel   solving    bi - objecti v e  opt i m iz at ion   problem s, ”   Appl i ed   In t el l ig ence ,   vol .   3 8 ,   no .   3 ,   pp .   331 - 356,   2013 .   [22]   M.  K.  Alsm adi ,   “ Quer y - sensit i ve  sim il ari t y   m ea sure  for  con t ent - base d  imag e  ret ri eval  using  m et a - heur ist ic   al gorit hm , ”   Jou rnal  of  King  Sa ud  Unive rs it y - C omputer  and  Inf orm ati on  Sci en c es ,   vol.  30,   no .   3,   pp.   373 - 381 ,   2018.   [23]   M.  K.  Alsm adi,   “ Conte nt - Base d  Im age   R et ri e val   Us ing  Co lo r,   Shape   and   T e xture  Descri p t ors  and  Fe at ure s, ”   Arabian  Journal   for Scie n ce   a nd  Engi ne ering ,  vol .   45 ,   pp .   3317 - 3 330 ,   2020 .   [24]   M.  K.  Alsm adi ,   et   a l. ,  “ Robust  fea tur e  ex tra c ti on   m et hods  f or  ge ner al   f ish  class ifi cation, ”   I nt ernati onal  Journal  o f   El e ct rica l  &   Co mputer  Engi n ee r ing ,   vo l. 9,  no.   6,   pp.   5192 - 5204,   2019.   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 870 8   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    47 1  -   480   480   [25]   M.  K.  Alsm adi ,   “ Hy b rid  Gene ti c  Algori thm  with  Ta bu  Sear ch  with  Bac k - Propaga ti on  Al gorit hm   for  Fis h   Cla ss ifi c at ion :  D et ermining   the  Appropria te  Fea ture   Se t, ”   Int e rnational   Journal  of  Applied   Enginee ring  Re searc h ,  vol.   14 ,   no .   23 ,   p p.   4387 - 4396 ,   2 019.   [26]   M.  K.  Als m adi ,   “ An   eff ic ie n t  sim il ari t y   m ea sur e  for  cont ent   b ase d  image  ret ri eva l  us ing  m em et i c  al gori thm, ”   Egy pti an   Journa l  of   Basic and A ppli ed   Scienc es ,   vol.   4 ,   no .   2 ,   pp .   112 - 122,   2017 .   [27]   M.  Alsm adi ,   “F ac i al   Re cogni t io n  under   Expre ss ion  Vari a ti ons ,”   The  Inte rnation al  Arab  Journal   of  Information  Technol ogy ,   vo l. 13,   no.   1A,   pp .   133 - 141,   2016 .   [28]   M.  Alsm adi ,   et   al . ,  “ A  hy br id  m emeti c  a lgori th m   with  bac k - propa gation  cl assifi er  for  fish  cl assific a ti on  base d  o n   robust  feature s  ext ra ct ion   from   PLGF   and  shape   m ea surem e nts, ”   In formatio n  Technol og y  J ournal ,   vol .   10 ,     no.   5 ,   pp .   944 - 9 54,   2011 .   [29]   M.  Alsm adi ,   et   al . ,  “ Fis h  Cla ss i fic a ti on:  Fis h  Cla ss ifi c at ion  Us ing  Mem et ic   Algori thms   with  Bac k  Propaga t io n  Cla ss ifi er ,”   LAP L ambert   Aca d e m ic   Publishing,  2012.   [30]   K.  Yous ef ,   et   al . ,   “ Appl y ing  the   big   bang - b i g  cru nch   m et a heur isti c  to  la r ge - size d   oper at i onal   probl ems , ”     The  Inte rnat iona l  Journal   of   Elec tric al   and  Comp ute r E ng ine ering   ( IJE CE) ,  v ol .   1 0,   no .   3 ,   pp .   284 8 - 2502,   2020 .   [31]     A.  Abuham dah,   “ Adapti ve  e li t ist - ant   s y s te m   for  m edi ca l   cl ust ering  proble m , ”   The  Journal   of  K in g  Saud  Univ ersit y   -   Computer  and   Information  Sc ience s ,  v ol .   32,   pp.   709 - 717 ,   2020 .   [32]     A.  Abuham dah,   “ Adapti ve  Acc ept a n ce   Criterio n  (AA C)  al gorit hm   for  Optimiza ti on  Problems , ”   T he  Journal  of  Computer  Scien ce ,  v ol .   11 ,   no .   4 ,   pp .   675 - 691 ,   2 015.   [33]     A.  Abuham dah,  et  al. ,   “ Adapti v e  Grea t  De luge   (AG D)  for  Medic a l  Clust eri ng  Problem , ”   T he  I nt.   J.  Eme rg.   Sc i .   ( IJE S) , v ol .   4 ,   n o.   1 ,   pp .   1 - 13 ,   2 014.   [34]   A.  Abuham dah,   et   al . ,   “ H y brid iz a ti on  Bet we en   Ite rative   Sim ula te d  Annea li ng  and  Modifie d  Grea t  Delug e  for   Medic a l  Cluste r i ng  Problems , ”   World  of  Computer  Scienc e  and  Information  Tec hnology   Journal   ( WCSIT ) ,   vol.   2 ,   n o.   4 ,   pp .   131 - 1 36,   2012 .   [35]     A.  Abuham dah  and  M.  A y ob,   “ Adapti ve  Rando m iz ed  Desce nt  Algorit hm   using  Round  Robin  f or  Solv ing  Course   Ti m et ab li ng  Pro ble m s , ”   Int ernat ional   Conf ere nc e  on  Int ellige n t  Syste ms   Design  and  Appl i cat ion s  ( ISDA )   IEE E ,    pp.   1201 - 1206 ,   2010 .   [36]   A.  Abuham dah,  et   al . ,  “ Popula ti on  base d   loca l  sea r ch  for  un ive rsi t y   cour se  ti m et abling  pro ble m s, ”   App l ied   Inte ll ige n ce ,   vol .   40 ,   no.   1,   pp.   44 - 53,   2013 .   [37]   S.  Haspesla gh,   et   al. ,  “ The   fir st  int ern ational   nurse  roster ing  competi ti on , ”  A nnals  of  Opera ti ons  Re search ,    vol.   218 ,   no .   1 ,   p p.   221 - 236 ,   201 4.   [38]   S.  Ceschia,   et   al. ,  “ The   se cond  in te rna ti ona l  nurse   roster ing  compe ti ti on , ”   Annal s  o f  Operations  R ese arch ,   vo l.   274 ,   pp.   171 - 186 ,   20 1 9 .   [39]   B .  L .   W ebster,   “ Solving  combinat ori al  opti m i za t ion  probl ems   using  a   new  a lgori thm  bas ed   on  g rav i ta t iona l   at tr ac t ion, ”   PhD   the sis,  Co ll eg e  o f  Engi n ee ring   a t F lori da  Inst it ut e of  Technol og y ,   2004.   [40]   A.  Abuham dah  and  M.  A y ob,   “ MP CA - AR DA   f or  solvi ng  cour s e  ti m etabli ng   pr oble m s, ”   i n  3rd  conf ere n ce   on   d ata  mining  and  op tim izati on  ( DMO ) ,   New York ,   pp .   171 - 177,   2011 .   [41]   I.   Chebbi ,   e t  al. ,  “ Big  dat a:   C once pts,  ch al l en ges  and  appl ica ti ons , ”   i n  Computati onal  co ll e ctive   intelligen ce ,  Springer,   Ch am,   pp.   638 - 647,   20 15.   [42]   I.   Chebbi ,   e t  al.  “ A  compari son  of  big  remote  sensing  dat a  proc e ss ing  with  Hado op  MapReduc e  and  Spark , ”  in  4 th  Inte rnational   C onfe renc e  on  A dvanc ed  Te chno logi es  for  Signa l  and  Image  Pr oce ss ing  ( ATSIP) ,   IEE E ,  pp.   1 - 4 ,   2018.   [43]   W .   Bouli l a,   et   al . ,  “ A  novel  d ec ision  support   s y stem  for  th e  i nte rpre ta t ion  of  remote  sensing  big  data ,”   Eart h   Sci en ce Inf orm at ic s ,   vo l. 11 ,   no.   1,   pp .   31 - 45 ,   20 18.   [44]   W .   Bouli la,  “ A  top - down  appr oac h  for  sem an ti c  segm entati on   of  big  remote   sensing  images ,”   Earth  S ci en ce  Informatic s ,   vo l.  12 ,   no.   3,   pp.   29 5 - 306,   2019 .   [45]   I.   R.   Fara h ,   e t  al . ,  “ Inte rpre tati on  of  m ult i - sensor  remote  sensing  images:  m ult i - app roa ch  fusi on  of  unce rt ai n   informati on, ”   I E EE   Tr ansacti ons   on  Geosci ence and R emot e  S en sing ,   vol .   46 ,   no .   12,   pp.   4142 - 41 52,   2008 .   [46]   I.   R.   Fara h ,   e t  a l. ,   “ Multi appr oa ch  s y stem  base d   on  fusion  of  mul ti spec tral  imag es  for  la nd - cov e r  cl assifi ca t ion,”  IEE E   Tr ansacti o ns on  Geosci ence  and  Re mot e  S e nsing ,   vol .   46 ,   n o.   12 ,   pp .   4153 - 4161,   2018 .   [47]   A.  Ferc hi chi,  et   al . ,   “ Reducing  u nce rt ai nt ie s  in   l a nd  cove r   ch ange  m odel s  using  s ensit ivit y   ana l y s is,”   Know le dge   and  Information Syste ms ,   vol .   55 ,   no  . 3,   pp.   719 - 7 40,   2018 .   [48]   W .   Bouli l a,   al.,  “ Com bini ng  Dec ision  Fus ion  and  Unce r ta in t y  Propaga ti on   to   Im prove   La nd   Cover  Chang e  Predic ti on  in  Sa te llite   Im age   Da ta base s, ”  The  Journal  of  Mult imedi a  Proce ss ing   and  Technol ogie s ,   vol.   2,   no.   3,   pp.   127 - 139 ,   20 11.   [49]   W .   Bouli la,  et   al.,   “ Sensiti vi t y   an aly s is a pproa ch  t o  m odel   epi stemic  and  a leator y   i m per fec ti on :  Applicati on  to La n d   Cover  Chang e  p red iction  m odel, ”  Journal   of   com putat ional sci en ce ,   vol .   23 ,   pp .   5 8 - 70,   2017 .       Evaluation Warning : The document was created with Spire.PDF for Python.