Indonesi an  Journa l  of El ect ri cal Engineer ing  an d  Comp ut er  Scie nce   Vo l.   13 ,  No.   1 ,  Jan uar y   201 9 ,   pp.  191 ~ 198   IS S N: 25 02 - 4752, DO I:  10 .11 591/ijeecs .v1 3 .i 1 .pp 191 - 198          191       Journ al h om e page :  http: // ia es core.c om/j ourn als/i ndex. ph p/ij eecs   An ant c olony  algorith m  for uni versiti  sul tan zain al abid in  examina tion time tabling p ro bl em       Ah m ad   Fir daus Kh air ,  M okhairi   Makh t ar ,  Muni rah  Ma z lan,  Moh am ad   Af e ndee  Moh amed ,    Mohd  N ordin  Ab d ul R ah m an   Facul t y   of  Infor m at ic s a nd   Com puti ng,   Univer sit i  Sulta n   Z ai n al   Abidin,   Te r engg anu,   Ma lay si a        Art ic le  In f o     ABSTR A CT    Art ic le  history:   Re cei ved   A ug   20 , 201 8   Re vised Oct  30 , 2 018   Accepte d Nov  19 , 201 8       The   re al - li fe   co nstruct ion  of  ex aminat ion  ti m etabli ng  prob le m   i s  conside red   as  a  comm on  proble m   that   al wa y s  en cou nte red   and  ex per ie n ce d  in  educ a ti ona l  insti tution  whether  in  school,  col le g e,   and   unive rsi t y .     Thi s  probl em  is  usually   exp eri en ce d  b y   th e  a ca d emic  m ana gemen t   depa rtment   where   they   h ave  trouble  to   ha ndle   complexi t y   for   assig n   exa m ina t ion  into  a  suita b le   t imeslot  m anua l l y .   In  thi s  pape r ,   a n  al gori thm   appr oac h  of  an t  col on y   op ti m isation  (ACO )  is  pr ese nte d  to  find  a n  eff ec t iv e   soluti on  for  dea l i ng  with  Univer siti   Sult an   Za inal  Abidi n  (UniSZA)  exa m ina t ion  ti m et ab li ng  probl e m s.  A  combinat ion  of  heur ist ic  with  ACO  al gorit hm   cont r i bute s  the   deve l opm ent   soluti on  in  orde r  to  si m pli f y   an d   opti m iz e  the   ph ero m one  occ urr enc e  of  m a tri x  updat es  which  i ncl ude   the  constra in ts  proble m .   Th e  imple m ent at ion  o f  re al   da ta se t  inst a nce s  from   ac ad emic  m ana g ement  is  appl i ed   to  the   appr oa ch   for  gen erati ng  t he  resul t  of   exa m ina t ion  ti m et ab le .   Th e  resul t  and  per form anc e  that  obta in ed  will   be  used   for  furthe r   use  t o  evalua t e   th e  q ual ity   and   obser ve  th e  solut ion  whethe r  our   exa m ina t ion  ti m et ab li ng  s y s te m   is  reliab l e  and   eff i ci en t  th an  the   m anual   m ana gement that can  d ea l   th e co nstrai nts pr ob lem .   Ke yw or ds:   An t c olony  op t i m isa t ion   Con st raints   Exam inati on  ti m et abling   Heurist ic   Ph e ro m on e   Copyright   ©   201 9   Instit ut e  o f Ad vanc ed   Engi n ee r ing  and  S cienc e .     Al l   rights re serv ed.   Corres pond in g  Aut h or :   Ah m ad  Fir da us K hair ,   Faculty  of In form atics and  C om pu ti ng ,    Un i ver sit i S ultan Zai nal Abid in,    Tereng ganu,  Ma la ysi a .   Em a il :  fird aus kh ai r@ ya ho o. c om       1.   INTROD U CTION     In   t he  la st  dec ade,  se ve ral  of  researc h  reg a r ding  ex am inatio n  ti m et abling  has  been   co nducte d  ov e r   the  world wide   by  pr e vious  researc hers.  G ener al ly ,  the  def i niti on   of  tim et able  can  descr i be  as  schedu l e   plan ning  on   pa rtic ular  e ven ts  that  ta ke  place  in  certai n  plac es.  I n  aca dem i c,  besi de  ti m e t able  f or   e xam i nation,   it   al so   can  be  us e d  for  orga ni zi ng   a  par ti cu la r  su bject   or  course.  F or  this  stud y,  exam i nation  ti m et abl ing   i s   descr i bing  a  li st  that  sh ow s   the  tim es   in  the  week   at   wh ic h  s pecif ic   exa m inati on   is  held.   Ty pical ly ,     the  distrib utio n  of  exam inati on   ti m e ta bles  is  dep e nd e d  on   how  t he  sta ff   m anag em e nt  is  m anag in g  th e   inf or m at ion   an d  set   of  data  i n  e ver y  e ducat ion al   in sti tuti on   resp ect iv el y.  Re gardin g  t he   tim et ables  pro blem ,  the  su r vey  on  the  pr evi ou s  researc h   co ncl ud e d  as  non - de te rm inist ic   p olyno m ia l - time  har d  ( NP - ha rd)  [1 ] .     The  e xam inatio n  tim et abling  pro blem   is  kn ow n  as  (ET P)   that  a rises   arou nd  the  world  w hich  i nvolv e s   edu cat io nal  ins ti tuti on s  wh et he r  sch oo ls,  c olleges  or  un i versi ty .  Ba sed  on   the  real - li fe  ex a m inati on   tim e ta ble  so lvi ng  the  sc hedulin g  pro ble m   fo r   the   hi gh  e du cat i on al   i ns ti tuti on s   are   m or e  com plicated  tha n  t he  sc hool.     It  app e ars  that   the  pro blem   o f  exam inati on   tim e ta bling   is  to  al locat e  exa m inati on   into  a  lim it ed  nu m ber   of  tim esl ot  and   wh il e  the  sat isfyi ng  ad diti onal   co ns trai nts .  Ty pical ly ,  the  e xam inati o n  ti m e ta ble  pro ble m   involves  tw o  ty pes  of   ha rd  and   soft  const raints  that  need   to  be  sat isfie d  in  orde r   to  pr od uce  f easi ble     tim e ta ble  [2 ] .   A  c onflic t  bet ween  tw o  or  m or e   exam inati on s  assi gns  in t o  lim i te d  tim eslo t  cau sin g  diff i culti es   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2502 - 4752   Ind on esi a n  J  E le c Eng &  Co m p  Sci,   Vo l.   13 , N o.   1 ,  Ja nu a ry 20 19   :   1 9 1   –   198   192   a m on g  the  st udents .  P rev i ous  resea rch e rs  ha ve  s uggeste d  a  so luti on   w he re  a  pen al ty   is  giv e n  wh e n  t he re  are   ci rcu m sta nces  that  vio la ti on  of   c onflic t  on   two  or  m or e  exam inati on s  is  assigne d  a t  the  sam e  t i m e  an d    day  [3] .  To  m e asur e  the  gap   a nd   ide ntify  the  avail abili ty   of   fr ee  am ou nt  of  tim e,  sp read i ng  the  pa per   m uch   as  po s sible  ov e r  exam inati on   durati on  c ould  pro vid e  e noug h  ti m e  fo r  preparati on  a nd   stud y  t hat  le ads  t o  increase t he  s uc cess of t he  stu den t.   Su r vey  on  the  li te ratur e,  m os t  of   the  c onstrai nts  an d  pr ob le m s   wer e  stu died  an d  s olv e d  by   pr evi ous   researc hers  us i ng   var i ous  ty pes  of   the  a ppr oa ch  pro pose d.   So m e  Gen et ic   al gorithm s  hav e  been   us e d  to  so lve   popula t ion   of   a  chrom os om e   wh ic h  is  re pr e sented  as  a  so l ution   f or   fin din g  t he  feasi ble   tim et able.  The  cro s s - ov e r  operat or   t ends  to   fi nd  sui ta ble  an d  pro duce  a n  a ppr opr ia te   resu lt   for  nex t  popula ti on  wh ic h  de pends  on   bo t h  par e nts  a nd  c hild  [4 – 6] .  Heurist ic   so l ution   pa rtic ularl y  pro ved   that  t his  kind  of  m eth od  pro vid e s  s olu ti on   exam inati on   ti m e  ta bling   by  deali ng  the  c onstrai nts  e ve n  t hough  not  gua r antee  not  op ti m al   and   perfec t  [7 ,   8].  A  he uri sti c  order i ng   is  us e d  to  exam inati on  tim et abling  prob le m   by  com par i ng   five  dif fer e nt  strat egie s   an d  evaluate  t he  be st  res ult  [ 9].   Com bin at ion  of  Genet ic   and  He uri sti c  al so   a re  gr eat   strat egies  wh i ch  c a n  ov e rc om e  diffi culti es  by  m a xim iz es  the  al locat ion   a nd  m ini m iz e  as  m uch   as  possi ble  the  vio la ti on s   of   const raint  in   de te rm ining   t he  best  s olu ti on for   ti m et abling  pro blem   [10] . A   Co ns tr uctive   he ur ist ic   is prese nted   for  so l ving  U niv e rsiti   Ma laysia   Pahang  exam inati on   ti m et abling  by   produce  a  good  qu al it y  so luti on   com par ed  t o  e xisti ng  softwa r e  syst e m   [11] .  The   rece nt  s urvey  al s o  fou nd  that  m e m et i c  al gorithm   wh ic h  is   m et aheu risti c  appr oach es   ha ve  be en  c onstructe d  f or   dea ls  exclusi vely   with  fi xed  le ng t h  ti m e ta bles  [12] .    Othe r  exam inati on   tim et abling  pro blem   a lso  ha ve  bee n  s olv e d  by  the  pr e vious  w ork   with  m et aheurist i c   appr oach es   suc h  as  Ta bu  Se arch   (TS),  GR AS P  (G),  G re at   Delu ge  ( G D)   a nd  et c.  [13 – 15] .  Th e  ev al ua ti on  perform ance  of   exam inati on   tim e ta ble  has  been   c om par ed  with  ot her   va riances  of  A CO  an d  ap pro ach  that   has  been   pro po s ed  of  Ma x - m in  ant  syst e m   (MM AS )   to  dete rm ine   the  feasi ble  so luti on  a nd   bette r     resu lt   [16, 1 7] .   AN C OTT  pro gr am   us ed  tw o  so luti ons  wh i ch  are  a nt  ra nk - base d  syst em   fr om   ACO  var ia nce  wit h  heurist ic   orde ri ng  to d et erm ine  the  lo west nu m ber   of  soft  co ns trai nts   an d  re du ci ng  the  am ount o f   no n - fe asi ble   tim e ta bles  [9,  17 ] .   A  hybri d  ant  col on y  al gorithm   and   a   c om plete   local   search   with   m e m or y  he ur ist i c  wer e  us e d  f or   s olv i ng   ti m esl ot  pr ob le m s  on   the   exam inati on   tim e ta ble  that  stud e nts  assi gn e d  m or e  th an  one   exam inati on   si m ultaneou sly   and   m axim iz e  the  a vaila ble  tim e slot  betwee n  two  co ns e cutive    exam inati on s  [ 18 ] .   In   this  researc h  pa per,  the  id ea  of   the  stu dy  is  to  sat isfy  al l  the  con st raint s  and   pro vid e  a  pr io rity   to   assign  e xam   e ven ts  i nto   a  ti m et able.  Ther e fore,  the  m a in  obj ect ive  of   t his  stud y  is  to  ba la nce  the  distribu t i on   of   ti m et able  sl ots  an d  st ud e nt   exam inati on   assignm ent.  We  pr e sente d  wi th  an  al gorith m   so luti on   w hi ch  is   base d  on  AC O  co nce pt  of   real - li fe  ant ’ s  behavi or   to   so lve  our  e xam inati on   tim et abling  for  Un iS ZA.    This  al go rithm   is  i m ple m ented  int o  the   syst e m   wh ere   th e  res ult  will   be   com par ed   an d  te ste d  with  sever a l   dataset s  to   ana ly ze  the  ef fecti ven ess   an d  fl exibili ty   of   ex a m inati on   ti m et able.  T his  pa per  is  prese nte d  a nd  orga nized  i nto   sever al   sect ions.  I n  t he   sec on d  sect io n,  an   e xp la nation  a bout  exam inati on  tim et abling  pr ob le m   and   discussi on  on  U niSZ A   exam inati on   tim e ta bling   pr ob le m   with  detai ls  of   con s trai nts.  A  s um m ar y  descr i bes  the   def i niti on   of   t he  prob le m   in  the  thir d  sect ion .   I n  the  f ourt h  sect io n,   t he  p r opos e d  m et ho d  appr oach,  AC O  is  ex plained .   The  ex pe rim e ntal  resu lt s  are includ e d  in  t he   fifth  sect io n  a nd   sect io n  si xth   is  the  final r e su lt  ac hi eved .  T he  la st  sect ion   pr e sent ed ov e rall  conc lusio ns  a nd fut ur e  work.       2.   AN T  COL ONY O PTIMIZ A TION  (ACO )   The  AC O  is   a  fam il y  of   m et aheu risti c  that  can  be  use d  to  so l ve  the  discrete  optim isa ti on    pro blem   [19] .  An t  Syst em   (A S)   is  t he  ea rlie st  al gorithm   of  ACO   that  has   bee n  pro po se d  by  D ori go  et .   a l  in   1991  for  so l vin g  tra velin g  sal es m an  pr obl e m   (TSP )  [20] .   Then,  this  A CO  evo l ved   a f te r  a  few   ye ars  with  e m erg ence  tw o  va riants  of  An t  Col on y  S yst e m   (A CS)  and   the  MM A S.  I n  rece nt  ye ars,   m any  research e r s   hav e   bee n  co ncen t rated  on   this  ACO  a lgorit hm   that  ap plied  s ucc essfu l ly   on  their  var i ous  discret e   op ti m isa t ion   pro blem   and   ot her   com bin at ori al   pr oble m s  s uch   as  the  Q ua dr at ic   Assign m ent  Pr ob le m   (QAP ),  Veh ic le  R ou ti ng P roblem  ( VR P) , G raph C olorin g  P roblem  ( GCP), a nd Job Sche du li ng  Pro blem  ( JSP)   [ 20] .    ACO  al gorith m   is  insp ired  by  trai l  la yi ng   for  f or a gi ng   and   f ollow s   th e  highest  co nc entrati on  of   ph e r om on es  in   est ablishin g  t he  s hortest   pa th.  He nce ,  the   pro bab il it y  of  us in g  s horter   paths  from   nest  to   resou rce  de pe nds  on   t he  hi gh  a m ou nt  of   phe ro m on e.  To  de scribe  t he  ste ps  of   AC O  al go rithm ,  an  exa m ple  of  AS   for  T SP  a s  sh owe d  i n  Fi gure  1 an d  t hr ee  levels  op e rati on  for  e xecu te  t he  c on ce pt  of a nt b e ha vior.        Evaluation Warning : The document was created with Spire.PDF for Python.
Ind on esi a n  J  E le c Eng &  Co m p  Sci     IS S N:  25 02 - 4752       An a nt co l on y   algorit hm for  universi ti  su lt an  za i na l  abidin   exam i na ti on…   ( Ahmad Fird aus K ha ir )   193       Figure  1 .  A C O   al gorithm       To  i niti al iz e  all  the  phe ro m on es  trai ls,  t he  first  le vel  oper at ion   is  t o  pla ce  ant  rand oml y  on   node   i   with info rm a t i on  th at  creates t he  so luti on.   T hen, an t m ov es  thr ou gh  th e no de  to no de  fro m  it s  starti ng  point of   node  i .  A t  no de   i,   by  us i ng  tr ansiti on  pr o ba bili ty ,  the  ant  v  will   deci de  th e  node  w hic h  ha s  not been visi te d  ye t  for next  node   j .  Th e  for m ula of tra ns it ion p robab il it y ru le s  desc ribe  a s foll ows:      ( ) =   (  ( ) )   . (  ) ∑   (  ( ) ) . (  ) 1    if    j ∈   (1)     -   Set of n odes  ant  v   wh ic h  is  at  the stat e no de   i     -     Am ou nt  of   pher om on e    -    ( )   Ph er om on e tr ai l i ntensity  that li nk   node   i   to  j .    -    = 1 /     Visibil it y(he ur ist ic  in form ation ) desi re  for  c hoosi ng c losest n ode  j   w hen at n ode   i ,    -   α  a nd β  par a m et er to  d et e r m ine the in flue nce  factor t he   ph e r om on e an d visi bili ty .    The  seco nd  le vel  op e rati on  is  search  so l ution   that  is  op t ion al   if  the  an t  find s  the  be st  so luti on .     The  phe ro m one  trai ls  update  is  the  la st  le vel  of   oper at ion  ACO  al gorith m .  Ther e  are  ci rcu m sta nces  in  A S   wh e re  the  co nst ant  ph e ro m one  trai ls  are  evap orat ed  to  le t  the  ants  la y  down   ph e r om on e  after  com pletio n  of  it s tou r . T he fo rm ula is d efine d  a nd d e scribe   as foll ows:        ( t )   = (1   -   ).     ( t  -   1) +  ∑ ∆    = 1   (2)       (3)     m  nu m ber   of a nts   ( 1 − )  e vapor at io n r at e w he re    is c on sta nt   ∆      am ou nt of  phe ro m on e lai d by  an t a nt  v . o n  t he  e dg e   i   an d  j   Q  c on sta nt stat e an d  is t he  le ngth  of a t our  th at  an t  v     ( t )   t he  le ngt h of a to ur that a nt        3.   PROP OSE  A CO APP ROA CH FO R  O U R   UETP   In  this  sect io n,  we   bri efly   e xp la ine d  t he  f low  proces s  f or  m anag ing  the  Un iS ZA ’s  exam inati on  tim e ta bling   pr ob le m   with  the  representat iv e  so luti on  an d  pro pose d  a ppr oach.  The  ACO  al go rith m   and  heurist ic   is  util iz ed  UE TP  t o  f ind   t he  s olu ti on  to  t he  heur ist ic   inform at ion   and  pher om one  trai ls  for  a  fe asi ble   so luti on.  T he  go al   is  to  ac hieve  best  a vaila ble  tim e  slot   assignm ent  fo r  st ud e nts  by   m axi m isi ng   the  ga p  betwee n  tw o o r  m or e co ns ec ut ive ex am inatio ns a nd o t her   r espected  constr ai nts.     3.1.    Re presen tativ e  So lu tio n   We  pr ese nte d  the  e xam ple  of  tim esl ot  ind ic es  on  U niS ZA  e xam inatio n  wee k  f or  our  s olu ti on.   Dep e nd  on  ea ch  sem est er,  the  nu m ber   of  days  a nd   ti m e slots  can   be   di ff ere nt  f or  th e  exam inati on  wee k.    Fo r  e xam ple,  3 - wee k  exam i nation  per i od   in  this  se m est er  an d  for  the   nex t  exam inati on   m a y  be  diff ere nt   wh et her   week   or   2 - weeks.  Sa m e  go es  to  tim esl ot,  if  two  ti m esl ots  in  a  day,  m eans  that  t wo   in dices  tim esl ots.   So   f or  exam ple,  with  3 - wee k  exam inati on  per i od   has  45  tim esl ots.  The  total   of  45   tim esl ots  ind ic es   is  A C O  A l gori t hm s                   - I ni t i a l i z e   phero m o ne tra i l s                 - D o   wh i l e   ( S t op   c ond i t i o n/ i f   c ri t e ri a   a re   not sa t i s f i e d) - l oop                           Ge n e r a t e   s o lut ion                           L o c a l   S e a r c h   s o lut ion                           U p d a t e   p h e r o m o n e   t r a il s                 - E nd   D o                 - E nd       ∆     (t)  =  {Q /     ( t )       i f  ( i ,  j )  ∈     ( t )                                0                i f  ( i ,  j )  ∉     ( t )   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2502 - 4752   Ind on esi a n  J  E le c Eng &  Co m p  Sci,   Vo l.   13 , N o.   1 ,  Ja nu a ry 20 19   :   1 9 1   –   198   194   represe nted  as  15   days  with out  ta king  wee ke nds  (S at urday  and   S unday )  because   there  are  no  exam s  are  hel d  and in eac h da y has  3  ti m esl o ts (m or ning,  af te rnoon, eve ni ng).           Figure  2 .  Tim e slot  in dices       Ba sed  on  re pre sent  in dices  ti m esl ot  in  Fig ure  2,   t he  ti m eslo t  num ber   1,   2  an d  3  a re  de note d  a s  day   on e ,  ti m esl ot  nu m ber   4,5  an d  6  i nd ic at e  as   day  2,  the n  f ollow e d  by  a nothe r  ti m esl ot  nu m ber   t o  de note   as   ano t her   day.  T his  ind e xing  ti m esl ot  is  rep re sented  to  pro vi de  an d  fi nd   a   s uitable   tim esl ot  fo r  th e  stu dent s  if  a  sit uation  t hat they di d no t  ha ve gap - f ree ti m e.    In   Table  1,   an   exam ple  of   r oo m   for  the  e xam inati on   ha s  bee n  a pp li ed   to  a  data  set   and  with   th e   detai ls  of  it s  ca pacit ie s.  A   pro cess  of  he ur ist ic   is  searc hing  f or  the  pro per  r oo m   to  be   ch ose n  for  e xam inati on  base d  on  the  r oo m   detai ls.  The  exam inati on   m us t  assign  into  a  room   bu t  if  it   is  nece ssary,  m ulti ple   of   a  room (g r ouping )  can  be  util ized   as  lo ng  the   exam inati on   is  nearby  to  ea ch  ot her   a nd  capaci ty   sh oul d  be   enou gh  t o  fit  the  nu m ber   of   s tud e nts.  Dista nc e  m a trix  valu e  betwee n  roo m   is  al so   giv e n  as  sho wn   i n  T able  1.   In   a  pa rtic ular   case,  there  is  an  exam inati on   that  needs  to   us e  m or e  than  one  r oo m   to  facil it at e   capaci ty   of   stud e nts.  T he r efore,  a   r oo m   gro up i ng  is  pro vid e d  by  c om bin ing   with   oth e r  room   t o  create   a   ne w  total   capaci ty   sh ow n  in  Ta ble  2.  To  facil it at e  the  room   capaci t y,  an  ar rangem ent  f or   the  r oom   gr ou ping  is  so rt e d  decr easi ng ly   from   la rg e  to   s m al l  siz e.  If   t he   r oo m   gro up i ng  ha s  been  ta ken  by   an   ex a m inati on   f r o m   the  li st,  the  oth e r  exam inati on   with  a  la rg e  ca pacit y  stud e nt  can  be  assigne d  to  a ny   su it able  roo m   gr oup  acc or ding  to   the  so rti ng   ca pa ci ty .  It  is  nec essary  to  orga nize  the  exam i nations  for  the   la rg e  stu den t  with  a  pr i or it y  so   that   durin g  the  assi gn at io n  f or   c hoos i ng  a  room   will   be  well   arr a ng e d  f or   t he  ne xt  exam i nation  to  fit  into  the   fo ll owin g  cap aci ty   of   the  ro om .  No te   th at ,  the  value  of   in form at ion   can  be  cha nged  dep e ndin g  on   the   op e rati ons th at  involve d       Table  1 . R oo m  D et ai ls  an d Di sta nce  Value  Ma trix   Ro o m   Grou p   Ro o m   Cap acity   DKU   AC2 1   AC1 9   AC2 0   AC2 3   FBIM   DKU   200   -   -   -   -   -   FIC   AC2 1   120   -   -   2   1   2   FIC   AC1 9   95   -   2   -   1   3   FIC   AC2 0   80   -   1   1   -   3   FIC   AC2 2   70   -   2   2   3   -       Table  2 .  R oo m  G r oupi ng  Detai ls   Ro o m   Grou p in g   New  Total Cap acit y   Exa m in atio n  Split  Valu e   (AC1 9 ,AC2 0 ,AC2 1 ,AC2 2 )   565   3   (AC1 9 ,AC2 0 ,AC2 1 )   495   2   (AC1 9 ,AC2 0 )   200   1   (AC2 1 ,AC2 2 )   190   1   (AC1 9 ,AC2 0 )   175   1       3.2.    A nt   St r ategies  Moveme nt   In  ord er   to  de m on strat e  the  ACO   oper at io n  for  t he  e xam inati on   assig nm ent,  we   pr ov i de  a n  e xam ple  m at rix  so l ution  f or   ti m esl ot  and  e xam inati on   as   sho wn  in   Table  3.   The n,  a  sam ple  of  7  exam inati on   da ta set s  and  set   of  num ber   stud e nts  ta ken   a n  e xa m   is  pr ovide d  to  sho w  the   ant  syst em   it e rati on   proces s   wh ic h  pr ese nted  in T able 4.       Table  3 .   Ma tri x  S olu ti on  of T i m esl ots an d E xam s   T i m eslo t   Exa m     E1     E2     ….       ….     E30   1                                                2             ……             45             ( 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,1 0 ,1 1 ,1 2 ,1 3 ,1 4 ,1 5 ,2 0 ,2 2 ,2 3 ,2 4 ,2 5 ,2 6 ,2 7 ,2 8 ,2 9 ,3 0 ,3 1 ,3 2 ,3 3 ,3 4 ,3 5 ,3 6 ,4 3 ,4 4 ,  4 5 ,4 6 ,4 7 ,4 8 ,4 9 ,5 0 ,5 1 ,5 2 ,5 3 ,5 4 ,5 5 ,5 6 ,5 7 )     Evaluation Warning : The document was created with Spire.PDF for Python.
Ind on esi a n  J  E le c Eng &  Co m p  Sci     IS S N:  25 02 - 4752       An a nt co l on y   algorit hm for  universi ti  su lt an  za i na l  abidin   exam i na ti on…   ( Ahmad Fird aus K ha ir )   195   Table  4 .   E xam ple of  7 Sam pl e Ex am s an d S tud e nts    Stu d en t  Grou p   Exa m s   {S1 ,S2,S3 ,S4,S5 }   E1   {S6 ,S7,S8 }   E2   {S6 ,S7,S8 }   E14   {S3 ,S4}   E17   {S1 ,S2}   E16   {S1 ,S2}   E19   {S5 }   E30       The  T a ble  5  dem on strat ed  the  first  sta ge   of  ant  proces s  to  init ia li ze  the  init ia l  sta te   rand om l y  assigne d  t he  a nt   v  is  at   the  firs t  node   i  in  orde r  to   pr ov i de  th e  tim esl ot  and  exam s  into  pr oper   day  a nd  se ssion.   As  ex plaine d  on   t he  re pr ese ntati ve  so l utio n,   D1   is  ass um ed  as  the  fir st  day  of   the  week   c onsist s  of   th ree   tim esl ots ( each  d ay   has  t hr ee t i m esl ots).       Table  5 .   In it ia l Sta te  Ran do m  A ssig n o n  Ma t rix   Date                      Sess io n   1   2   3   D1   (E 1 ,T 1 )       D2     (E 2 ,T 5 )     D3         D4         D5             Ba sed on  t he p rev i ou s  secti on on  ACO  e xpla nation,  prob a bi li ty  so luti on   rul e is used to  de te rm ine the   node   w hich   is  no t   visit ed   ye t  by  a nt  v   w hich   init ia ll y  was  pl aced  on  node  i   exam inati on   will   fin d  oth e r  node   j  exam inati on .  T he  perf or m ance  of  a nt  v   play ed   a n  im po rta nt   ro le   on  t he  he ur ist ic   a nd  phe ro m on e  i nfor m at ion   on  the  e dge,  w her e   the  pro ba bili ty   pr efe rence   of  ti m esl ot  exam inati on   node   j  f or  the  c urren t  node   i   de pends   on  it .  T able  6  sho wed  the  t i m esl ots  and  exam s  that  ha ve  been  assi gned   s uitable   da y  aft er  ta king  the   pro bab il ist ic  sol ution ,  and t he c onflic t co ns tr ai nts in  eac h  e xam inati on  are  conside red.       Table  6 .   Assi gn  Af te r   P roba bi li sti c So luti on   Date                      Sess io n   1   2   3   D1   (E 1 ,T 1 )       D2     (E 2 ,T 5 )     D3   (E 1 9 ,T 7 )     (E 3 0 ,T 9 )   D4         D5     (E 1 4 ,T 1 4 )         3. 3 .    Heuris tics   The  ACO  a ppr oach  for   e xam i nation  ti m et abl ing  p r oble m   is  su pp or te d  with   a  heurist ic   m e thod  w he re   ta kin g  the   Lar gest  degree  a nd  La r ge st  E nroll m ent  into  a ccount.  This   he ur ist ic   is  util i zed  to   s peed  up  th e   process   of  fi nding  a   sat isfact or y   so l utio n  e ven  t hough  the   possi bili ti es  to  a chie ve  opti m al   so luti on   does   no t   gu a ra ntee but e nough t o p rovi de  a  res ult.  T he  d esc riptio n o f  the  m et ho d  is  d esc ribing a s foll ows:   LD: E xam  is assign e d first i n t he  sc hedule if   the ex am  h as  t he  m os t co nf li ct s w it h othe r  e xam s.   LE: Exam  w it h l ar ge  enrollm e nt stu de nts is  gi ven   pri or it y t o assi gn ea rlie r .     3. 4 .    Pher om one U pd at e   A   f or m ula  is  giv e n  t o  i nter pr et e   the   be st  it erati on  acc ordin g  to   the   up dated   m at r ix  value   o f   ph e r om on e  trai ls.  He nce,  t o  ge t  the  str ong  c on ce ntrati on  of  the  ph e ro m one  trai ls,  ad diti onal   so m e  a m ou nt  of   value  will   pro vid e  res ult  whet her   the   best  so luti on  ca n  be   obta ined  bas ed  on   t he  ph e r om on e  up date  ru le s .     A   ne w  am ou nt   of   ph e ro m on e   is  updated  when  the  a nt  has  been   m ov e d  to   al l  exa m   that  al read y  assig ne d  to   each ti m esl ot o n  the  tim et able:     ∆      (t) =  {Q /    ( t )             if ( i, j )  ∈     ( t )                                0                             if ( i,   j )  ∉     ( t )     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2502 - 4752   Ind on esi a n  J  E le c Eng &  Co m p  Sci,   Vo l.   13 , N o.   1 ,  Ja nu a ry 20 19   :   1 9 1   –   198   196   In  orde r  t o  m ake  s ure  that   the  un li m i te d  inf or m at ion   pher om on e  at   t he  e nd  proces s  of  t he  ACO   al gorithm , th e ru le s  of  ph e rom on e evapo rati on   proces s is a pp li ed  to u pdat e an d  c om pu te   the trail s:        (t)  = (1   -   ).     ( t  -   1)  +  ∑ ∆    = 1       4.   E X PERI MEN TAL RES UL T   The  propose d  ACO  a ppr oach  is  execu te d   in   our  sim ulati on   ex pe rim ent  fo r  m aking   a n  ob s er vatio n  and  ide ntify  m os t  op ti m al   resu lt   pe rfor m ance  pro duced   by   data  set .   T he  al gorithm s  were  i m ple m ented  an d  cod e d  i n  a  we b - base d  c om pu te r  syst em   on  W in dows   10  with  s upporte d  by  CP U  I ntel  Core   i5 - 5200 U  2.20   GH z  a nd  4.0 0GB  RAM.  We   wer e  al s o  usi ng   e xam ples  of  real  dataset   wh ic h  are  a ppli ed  to  the  sim ulati on   pro gr am   syst e m .  The  six  of  te st  case  datase t  instances  are  pr ese nted   ba se d  on  fi ve  detai ls  of  e xam s,  stud ent s ,   enroll ed,   ti m es lots  an d  pri ori ty   as  show n  in   Table  7.  All  da ta set   is  com p uted  acc ordin g  to  each  num ber   of   exp e rim ent sim ula ti on  that c onduct ed  t o  c om par e each  res ult t hat has  bee n ob ta ine d by t he  syst em .       Table  7 .  T he  F IC D at aset s   Exp Nu m   Test Case   Exa m s   Stu d en ts   Enro lled   Ti m eslo ts   Priority   1   FIC3 0 _ A   30   460   1416   45   Y   2   F1 C3 0 _ B   30   460   1416   30   Y   3   FIC3 0 _ C   15   407   1058   30   Y   4   FIC3 0 _ A   30   460   1416   45   N   5   FIC3 0 _ B   30   460   1416   30   N   6   FIC3 0 _ C   15   407   1058   30   N       4 . 1 .      Discussi on   on Te st C ase   A  pr i or it y  is  gi ven  on  fe w  of   the  te st  case  t o  determ ine  exa m inati on   assi gned   f or  the   la r ge  st ud e nt’s  capaci ty   or   la rg e  e nrollm e nt  of   e xam inati on   (LE )  a nd   to  be  sc he du le d  earli er   into  the  tim esl ots.    The  e xp e rim e nt  has  bee n  ca rr ie d  out  on  the  exam inati on   t i m et abling  that  app li e d  w it h  ACO  a ppr oach   t o  com pu te   the  e xam inati on   ti m et able  resu lt   with  t he  te st  case  inf orm ati on  that  has  prov i ded  in  t he  pr e viou s   sect ion .   The   r esult  of  the   te st  case  in  Ta bl e  8  i nd ic at es  t hat  FI C 30_A 1  w hich  is  t he  pr i or it y  giv e n  has  t he   lowest  value   0.96  of  sta nda rd  de viati on  a nd  F IC30_B 5  w hich   is  not   giv e n  a  pr i ori ty   pr od uced  0.78  of  sta nd a rd  de via ti on .  B oth  res ul ts  def ine d  t hat  the  e xam inatio n  was   sc hedu le d  ine ff ic ie ntl y  and  pro vide   good  resu lt   rather t ha n othe r  te st ca se r es ult f or  th e d ist rib utio ns   of exam inati on ev e nt in  t he  ti m et able.       Table  8 .   T est   Ca se Result   o n FIC  Data Set  I ns ta nces   Test Case   Den sity  Co n f lict ( %)   Mean   Var.   St.dev   FIC3 0 _ A1   2 .12 %   1 .61   0 .92   0 .96   FIC3 0 _ B2   2 .12 %   1 .91   0 .98   0 .99   FIC1 5 _ C3   1 .42 %   2 .43   2 .94   1 .71   FIC3 0 _ A4   2 .12 %   2 .00   1 .17   1 .36   FIC3 0 _ B5   2 .12 %   1 .89   0 .61   0 .78   FIC1 5 _ C6   1 .42 %   2 .62   1 .90   1 .38       4 . 2 .      Result   In  T a ble  9,  the   fi nal  res ults  of  t he   FI C  assi gnm ent  exa m inati on   tim et ablin g  wer e  a uto - gen e rated  t o  su it   the   rele va nt  ti m e  slots  and  c om pu te d  by   co ns ide rin g  al l  pro blem s  a nd  s olu ti ons.   T he  res ult  al so  pro vid e s   m axi m u m   separ at ion   for  the   consecuti ve  e xam s  and   exa m inati on   that  has  been   giv e n  pr i or it y  was  a ssign e d  earli er  int o  su it able  ti m esl ots.  T o  dep ic t  e xa m ples  of   t he  da ta   ex am inati on   t hat h as b ee n  assig ne d,  inf orm ation   on stu de nt take s ex am inati on   E1, E3 , E 16, a nd E 19 tim e slots as s how n  i n  T able  10.                   Evaluation Warning : The document was created with Spire.PDF for Python.
Ind on esi a n  J  E le c Eng &  Co m p  Sci     IS S N:  25 02 - 4752       An a nt co l on y   algorit hm for  universi ti  su lt an  za i na l  abidin   exam i na ti on…   ( Ahmad Fird aus K ha ir )   197   Table  9.  E xam i nation Ti m et ab le  Result  of FI C   T i m es l o t s                                       E x am s   E1   E2   E3   E4   E5   E6   E7   E8   E9   E 1 0   E 1 1   E 1 2   E 1 3   E 1 4   E 1 5   E 1 6   E 1 7   E 1 8   E 1 9   …   E 3 2   E 3 3   T1                                                 T2                                               T3                                               T4                                               T5                                               T6                                               T7                                               T8                                               T9                                               T 1 0                                               T 1 1                                               T 1 2                                               T 1 3                                               T 1 4                                               T 1 5                                               T 2 0                                               T 2 2                                               T 2 3                                               T 2 4                                               T 2 5                                               T 2 6                                               T 2 7                                               T 2 8                                               T 2 9                                               …                                               …                                               T 5 7                                                   Table  9 .   E xam ples  of   Stu den t  Ex am inati on   Assignm ent   Ti m eslo t   T7   T2   T14   T22   Exa m in atio n s   E1   E3   E16   E19       5.   CONCL US I O N   In   t his  pa pe r,   i t  can  be  co ncl ud e d  t hat  the  i m ple m entat ion   of  AC O  al go r it h m   su ccessf ul ly   ob ta ined   and  s olv e d  t he   real  pr act ic al   exam inati on   t i m et abling  pr oble m s  faced  by   the  F IC,  U ni SZA .   Alth ough  t he   pr ese nted  res ult  do es  no t  gu a ran te e  the  best   scenari o,   at   le ast   the  auto - ge ner at e d  proce s sing   is  m uch   be tt er   than  m anu al ly   process   f or  the   feasible   so l ution  on  our   UTi m e .  It  is  prov e d  that   the  a ppr oach  ca n  ob ta i n  good   resu lt s d e pend s  on h ow  t he  operati on  as so ci at ed  with   the proble m .  Be sides,  the p e rfor m ance  ca n  be  im pr ove d  and   e nh a nce d  by  cal ibrati ng   on   the  s olu ti on .  Ther e f or e,  further   te sti ng  an d  analy zi ng  of   this  resear c h  w il l  be  able  to   ens ure  the  est ablis hme nt  of  t he  a ppr oach  w hich   helps  res olv e  oth e r  var ia nts   of  e ducat ion al   insti tuti on   exam inati on  ti m et abling wit h t he diffe re nt requ i rem ent an d  s pecifica ti on  for  the  futu re.       ACKN OWLE DGE MENTS     This  wor k  is  pa rtia ll y su pport ed by U niSZ A (G ran t R R 008 C RIM/ 2016).       REFERE NCE S    [1]   M.  Doulaty ,   M.   R.   F.   Dera khsh i,   and  M.  Abdi .   Timetabl ing:   A   Stat e - of - th e - Art   Ev olu ti onary   A pproach.   Int .   J.  Mac h.   Learn .   C omput.   2013;   3( 3):  255 – 258.   [2]   W .   K.  Ho,  A.  Li m ,   and  W .   C.   O on.   Max imizing  Pape r  Spread  in  Ex aminati on  Ti metabl ing  using  a  Ve hic l e  Routin g   Me thod.  2001:   3 59 – 366.   [3]   A y ob,   M.,  Abdulla h ,   S. ,   &   Malik,  A.   A  Pract i ca l  E xaminat ion   Ti metabl ing   Probl em  at  the   Uni ver siti   Kebangsaa n  Malay sia .  Int ernati onal Journal of  Computer  S cienc e   and  N et wor k  Se curit y .   20 07;   7(9):  198 – 204 .   [4]   M.  Golub  and  D.   Jakobovi.  E xam  Timetabl i ng  Us i ng  Gene t ic A lgo rithm .   2009:   357 – 362.   [5]   S.  K.  Jha .   Ex am  Timetabl ing   Pro ble m using  G enetic A lgori thm .  In t.   J. Res. Eng. Te chnol .   2014;   3(4 ):  649 – 654, .   [6]   W .   Erbe n  and  P.  Y.  Song.  A  Hybrid  Gr ouping  Gene tic  Al gor it hm  for  E xami nati on  Timetab ling  2  The  Hybri d   Gr ouping  Gene tic  A lgorit hm .   200 4.   [7]   Z.   Fu  and  A .   L i m .   Heuristic s  for t he   e xam  sche d uli ng  probl em .  2 000:  172 – 175.   [8]   A.  O.  Adewum i,   B.   A.  Saw y err ,   and  M.   Montaz  Ali.   A  Heurist ic   Solut ion  to  the   Unive rs it y  Time t abli ng  Proble m .  Eng.   Comput .   20 09;  26(8):   972 – 9 84 .   [9]   T.   The pph akor n   and  P.  Pongchar oen,   “ Heuri sti c  orde ring  for  a nt  col on y   base d   ti m et abling  too l, ”  2012 ,   vol.   4,     pp.   87 – 96 .     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2502 - 4752   Ind on esi a n  J  E le c Eng &  Co m p  Sci,   Vo l.   13 , N o.   1 ,  Ja nu a ry 20 19   :   1 9 1   –   198   198   [10]   N.  D.  Tha nh.   Solv ing  Timeta bli ng  Proble m  Us ing  Gene ti c  and  Heuristic   Al gorithms .  AC IS  Inte rnational   Confe renc e  on  Soft ware  Eng in ee ring,   Artificia l  Intelli g ence,   Net working ,   an d  Parall e l/ Distr ibut ed  Comput i ng   ( SNPD  2007) ,   2007;  3:   472 – 477.   [11]   M.  N.  M.   Kah ar  and   G.  Ken dal l .   The  Ex am inat ion  Time tab li ng  Probl em  A t  Univ ersiti   Ma lay sia  P ahang:   Compar ison  of  a  Constr uct ive  Heuristic   wit h  an  Ex isti ng  S oftw are  Solut ion .  Eur.   J.  Oper.  R es.   2010;  207(2 ):    557 – 565.   [12]   E.   K.  Burke,   J.   P.  Newal l,   and   R.   F.  W ea re.   A  Me metic  Al go ri thm  for  Unive rs it y  Ex am  Timetabl ing   Springe r,   Berl in ,   He ide lb e rg,   1996:   241 – 2 50.   [13]   L.   Di   Gaspero   a nd  A.  Sch ae rf .   T abu  Searc h  T ec h nique s for Exam inat ion  Tim et abl ing .   2001 ;  2079   LNCS: 104 – 117.   [14]   S.  Case y   and  J.   Thomps on.   GRA SPi ng  the   Ex am inat ion  S che du ling  Proble m .   Spr inge r,  Ber li n,   H ei de lbe rg,  2003:  232 – 244.   [ 15]   H.  T.   à and  S.   Abdulla h.   An  Inte gra te d  H y bri d  Approac h  To  The   Ex aminat io n  Ti m et ab li ng  P roble m .   Om ega .  2011;  39(6):   598 – 607.   [16]   A.R. Mirzaei   and   F.Dja nnaty .   En hanci ng  Max - Mi n  Ant   Syste m  for  Ex aminati on  Ti metabl ing  Probl ems .  Int.   J .   Sof t   Comput.   2008:   2 30 – 238.   [17]   M.  Ele y .   Ant  Algor it hms   for  the  Ex am  Time tabling  Probl em .  Pr act .   Theory  Autom .   Timetabling   VI .   2006;   3867 :    167 – 180.   [18]   R.   Abounac er ,   J.  Boukac hour,   B . Dkhiss i,   A.  E l  Hila li   Al aoui .   A  Hybrid  Ant   Colony   Al gorith m  for  The  Ex am  Timetabl ing   Pro ble m .   2016 ;  12 : 15 - 42.   [19]   Dorigo,   M.,  &  B lum,  C.   Ant   Col ony  Optimizati o n  the ory:  a   Surv ey .  Theoretical  Computer  Sci en ce   2005;   344 (2 – 3) :   243 – 278.   [20]   S.  Katiy a r  and   A.  Q.  Ans ari.  A nt  Colony  Opti mi zation :  A  Tut orial  Revi ew  An t  Colony  Optimi zation :  A  Tutor i a l   Re v ie w .  2015;   7  no.   AU GU ST:  3 5 – 41.     Evaluation Warning : The document was created with Spire.PDF for Python.