I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   10 ,   No .   6 ,  Dece m b er   2 0 2 0 ,   p p .   6 5 5 8 ~6 573   I SS N:  2 0 8 8 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 1 0 i 6 . pp 6 5 5 8 - 6 5 7 3          6558       J o ur na l ho m ep a g e :  h ttp : //ij ec e. ia esco r e. co m/in d ex . p h p /I JE C E   Co urses  t i m e tabli ng  bas ed on hill  cl i m bing  alg o rith m       Abdo ul Rj o ub   Co m p u ter E n g in e e rin g   De p a rtm e n t,   Jo r d a n   U n iv e rsity   o f   S c ien c e   a n d   T e c h n o l o g y ,   Jo rd a n       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Sep   14 ,   2 0 1 9   R ev i s ed   Feb   2 9 ,   2 0 2 0   A cc ep ted   J u n   5 ,  2020       In   a d d it io n   to   it s  m o n o t o n o u s   n a tu re   a n d   e x c e ss iv e   ti m e   re q u irem e n ts,    th e   m a n u a l  sc h o o l   ti m e tab le  sc h e d u li n g   o f ten   lea d s  to   m o re   th a n   o n e   c las s  b e in g   a ss ig n e d   to   th e   sa m e   in stru c to r,   o r  m o re   th a n   o n e   in str u c to r  b e in g   a ss ig n e d   to   t h e   sa m e   c l a ss ro o m   d u ri n g   th e   sa m e   slo t  ti m e ,   o r  e v e n   lea d s  to   e x e rc is e   in   in ten ti o n a l  p a rti a li ti e s  in   f a v o r  o f   a   p a rti c u lar  g ro u p   o f   in stru c to rs .   In   th is  p a p e r,   a n   a u t o m a ted   s c h o o l  ti m e tab le  s c h e d u li n g   is  p re se n ted   to   h e l p   o v e rc o m e   th e   trad it i o n a l   c o n f l icts  in h e re n t  i n   t h e   m a n u a l  sc h e d u li n g   a p p ro a c h .   I n   th is  a p p r o a c h ,   h il l  c li m b in g   a l g o rit h m s  h a v e   b e e n   m o d if ied   to   tran sa c t  h a rd   a n d   s o f t  c o n stra in ts.   S o f t  c o n stra in ts  a re   n o t  e a sy   to   b e   sa ti s f ied   ty p ica ll y ,   b u t  h a rd   c o n stra in ts  a re   o b li g a ted .   T h e   im p lem e n tatio n   o f   th is  tec h n iq u e   h a s  b e e n   su c c e ss f u ll y   e x p e ri m e n ted   in   d if f e r e n t  sc h o o ls  w it h   v a rio u s  k in d s   o f   sid e   c o n stra in ts.   Re su lt s  sh o w   th a t   th e   in it ial  so l u t io n   c a n   b e   im p ro v e d   b y   7 2 %   to w a rd s  th e   o p ti m a l   so lu ti o n   w it h in   th e   f irst  5   se c o n d s  a n d   b y   5 0 %   f ro m   th e   s e c o n d   it e ra ti o n   w h il e   th e   o p ti m a l  so lu ti o n   w il l  b e   a c h iev e d   a f ter   1 5   it e ra ti o n s  e n su rin g   th a t  m o re   th a n   5 0 %   o f   sc ien ti f ic   c o u rse s  w il l  tak e   p lac e   in   th e   e a rl y   slo ts  ti m e   w h il e   m o re   th a n   5 0 %   o f   n o n - sc ien ti f ic  c o u rse s   w il l  tak e   p lac e   d u rin g   th e   late r  ti m e ' s slo ts .   K ey w o r d s :   C o u r s e  s c h ed u le   Har d   an d   s o f t  c o n s tr ai n t s   Hill  c li m b i n g   a lg o r it h m s   Ma n u a l  s c h o o l  t i m etab le   T im e  s lo t   Co p y rig h t  ©   2 0 2 0   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts re se rv e d .   C o r r e s p o nd ing   A uth o r :   A b d o u l Rj o u b ,     C o m p u ter   E n g in ee r i n g   Dep ar t m en t,    J o r d an   Un iv er s it y   o f   Scie n ce   a n d   T ec h n o lo g y ,     Un i v er s it y   C a m p u s ,   I r b id   2 2 1 1 0 ,   P .   O.   B o x .   3 0 3 0 ,   J o r d an .     E m ail:   ab d o u l @ j u s t.e d u . j o       1.   I NT RO D UCT I O N     I n   r ec en t   ti m es,  s ch ed u li n g   o f   ti m etab li n g   [1 ,  2 ]   h as  g a in e d   co n s id er ab le  i m p o r tan c e  an d   h as   w it n e s s ed   r ap id   g r o w t h   d u e  to   its   s i g n if ican t  r o le  i n   t h e  s u cc e s s   o f   s ch o o l  [ 3 ,  4 ] ,   u n i v er s it y   [ 5 ,  6 ]   an d   ex a m in at io n   ti m etab le  p lace m en ts   [ 7 ] .   Giv e n   t h e  d i f f er e n t  c h alle n g e s   f ac in g   ea c h   o f   t h e s e   s ec to r s ,   d esig n i n g   an   ap p r o p r iate  alg o r ith m   f o r   ea ch   w ill  co n tr ib u te  to   s o l v i n g   its   ch a llen g es  s ep ar atel y .   I n   th is   p ap er ,   th e  is s u e   o f   s ch o o l ti m etab le  s c h ed u li n g   is   ad d r ess ed .   Usu al l y ,   a  s c h o o l  ti m etab le  i s   b u ilt  at  t h e  b eg i n n i n g   o f   e ac h   s e m ester   to   o r g an ize  t h e   ac ad em i c   p r o g r am   o f   s t u d y   b y   co n s id er in g   h u g e  a m o u n ts   o f   in f o r m atio n   to   b e  f i lled   in   s u c h   as  co u r s es,  clas s es ,   in s tr u cto r s ,   th e  n u m b er   o f   lec tu r es  f o r   ea ch   co u r s e  t h r o u g h   th e  w ee k   a n d   f in all y ,   t h e  m a x i m u m   n u m b er   o f   h o u r s   t h at  ar e  ass i g n ed   to   ea ch   in s tr u cto r .   T h ese  p ar am eter s   s h o u ld   b e  tak en   i n   co n s id er at io n   w h e n   s o m eo n e   p lan s   to   b u ild   a  ti m etab le  f o r   an y   ac ad e m ic  i n s tit u tio n .   Un f o r tu n atel y ,   en s u r i n g   co m p atib ilit y   o f   th e s e  in p u ts   is   ti m e  co n s u m in g   esp ec iall y   w h e n   d o n e   m a n u all y .   I n   ad d itio n ,   t h e  m a n u al   m eth o d   r eq u ir es  h u m an   la b o r ,   th e  i n s tr u cto r s ’   h elp   s o m eti m es,  w h ich   m ea n s   m o r e  ar r an g e m en t  e f f o r ts ,   m o r e  r eh ea r s als   in   ter m s   o f   w r i tin g   an d   r ev ie w i n g   t h e  r eq u ir ed   p ar am eter s   an d   r esu lti n g   p ar tialit y ,   w h ich ,   i n   tu r n ,   m a y   l ea d   to   p r o b lem s   in   th e  w o r k   e n v ir o n m e n t  [ 8 ] .   T h ese  ch alle n g es  a f f ec t  th e  teac h in g   p r o ce s s   a n d   in s tr u cto r s ’   s cien t if ic  e f f icie n c y   an d   p r o d u ctiv it y .   He n ce ,   th i s   is   t h e  m a in   m o ti v atio n   b eh i n d   th e  p r o p o s ed   tech n iq u e  to   o v er co m e  t h e  m a n u a l   ti m etab le  s c h ed u l in g   an d   h av e   it r ep lace d   b y   an   au to m ated   o n e.   C o u n tles s   ef f o r ts   h av e  b ee n   m ad e  in   t h is   ar ea .   B ased   o n   lo ca l  s ea r ch   tech n iq u es  [ 9 ] ,   th e  p r o ce s s   b eg in s   w it h   s o m e  i n itial  s tat e  th at  i s   cr ea ted   r an d o m l y   o r   r ea d   f r o m   a  f ile  w ith o u t  s atis f y i n g   an y   h ar d   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       C o u r s es ti meta b lin g   b a s ed   o n   h ill climb in g   a lg o r ith m  ( A b d o u l R jo u b )   6559   co n s tr ain ts   [ 1 0 ] .   T h er ef o r e,   th er e  is   a  n ee d   to   s ati s f y   s u c h   co n s tr ai n ts   to   cr ea te  a  co r r ec t sta te  an d   t h en   atte m p t   to   ac h iev e  t h e  s o f t  co n s tr ai n ts   [ 1 1 ] .   Hen ce ,   th is   w o u ld   r eq u ir e  m o r e  o p er atio n s   to   co n v er t  t h e  in co r r ec t   r an d o m   s tate  i n to   an   ac ce p t ab ly   m o r e  co r r ec t  s tate  th at,   in   tu r n ,   r eq u ir es  ad d itio n al   ti m e.   I n   t h i s   n e w  ap p r o ac h ,   th e  h ar d   co n s tr ain ts   ar e  alr ea d y   s at is f ied   d u r in g   t h e  in itial  s tate  as  f u l f ill m e n t  o f   th e  s o f t  co n s tr ain t s   co m m e n ce s   w h ile,   i n   t h e  p r o c ess ,   m ai n tai n i n g   th e  h ar d   co n s tr ain ts   f r o m   a n y   v io latio n s .   I n   [ 1 2 ,  1 3 ]   a  class - o r ien ted   r e p r esen tatio n   o f   T i m etab l e  is   u s ed ,   w h ich   i m p licit l y   a v o id s   class r o o m   co n ten tio n s ,   th e   i n s tr u cto r - o r ien ted   r ep r esen tat io n   o f   t i m et ab le  is   u s ed   w h ic h   i m p lic itl y   av o id s   in s tr u cto r s   ti m e  tab le  co n te n tio n s .   I n   th is   p ap er ,   b o th   C las s - o r ie n ted   an d   I n s tr u c to r - o r ien ted   r ep r esen tatio n s   o f   a  ti m etab le,   w h ich   a v o id   class   clash e s   an d   in s tr u c to r   clash e s   ar e  u s ed   in   p ar allel.   A cr o s s   t h e  liter at u r e,   v ar io u s   alg o r ith m ic  clas s es  h av e  b e en   p r o p o s ed   to   ad d r ess   th e  s ch ed u li n g   p r o b lem   at  ac ad e m ic  i n s ti tu ti o n s .   T h ese  alg o r ith m s   in cl u d e :  A l g o r ith m s   f all i n g   u n d er   th e   g en etic  al g o r ith m s   class   w h ic h   ar e  o f ten   u s ed   to   tack le  h u g e  a m o u n ts   o f   d ata,   an d   s i m u lated   a n n ea l in g   al g o r ith m s   w h ich   le n d   th e m s el v es   f air l y   w ell   to   p r o b le m s   w it h   lar g e  s ea r ch   s p ac es.  Neit h er   o f   t h ese   clas s es   o f   al g o r ith m s   w i ll  b e   lev er ag ed   i n   th e  c u r r en t  w o r k .   I n   th e  f o r m er   clas s   o f   al g o r ith m s   lar g e  m e m o r y   s izes  ar e   r eq u ir ed   [ 1 4 ,   1 5 ] ,   w h ile  i n   t h e  latter   ca te g o r y   c er tain   d is ad v a n ta g es  ar e  co m m o n l y   e n co u n ter ed .   T h ese  d ea l  w i th   t h e  f ac t  t h at   th e  o p ti m al  s o lu t io n   u s u all y   d ep en d s   o n   th e  in i tial  s ta te  w h er e  th e  s p ee d   o f   co n v er g e n ce   is   r ath er   to o   s lo w   th an   m a n y   o t h er   alg o r it h m s   [ 1 6 ,  1 7 ] .   Fu r th er m o r e,   in   t h is   w o r k   n o   co n s id er atio n   w ill  b e  g iv e n   to   T ab u ’ s   s ea r ch   al g o r ith m   w h ic h   is   cl ass i f ied   u n d er   th e  lo ca l  s ea r c h   f a m i l y   a n d   w o u ld   r eq u ir e  a  lar g e  n u m b er   o f   iter atio n s   f o r   its   co n v er g e n ce   [ 1 8 ] .   I n   th is   p ap er ,   a  n o v el  tech n iq u e  is   p r o p o s ed ;   th is   tech n iq u e  is   m ad e - u p   o f   t w o   s tag e s :  I n   th e  f ir s t,     an   i n itial  s o lu tio n   is   cr ea ted   in   a  w a y   th a t  w o u ld   a v o id   an y   cla s h e s   lev er a g i n g   C las s - o r ie n ted   an d     I n s tr u c to r - o r ien ted   r ep r esen tat io n s   w it h   v ar io u s   o t h er   f u n cti o n s   to   m a k e  s u r e  t h at  n o   ti m e  s lo ts   ar e  s elec ted   i n   w a y s   t h at  w o u ld   e n d   u p   in   cla s h e s .   I n   th e  s ec o n d   s tag e,   t h e  h ill - cli m b i n g   al g o r ith m ,   w it h   s o m e  m o d i f icatio n s ,   p er   th e  p r o ce d u r e  o u tl in ed   in   s ec tio n   3 ,   is   u s ed ,   lev er a g i n g   th e  n u m b er   o f   ad v an ta g es   it   e n tail s   i n cl u d in g   i ts   lo w   p o w er   r eq u ir e m en ts ,   its   r ath er   f ast  co n v er g en ce   a n d   its   r ea s o n ab le  r eq u ir e m e n t s   o f   lo w   m e m o r y   s izes [ 1 9 ] .   T h e  r est  o f   t h is   p ap er   is   o r g an ized   as  f o llo w s :  s ec tio n   2   d etails  th e   co m m o n   p r o b le m   o f   s c h o o l   ti m etab li n g .   Sectio n   3   ill u s tr a tes  th e  m o d i f ied   Hill  C li m b in g   A lg o r it h m .   S ec tio n   4   elab o r ates  th e  m ec h a n ic s   o f   t h e  p r o p o s ed   tech n iq u e,   a s   s ec tio n   5   e x p lain s   t h e  m ai n   r es u lt s   an d   o f f er s   p e r tin e n t   an al y s e s .   Fi n all y ,   s ec tio n   6   p r o v id es th e  co n cl u s io n s .       2.   P RO B L E M   ST AT E M E NT :   DE SCR I P T I O N  AND  R E Q UIRE M E NT S   T h e  p r o b lem   o f   s c h o o l  ti m eta b le  s ch ed u li n g   h as  tr ad itio n al l y   b ee n   d ef in ed   b y   a  p r o ce s s   th at  w o u ld   en s u r e  i n teg r it y   a n d   co n s is t en c y   as  w e   co m b i n e  i n s tr u c to r ,   class r o o m   an d   co u r s e  ti m es  to g et h er   i n t o  co m m o n l y   f ea s ib le  ti m e  s lo ts ,   s atis f y in g   a  ce r tain   g r o u p   o f   co n s tr ai n ts   t h at  w o u ld   m a k e  th e  s tr u ct u r e  o f     th e  tar g eted   s c h o o l  ti m e  tab le  s o u n d   an d   co r r ec t .   T h e  b asic  f ac to r s   o f   th e   s c h o o l  ti m etab le - s c h ed u li n g   p r o b lem   co n tain   f r o m   t h r ee   l a y er s ,   t h ese   t h r e e  la y er s   ar e  f ea t u r ed   in   th e   s a m e  d ia g r a m .   L a y er   1   co n ta in s     th e  m o s t e s s e n tial c o m p o n en t s   in   t h e  p r o ce s s ,   viz.,   I n s tr u c to r s ,   C las s es a n d   C o u r s es.  L a y er   2   f ea tu r es   th e  m o s t   i m p o r tan t  h ar d   co n s tr ai n ts   ( C l ass r o o m   clas h e s ,   I n s tr u cto r   cl ash e s ,   lectu r e  a n d   d a y   teac h i n g   lo ad s )   th a t  m a k e   th e  o v er all  s tr u ct u r e  o f   t h e   ti m etab le  lo g icall y   co r r ec t.  L a y er   3   co n tai n s   a  g r o u p   o f   s o f t   co n s tr ain ts   ( I n s tr u cto r s ’   p r ef er en ce s ,   Dail y   w o r k i n g   lo ad s   ( h o u r s ) ,   d esi r ed   L ast  L ec tu r e  a n d   P r ef er en ce s   o f   th e  C las s es)   w h er e  th e s e  co n s tr ai n t s   ar e  m e an t to   en h an ce   t h e  Sc h o o l T im etab le  q u alit y   [ 2 0 ,  2 1 ] .     2 . 1 .     L a y er   1 :   ins t ruct o rs,  cla s s es,  co urs e s   T h e   I n s tr u cto r s :  I   ( j) ;   j=  1 ,   2 ,   3 ,   …   ,   ḽ ;   ar e   an   ess en tial  ele m en t  in   an y   s ch o o l  ti m etab le - s ch ed u lin g   m ec h a n i s m ,   w h er e  ea ch   o n e   o f   th e  in s tr u ct o r s   h as  a  p ar a m eter   ca lled   S p ec ia lty ,   w h i ch   is   an   i m p o r ta n t  ch ar ac ter is tic  t h at  ca n   tak e  v alu es  f o r   P r im ar y   L e v el  I n s tr u cto r ,   Dip lo m a  an d   B ac h elo r ' s   d eg r ee s   o r   ev en   th o s e  th at  ar e  ab o v e.   T h ese  v alu es  h e lp   th e  p r o g r a m m in g   p r o ce s s   to   d ete r m i n e  th e  cla s s   lev e l  an   i n s tr u cto r   ca n   teac h .   Mo r e  s p ec if icall y ,   an   in s tr u cto r   w ith   a  P r i m ar y   L e v el  I n s tr u cto r   s p ec ialt y   ca n   o n l y   teac h   p r i m ar y   lev el  clas s es,  w h ile  th at  w it h   a  Dip lo m a  s p ec ial t y   ca n   teac h   b o th   p r im ar y   a n d   in ter m ed iate  lev el  class e s   an d   th e  in s tr u cto r   w h o s e  s p ec ial t y   is   at  th e  B ac h elo r ' s   d eg r ee   o r   ab o v e  ca n   teac h   all  class   lev els.  T h e   C lass e s :     C   ( j) ;   j=  1 ,   2 ,   3 ,   …  ,   Ҫ ;  t h e  class e s   co n s tit u te  t h e  s ec o n d   m o s t  i m p o r tan t  ele m e n t  i n   s c h o o l  ti m etab le   s ch ed u lin g ,   w it h   ea c h   cla s s   p o s s ess   in   a  p ar a m eter   ca lled   t h e  C la ss - Leve l .   T h is   p ar a m ete r   ca n   tak e  o n   v alu e s   o f   p r i m ar y ,   i n ter m ed iate  o r   s ec o n d ar y ,   w i th   th e  v al u es  in d icatin g   t h e  s p ec ialt y   o f   th e  i n s tr u cto r   th a t  allo w s   h i m   to   teac h   a  p ar ticu lar   class ,   an d   f in al l y ,   t h e    C o u r s es :  K   ( j ) ;   j=  1 ,   2 ,   3 ,   …  ,   Ḳ ;   w h ic h   ar e  th e  la s t  ele m en t  in   th e  s ch o o l  t i m etab le   s c h ed u li n g   p r o ce s s ,   w h er e  ea c h   co u r s e  h as   a  p ar a m e ter   c alled   C o u r s e   typ e.     T h is   p ar am eter   h a s   t w o   v alu es:  s cien tific   co u r s es  s u ch   as  P h ysics ,  Ma th ema tic s   an d   C h emist r y ,    an d   n o n - s c ien t if ic  o n es  s u c h   a s   A r ts ,  S p o r ts ,  Hi s to ry   an d   C o mp u ter   s kills .   T h is   p ar a m e ter   is   u s u al l y   w e ig h ed   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 558   -   6 5 7 3   6560   in   m o r e  h ea v il y   i n   a s s i g n i n g   s cien ti f ic  co u r s es   to   ea r l y   ti m e  s lo ts ,   a n d   th o s e  t h at  ar e  n o n - s cien ti f ic  co u r s es   to   later   ti m e   s lo t s ;  s o m et h i n g   t h a t  w o u ld   co n tr ib u te  m o r e  p o s iti v el y   to w ar d s   s tu d e n ts ’   lear n i n g   ap p etites.  All  o f   th ese  e le m e n t s   ar e  s c h ed u led   t o   tak e  p lace   w it h i n   ce r tai n   ti m e  s lo ts   d u r i n g   s c h o o l  d a y ,   T S  ( j )   =  1 ,   2 ,   3 ,   …  , Ṣ .   T h e  s o lu tio n   s p ac e  o f   s u c h   a  p r o b lem   t h u s   b ec o m es:      =   ×   ×   ×      ( 1 )     Ass u m in g   t h at  t h e  i n s tr u cto r   te ac h es  j u s t  o n e  o r   t w o   co u r s es,  a  class r o o m   tak e s   s o m e  b u t  n o t  al l   co u r s es,  a n d   it  is   o f te n   k n o wn   w h ic h   i n s tr u cto r   teac h es  wh at  co u r s e  a n d   at  w h ic h   cla s s r o o m .   I n   ad d itio n ,   lectu r es  ta k e  p lace   d u r i n g   a  li m ited   ti m e  f r a m e  ( e. g .   d a y ) ,   w h ich   i n h er en tl y   li m i ts   t h e  ac tu al  ti m es lo ts .   As  a  r es u lt s ,   SP A C E   i s   r ed u c ed   to   V ,   w h er e  V    SP A C E ,   w h ic h   r ep r esen t s   o n l y   th o s e   l ec tu r es  t h e  t i m e   s ch ed u lin g   o f   w h ic h   m a k e s   s e n s e,   s u c h   th at        , , , =   { ;                 ℎ                               ;        ℎ                                                                                                                                                                                              ( 2 )     w h er e  , , ,   r ep r esen ts   a n   ele m e n t  o f       , , , .     2 . 2 .     L a y er   2 :   ha rd  co ns t ra in t s   T h e  s ec o n d   la y er   r ef er s   to   t h e  h ar d   co n s tr ai n ts ,   w h ich   e n co m p as s es  th o s e   co n s tr ain t s   th at   m a k e     th e  s tr u ct u r e  o f   t h e   ti m etab l e  s o u n d   a n d   co r r ec t  w h ich   h as  to   b e  s ati s f ied   in   all   ca s e s   a n d   at  a ll  ti m e s .     T h ese  co n s tr ain t s   i n clu d e:   a.   C las s r o o m   clas h   ( co n f l ict)   C las s r o o m   clas h   r e f er s   to   a   s it u atio n   w h er eb y   w e  w o u l d   allo c ate  m o r e  th a n   o n e   in s tr u cto r   to   th e  s a m e   clas s r o o m   ti m etab le   in   th e  s a m e  ti m e  s lo t.  T h is   p r o b l em   o cc u r s   b ec au s e  t h e  ad m i n is tr ato r   ca n n o t   s ee   th e  ti m etab le  f o r   all  class r o o m s   at  th e  s a m e  ti m e.   C o n s e q u en tl y ,   th e  ap p licatio n   o f   t h e   p r o p o s ed   s o lu tio n   av o id s   t h is   p r o b lem   b y   u s in g   a  C las s - o r ien ted   r ep r esen ta tio n   o f   t h e  ti m etab le,   w h ic h   allo w s   s ee in g   t h e  e n tir e   ti m etab le  f o r   all  class r o o m s   al l a t th e  s a m e  ti m e.   C la s s   clas h es c an   b e  r ep r esen ted   as:     ∑ ( 1 , 1 , 1   +   v 1 , 2 , 1 ) =   1 ;             ∀   ∈ V   ∈       ( 3 )     w h ic h   m ea n s   t h at  f o r   an y   cla s s r o o m   c 1 ,   n o   t w o   co u r s es  ( k 1 ,   k 2 )   ar e  as s ig n ed   to   it  at  t h e  s a m e  ti m e  s lo t s 1   r eg ar d less   o f   th e   in s tr u c to r   wh o   g ets   ass ig n ed   to   th at   p ar ti cu lar   co u r s e.   I n s tr u cto r s   clas h   ( co n f lict) :   T h is   is   q u ite  th e  o p p o s ite  o f   th e  clas s r o o m   clas h   p r o b lem   s u c h   th at   o n e  ca n n o t  allo ca te  m o r e  th a n   o n e  class r o o m   i n   th e  s a m e  t i m e   s lo t  f o r   a  g i v e n   i n s tr u cto r ’ s   ti m etab le.   S u ch   a  p r o b lem   u s u all y   o cc u r s   s i n ce   th e  ad m in is tr ato r   ca n n o t  s ee   t h e  ti m etab les  f o r   all  in s tr u cto r s   al l  at  t h e  s a m e   ti m e.   Her e,   a g ain ,   th e  p r o p o s ed   s o lu tio n   a v o id s   th is   p r o b le m   u s i n g   I n s tr u ct o r - o r ien te d   r ep r esen tatio n   o f   a  ti m etab le  s u c h   t h at  it   allo w s   d is p la y i n g     th e  ti m etab les  f o r   all  in s tr u cto r s   all  at  th e  s a m e  ti m e.     I n s tr u c to r   clash   ca n   b e  r ep r esen ted   in   th e  f o r m :     ∑ ( 1 , 1 , 1   +   v 2 , 1 , 1 ) = 1 ;           ∀     ∈ ∈     ( 4 )     T h is   m ea n s   th at  f o r   an y   g i v e n   in s tr u cto r   i k ,   n o   t w o   clas s r o o m s   ( c i ,   c j )   ar e   ass ig n ed   to   h i m /h er   i n     th e  s a m e   ti m e  s lo t  s k   r eg ar d les s   o f   w h ich   co u r s e s   h e/s h e  i s   a s s ig n ed   to .   F in all y ,   th e   L ec tu r e s   ( w ee k l y )   lo ad :   I n   ev er y   Sc h o o l  p o lic y ,   ea c h   co u r s e  h as  a   p r eset  n u m b e r   o f   lect u r es   p er   w ee k   p er   ea ch   clas s r o o m .     T h is   co n s tr ai n t   r ea d il y   i m p li es  t h at  w e   ca n n o t  p o s s ib l y   i n cr ea s e  o r   d ec r ea s e  t h e  n u m b er   o f   lect u r es  f o r   a  co u r s e  in   a n y   g i v en   cla s s r o o m .   T h er ef o r e,   th e  r eq u ir ed   n u m b er   o f   lectu r e s   f o r   co u r s e  k 1 t au g h t   at  cla s s r o o m   c 1   d u r in g   t h e  w ee k   r eg ar d less   th e  ti m e  s lo t d is tr ib u tio n   o r   th e  p ar ticu lar   in s tr u cto r   o f   th e  c o u r s e  is   g iv e n   b y :        ≡   ∑ ∑ ∑ 1 , 1   ;                 ∀   ∈ ∈ ∈  ∈     (5 )     w h er e  D  ( j )   =   1 ,   …  ,   5 ;  w h ic h   r ep r esen ts   th e  w ee k l y   s c h o o l  d ay s .   Si m ilar l y ,   t h e  n u m b er   o f   lectu r es  h as  to   b e  tau g h t   b y   i n s tr u cto r   i 1  d u r i n g   th e  w ee k   r eg ar d les s   o f   co u r s e s   g et   tau g h t,  t h e  ti m e  s lo ts   o r   th e  cla s s r o o m s   is   g iv e n   b y :      ≥   ∑ ∑ ∑ ∑ 1   ;               ∀     ∈ ∈  ∈ ∈ ∈     ( 6 )       Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       C o u r s es ti meta b lin g   b a s ed   o n   h ill climb in g   a lg o r ith m  ( A b d o u l R jo u b )   6561   b.   Da y   lo ad   T h e  n u m b er   o f   lect u r es  p er   co u r s e  f o r   ea c h   clas s r o o m   m u s t  b e  d i v id ed   in to   f i v e  w o r k in g   d a y s .   Fo r   ex a m p le,   if   a  g iv e n   clas s   r o o m   ca ter s   f o r   f i v e  Ma th   co u r s e  lectu r es,  th e n   ea ch   d a y   ca n   h av e  n o   m o r e  th an   o n e  lectu r e  f o r   th e  s a m e  co u r s e.     C o n s eq u e n tl y ,   th r ee   ca s es   w ill  ar is e  as s u m i n g   th at  t h er e  ar e  5   s ch o o l  d ay s   ( w o r k i n g   d a y s )   i n   a  g i v en   w ee k :   C ase  1 :   C la s s   c   h a s   les s   th a n   f i v e  lectu r e s   o f   co u r s e  k   d u r i n g   th e  w ee k     ∑ ∑ ∑     1 , 1 < 5 ;             ∀   ∈ , ∀     ∈  , ∀     ∈ ∈ ∈  5 = 1   ( 7 )     T h en ,       1 , =   { 0 , 1 } ;       ∀   ∈   ( 8 )     w h er e ,     , ,   ≡   { 1 ;              ℎ                        0 ;        ℎ                                                                                                                                             ( 9 )     C ase  2 :   C la s s   c   h a s   ex ac t l y   f i v e  lectu r es o f   co u r s e  k   d u r in g   t h e  w ee k     ∑ ∑ ∑     1 , 1 = 5 ;               ∀   ∈ , ∀     ∈  , ∀     ∈   ∈ ∈  5 = 1   ( 1 0 )     T h en ,       1 , = 1   ;       ∀   ∈                                                       ( 1 1 )     C ase  3 :   C la s s   c   h a s   m o r e  t h an   f i v e  lectu r e s   o f   co u r s e  k   d u r i n g   th e  w ee k       ∑ ∑ ∑ 1 , 1 > 5 ; ∈ ∈  5 = 1               ∀   ∈ , ∀     ∈  , ∀     ∈   ( 1 2 )     T h en ,           1   ≤   1 ,   ≤ 2   ;       ∀   ∈                                                                             ( 1 3 )     s u c h   th a t     ∑ 1 , 5 = 1 =   ∑ ∑ ∑ 1 , 1 ∈                                                               ∈  5 = 1     ( 1 4 )     T h e  f in al   an d   d ef in i te  co n s tr ain t  i s   th a t  n o   f r ee   lect u r es  ar e  allo w ed   to   b e  ass ig n ed   to   an y   cla s s r o o m   b ef o r e  th e  last   lect u r e  in   t h at  p ar ticu lar   class r o o m   o n   a  g i v en   d ay .       1   ≠ 0 ;           ∀     <         , ∀   ∈ , ∀   ∈                   ( 1 5 )     2 . 3 .     L a y er   3 :   s o f t   co ns t ra int s   So f t  co n s tr ain ts   r ef er   to   t h e  p ar a m eter s   t h at  ar e  s o m e w h at  le s s   i m p o r ta n t  t h an   t h eir   h ar d   co u n ter p ar t s   ar e.   Her e,   alth o u g h   th e s e  w o u ld   s h o w   u p   in   th e  co m p u ter   p r o g r a m ,   it  w o u ld   n o t  b e  v er y   n ec ess ar y   to   ac co u n t   f o r   all  o f   th e m .   Def i n ite l y ,   t h e  m o r e  co n tai n ed   it  is ,   t h e  b et ter   th e  s ch ed u le.   A s   m en tio n e d   ea r lier ,   la y er   3   is   m ad e  u p   o f   t w o   co n s tr ai n ts :   C las s r o o m   p r ef er e n ce s :   P r ef er en ce s   o f   cla s s r o o m s   i m p licitl y   r e f er   to   t h e   th r e e   co n s tr ain ts   a s s o ciate d   w it h   cl ass r o o m s :  Scie n ti f ic  C o u r s e s :  Scien ti f ic  co u r s es   s u ch   a s   P h ysics ,  Ma th ema tics ,  C h emist r y   an d   B io lo g y   ar e  t o   b e  co n s id er ed   d u r in g   th e  ea r l y   ti m e  s lo ts .   No n - Scien ti f ic   C o u r s es :     No n - Scien tific   co u r s e s   s u c h   a s   A r ts ,   S p o r ts ,   His to r y  a n d   C o mp u ter  s kills   ar e  to   b e  co n s i d er ed   f o r   th e  latter   ti m e  s lo ts .   T h e  I n s tr u cto r   p r ef er en ce s   w h ich   i s   an   e s s en tia l  p ar t  o f   th e  teac h in g   p r o ce s s   ad d r ess es     th e  i n s tr u cto r s ’   co n v e n ie n ce   a n d   co m f o r t  lev el s   d u r in g   t h e  s e m ester ,   s u c h   t h at  th e  teac h i n g   ef f o r t  is   r e f lecte d   m o r e  p o s iti v el y   o n   th e  o v er all  ed u ca tio n al  p r o ce s s .   Hen ce ,   s ev er al  in s tr u cto r - ce n tr ic  f ac ets  ar e  co n s id er ed .   T h ese  in clu d e  an   i n s tr u cto r ’ s   p r ef er en ce   o n   w h et h er   h e/ s h e  w o u ld   r ath er   s tar t  th eir   d ail y   t ea ch in g   i n   th e  f ir s t   lectu r e  s lo t  o f   ea c h   d a y   o r   n o t .   A l s o ,   an   in s tr u cto r ’ s   p r ef er e n ce   to   ca ll  it  a n   ea r l y   q u it s ,   o n   a n y   p ar tic u lar   d a y   o f   ch o ice,   a n d   f i n all y   w h et h e r   th e  i n s tr u cto r   s till   h ap p en s   to   b e  a  s tu d en t  o f   t h e  i n s tit u t io n   h i m s el f /h er s el f   w it h   ce r tai n   co n v en ie n ce - d r iv en   n ee d s   t h at  n ee d   to   b e  ac co m m o d ated   b y   t h e  ti m etab le  o r g an izer s .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 558   -   6 5 7 3   6562   3.   E F F I CI E N T   H I L L   C L I M B I NG   A L G O R I T H M   T h e  Hill  C li m b in g   A l g o r ith m   ( HC A )   is   a  m at h e m atica l  te ch n iq u e  th at  b elo n g s   to   th e  ca teg o r y   o f   lo ca l  s ea r ch   a lg o r it h m s   [ 2 0 - 2 2 ] .   I t  is   a  r ep etiti v e  al g o r ith m   th at   s tar t s   w it h   a n   in i tial  p o p u latio n   ch o s en   f r o m   th e  p r o b lem   s o lu t io n s   s p ac e.   I t  th en   g o es  t h r o u g h   a  p r o ce s s   th at  i m p r o v es  t h ese  s o lu t io n s   b y   in cr e m e n ta ll y   ch an g i n g   o n e  o f   t h e  ele m en ts   in   o r d er   to   cr ea te  n e w   s o l u tio n s .   I n   t h e  p r o ce s s ,   s o l u tio n s   t h at  h av e  h i g h er   co s t  v alu e s   ar e   ad o p ted   in   a n   e f f o r t  to   g e n er ate  a   n e w   p o p u la tio n   a n d   t h e  p r o ce s s   is   r ep ea ted   u n til   n o   f u r th er   i m p r o v e m en t s   ca n   b e  ac h ie v e d   [ 2 3 ] .     Un d er   th e  p r o p o s ed   tech n iq u e,   th e  Hill  C li m b in g   al g o r ith m   i s   m o d if ied   to   b e  u s ed   as a n   o p ti m izat io n   alg o r ith m ,   w h er e  th e  o p ti m i za tio n   p r o ce s s   co n tin u e s   as   lo n g   as  th e  ca lcu lated   h e u r is tic  v al u e   ,   i.e . ,     co s t  v a lu e,   o f   t h e   last   o p ti m iz ed   s o lu tio n   i s   le s s   th a n   ze r o ;  o th er   t h an   th a t  t h e  p r o ce s s   is   s to p p ed   if   t h is   v alu e   d o es  n o t  ch an g e  f o r   eig h t  co n s ec u ti v e  e x ec u tio n s ,   as  t h is   wo u ld   in d icate   th at  n o   f u r th er   i m p r o v e m e n t  ca n   b e   ac h iev ed ,   a n d   th e  s o lu t io n   i s   f in all y   r ea ch ed   [ 2 4 ] .   T h e  h eu r i s tic  v alu e  is   a  li n ea r   f u n ctio n   o f   s o f t  co n s tr ain t s ;  s u c h   t h at  it  m ea s u r es  to   w h a t  d eg r ee   th e  c u r r en t  s o lu tio n   s atis f ie s   th e s e  co n s tr ain t s .   I t   ch ec k s   i f   t h e  t w o   co n s tr ain ts   o f   cla s s   p r ef er e n ce s   ar e  s atis f ied   f o r   all  clas s es i n   th e  s c h o o l,  s u c h   th at:      =   { 0 ;            ℎ                 ′                                                                                                           − 1 ;              ℎ                                                  − 2 ;         ℎ      ℎ                                                                                        ( 1 6 )     w h er e       r ep r esen ts   a  m ea s u r e  o f   th e  cla s s   p r ef er e n ce   co n s tr ai n ts   f o r   class   c.   I n   ad d itio n ,   it  c h ec k s   i f   t h e  co n s tr ai n ts   o f   t h e  i n s tr u cto r ' s   p er s o n al  p r ef er e n ce s ,   d ail y   w o r k   h o u r s   a n d   last   lect u r e  p r ef er en ce s   ar e  s at is f ied   f o r   all  in s tr u cto r s ,   s u ch   t h at:      =   {         0 ;            ℎ         ,       ℎ                                                                                                                                   − 1 ;              ℎ                                                                            − 2 ;            ℎ                                                                   − 3 ;           ℎ                                                                               ( 1 7 )     w h er e       r ep r esen ts   th e  m ea s u r e m en t  o f   th e  i n s tr u cto r 's  p r e f er en ce s ,   d aily   w o r k   h o u r s   an d   last   lectu r e  p r ef er en ce s   f o r   in s tr u cto r   i .   As   a  r esu lt,  th e  h eu r i s tic  p ar a m et er   is   g iv e n   as :     =   ∑  Ҫ = 1 +   ∑  ḽ = 1     ( 1 8 )     T h e  in itial  a n d   o p ti m al  v al u e  f o r   is   0 .   I t  is   d ec r ea s ed   b y   1   ea ch   ti m e  a n y   o f   t h e  co n s tr ain t s   is   f o u n d   to   b e  v io lated   f o r   an y   cla s s r o o m   o r   in s tr u cto r .   Har d   co n s tr ai n ts   ar e  n o t c o n s id er ed   as M H C A   d o es n o t p r o v id e  a  s o lu tio n   u n les s   all  th e  h ar d   co n s tr ain ts   ar e  s ati s f ied .   T h e  in p u t  v ec to r   th at  is   r eq u ir ed   to   r u n   th is   tech n i q u e  is :   〈     ,     ,          〉   as f o llo w s :   -   C o u r s e  d etails : s u ch   as c o u r s e  titl e,   co u r s e  t y p e  ( Scie n ti f ic  o r   No n - Sc ien t if ic) .   -   C las s   d etail s :  s u c h   a s   cla s s   n a m e,   cla s s   d iv i s io n ,   cla s s   le v el  ( P r im ar y ,   I n ter m ed iate   o r   Seco n d ar y )   a n d     th e  lis t o f   all  co u r s e s   th a t a r e  tau g h t i n   a  g i v e n   class r o o m .   -   I n s tr u c to r   d etails:   s u ch   as  h i s /h er   I D   n u m b er ,   n a m e,   n u m b er   o f   le ctu r e s   h e/s h e  ca n   teac h ,   i n s tr u cto r   s p ec ialt y   ( P r i m ar y   lev e l,  Dip lo m a  o r   B ac h elo r ' s   d eg r ee   o r   ab o v e)   a n d   a  lis t  o f   all  class r o o m s   a n d   th e  co u r s e s   th at  ar e  ta u g h t b y   t h is   i n s tr u cto r .       4.   T H E   P RO P O SE D  T I M E T A B L E   SCH E DU L I N G   T E CH NIQU E     On ce   all  r eq u ir ed   d ata  w ill   h av e  b ee n   id en t if ied   a n d   ac co u n ted   f o r ,   th e  cr ea tio n   p r o ce s s   w il l   co m m e n ce   i n   t h r ee   s ep ar ate  p h ase s .   T h e  f ir s t   p h ase  is   t h e  d ata  o r g an izatio n   p h a s e  ( DOP )   w h ic h   o r g a n izes  al l  th e  d ata  th at   w as   ac co u n ted   f o r   ea r lier .   T h e  s ec o n d   p h ase   is   t h e  i n itia l  s tate  p h a s e  ( I SP )   w h ic h   cr ea tes   a n   in itial  s o lu tio n   f o r   th e  t i m e ta b le  an d   th e  th ir d   p h ase  i s   th e  s atis f ied   s o f t  co n s tr ai n ts   p h ase   ( SS C P )   w h ic h   i m p r o v es   th e   i n itial  s o lu tio n   u s i n g   MH C A   to   s ati s f y   a ll  o f   th e   s o f t  co n s tr ain ts   a s   it   p o s s ib l y   ca n   i n   o r d er   to   ac h iev e  t h e  " b est"   f in al  s o l u tio n   [ 2 5 ] .         Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       C o u r s es ti meta b lin g   b a s ed   o n   h ill climb in g   a lg o r ith m  ( A b d o u l R jo u b )   6563   4 . 1 .     T he  da t a   o rg a niza t i o n pha s e  ( DO P )     W h en   th e  s y s te m   b eg i n s   to   b u ild   a  s ch o o l  ti m etab le,   it  co m m en ce s   b y   o r g an izi n g   th e  r eq u ir ed   d ata  as  a  f ir s t  tas k .   I n   th i s   p h ase  ( DOP ) ,   th e  s y s te m   s tar ts   t h e  cr ea tio n   o f   th e  ti m etab le   b y   lo ad in g   th e  r eq u ir ed   d ata  an d   s etti n g   u p   th e  d ata  s tr u ct u r es.  Su c h   r eq u ir ed   d ata  in   th e  s ch o o l o b j ec t sp lits   in to   f o u r   t y p e s   o f   o b j ec ts :   -   I n s tr u c to r   Ob j ec t:  co n tain   v ar iab les  s u c h   as  I n s tr u cto r - I D,   I n s tr u cto r - T o tal - Nu m b er - Of - L ec tu r e s   an d   C las s - C o u r s e - Li s t  t h at  r e f er s   to   th e  cla s s e s   a n d   co u r s e s   w h ich   t h i s   i n s tr u cto r   teac h e s   a n d   th e  I n s tr u cto r - Nu m b er - Of - L a s t - L ec tu r e.   -   C las s   Ob j ec t:  co n tain s   v ar iab les  s u c h   as  C las s - I D,   C lass - T o tal - N u m b er - Of - L ec t u r es,  C l ass - C o u r s e - L is t   th at  r ef er s   to   ea ch   co u r s e  w it h   its   in s t r u cto r s ,   C las s - L a s t - L e ctu r e  th at  r ef er s   to   th e  in d e x   o f   last   lect u r e  in   th e  clas s   ti m etab le  an d   C la s s - Nu m b er - Of - L a s t - L ec tu r e  t h at  r ef er s   to   th e  to tal  n u m b er   o f   la s t le ctu r e s .   -   C o u r s e  Ob j ec t: c o n tain s   v ar ia b les s u c h   as  C o u r s e - I D  an d   C o u r s e - T y p e.   -   C las s - C o u r s e   Ob j ec t:  co n tain s   s o m e   v ar iab les   th a t  li n k   C l ass - I D,   C o u r s e - I D,   N u m b er - Of - L ec tu r e s   an d   I n s tr u c to r - I D  w it h   th e  I n s tr u ct o r   Ob j ec t,  C lass   o b j ec t a n d   C o u r s e  o b j ec t.   On ce   t h e  r eq u ir ed   d ata  is   lo ad ed   an d   s p lit   in to   th e   s aid   o b j ec ts ,   t h e  al g o r ith m   co m m en ce s   t h e  s c h o o l   ti m etab le  g e n er atio n .   T h e  I C T NL   F u n ct io n   ill u s tr ates  h o w   m an y   ti m es  ea ch   s p ec i f ic  co u r s e  is   g o n e  th r o u g h   f o r   a  s p ec if ic   i n s tr u cto r   an d   h o w   m a n y   ti m es   ea c h   s p ec i f ic   co u r s e  i s   g o n e  th r o u g h   f o r   a  s p ec if ic  cla s s r o o m .     A   lo o p   s elec ts   th e  n ex t  o b j ec t   f r o m   C la s s - C o u r s es  li s t,  an d   th en   f i n d s   th e  i n s tr u cto r   o b j ec t  th at  h a s   th e  s a m e  I n s tr u c to r - I D.   T h is   is   p er f o r m ed   i n   o r d er   to   ad d   t h e  n u m b er   o f   lect u r es  f o r   t h e  C la s s - C o u r s es   o b j ec t  to     th e  to tal  n u m b er   o f   lect u r es  o f   th e  i n s tr u cto r   o b j ec t  an d   th en   t h e  s a m e  p r o c ed u r e  is   r ep ea ted   f o r   th e  class   o b j ec t.  I t  is   q u ite  ev id en t  th a t  t h e  co m p lex it y   o f   th i s   f u n ctio n   is     (  ( ḽ   +   Ҫ ) ) .   W h er e  CKO   is   t h e  n u m b er   o f   class - co u r s e  o b j ec ts ,   w h ic h   ca n   b e  d escr ib ed   as:      =   ∑ ∑ ∑ ,   ;           ∀     ∈ , ∀   ∈ , ∀   ∈     ∈ ∈  ∈     ( 1 9 )                         =   ∑ ∑    ;               ∀   ∈ ∈ ∈ , ∀ ∈       Th e  to tal  n u m b er   o f   lect u r es  f o r   an y   in s tr u cto r   i   is :      =   ∑ ∑ ∑ ∑   ;             ∀   ∈ , ∀   ∈ , ∀   ∈ , ∀   ∈ ∈          ∈ ∈ ∈ , ∀   ∈    ( 2 0 )     Si m i lar l y ,   t h e  to tal  n u m b er   o f   lectu r es  f o r   an y   cla s s   c   is :      =   ∑ ∑ ∑ ∑ ;         ∀   ∈ , ∀   ∈ , ∀   ∈ ,       ∀   ∈ ,       ∀   ∈  ∈  ∈ ∈ ∈   ( 2 1 )     Fro m   ( 1 0 ) ,   th e  to tal  n u m b er   o f   lect u r es  i n   t h e  s c h o o l  is   th e  s u m m atio n   o f   t h e  to tal  n u m b e r   o f   lectu r e s   o f   al l   class r o o m s ,   as  g i v en   b y :     Ω =   ∑    ;           ∀   ∈ ∈     ( 2 2 )     As a  r esu lt,  t h e  p r o b ab ilit y   to   s ch ed u le  th e  lect u r es o f   t h e  n e x t in s tr u c to r   ( f+1 )   is :     + 1 =   ( 1 ḽ   − ) ( Ω   −   −   ∑  1 Ω )     ( 2 3 )     w h er e  z   is   t h e  n u m b er   o f   lectu r es r eser v ed   f o r   in s tr u cto r   ( f+1 )   in   th e  p r o ce s s .   On ce   t h e   to tal  n u m b er   o f   lect u r es  i s   ca lcu lated ,   an   I L L   f u n ctio n   w i ll  f i n d   t h e  i n d ex   f o r   l ast  lect u r e   f o r   ea ch   clas s r o o m ,   i.e . ,   th e  t i m e  s lo t  o f   t h e  last   lectu r e  with i n   t h e  w ee k ,   in   o r d er   to   in itialize  i n s tr u cto r ’ s   ti m etab le s   an d   cla s s   ti m etab les  as  w e ll  as  th at   f o r   t h e  s c h o o l   as  a  w h o le.   A   n e w   p ar a m eter   is   as s ig n ed   ( ( Ҫ ) )   to   d is tr ib u tes  th e  cla s s   lect u r e s      o v er   th e  f i v e  w ee k l y   d a y s   e v en   h an d ed l y   to   f in d   t h e  m a x i m u m   ti m e  s lo ts   f o r   o n e  w o r k i n g   d a y .   T h e n ,   w h er e  t h er e  r e m ain   lect u r es   u n ac co u n ted   f o r ,   t h e  I L L   in cr ea s es  t h e   m a x i m u m   n u m b er   o f   ti m e  s lo t s   b y   o n e ,   an d   d is tr ib u tes  th ese  lect u r es  o v er   th er e  m a in i n g   in s tr u cto r s   s tar tin g   f r o m     th e  f ir s t d a y   o f   t h e  w ee k ,   s u c h   th at:      =   {  5 ;                 (  5 ) = 0  5 + 1 ;            ℎ                      ( 2 4 )     w h er e      is   t h e  m a x i m u m   n u m b er   o f   tim e  s lo ts   o f   class   c  f o r   an y   w o r k i n g   d a y .   Fo r   th e  en tire   s ch o o l,    th e  in d e x   f o r   th e  la s t le ct u r e     is   g i v en   b y :   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 558   -   6 5 7 3   6564    =  (  ) ;                                   ∀     ∈     ( 2 5 )     T h e  NL L I   Fu n ctio n   in   g e n er al   co u n t s   h o w   m a n y   w e e k l y   lect u r es  ar e  s c h ed u led   to   tak e  p la ce   in   ti m e   s lo t   f o r   th e  w h o le  s ch o o l,  an d   th e n   it  d is tr ib u te s   th e s e  l ec tu r es  a m o n g s t  i n s tr u cto r s   ev en - h an d ed l y .     T h is   h ap p en s   co m m e n s u r ate  w it h   t h e  f air n es s   cr iter io n   t h a t  w ar r an ts   th at   th e   lect u r e  d is tr ib u tio n   p r o ce s s   i s   b ias  f r ee   d e v o id   o f   a n y   f av o r i tis m   p r ac tices,  p er   t h e  s o f t  co n s tr ai n ts   i n   s ec t io n   2 .   As  a  r es u lt  o f   t h is   f u n ctio n ,   ea ch   i n s tr u cto r   g ets   h i s / h er   o wn   s h ar e  o f   t h e  Nu m b er   o f   L ast   L ec t u r es   ( N L L ) .   First,   th e   n u m b er   o f   a ll lec t u r es   th at  ta k e  p lac e   ti m e  s lo t a cr o s s   th e  s c h o o l is g i v en   b y :      =   ∑ ∑  ;             ∀   ∈ Ҫ Ҫ = 1 5 = 1     ( 2 6 )     T h en   f o r   all  in s tr u cto r s ,   i f   i n s tr u cto r   i   teac h e s   a  class   s u c h   th a t    =    ,   th e n   th e  n u m b er   o f   in s tr u cto r s   w h o   teac h   lect u r es  in   th a t c lass r o o m   w i th in   t h at  ti m e  s lo t is  g i v en   b y :      =    + 1     ( 2 7 )     w h er e  t h er e  s t ill  e x i s ts   ca s es   o f   m o r e  lectu r es   t h an   t h er e  ar e  in s tr u cto r s ,   th e n   t h e  r e m ai n i n g   n o n - d i s tr ib u ted   lectu r es  ar e  d is tr ib u ted   r an d o m l y   ac r o s s   i n s tr u cto r s ,   s u ch   t h at  t h e  r an d o m   p r o b ab ilit y   to   s elec t  an y   o n e  o f   th e m   is :      =   1      ( 2 8 )     4 . 2 .     T he  ini t ia l st a t e  ph a s e   ( I SP)   I n itiall y ,   an d   as  ex p lain ed   i n   [ 1 6 ,  1 7 ] ,   th e  f ir s t  s tep   is   to   cr ea te  a  r an d o m   in itia l  s o lu tio n   an d   th e n   p er f o r m   ad d itio n al  o p er atio n s   o n   it  w it h   t h e  o b j ec tiv e  o f   s atis f y i n g   t h e  h ar d   co n s tr ain t s   th er eb y   ar r iv i n g   at     th e  co r r ec t  i n itial   s o l u tio n   [ 1 8 ] .   I n   f ac t,   th is   h a s   b ee n   a  r ath er   ti m e - co n s u m i n g   m et h o d .   I n   t h e  p r o p o s ed   tech n iq u e,   th e  i n itial  s o lu tio n   w h ich   i s   cr ea ted   in   th e  in i ti al  s tate  p h ase   ( I SP ) ,   k ee p s   all  h ar d   co n s tr ain t s   d ev o id   f r o m   an y   v io latio n s   s o   as  to   m ain tain   i n te g r it y   an d   c o r r ec tn ess   o f   t h e  ti m etab le  s tr u ctu r e  t h r o u g h o u t.   T h e  I SP   p r o ce s s   ca n   b e  s p lit  in to   th r ee   m ain   p ar ts   i n   a  w a y   t h at  w o u ld   u n d er s co r e  its   r ath er   i m p o r tan t   f u n ct io n s :     4 . 2 . 1 .  Co m m o n  brea k   a rr a y   ( CB A)     W h en   an   i n s tr u cto r   is   p ick ed   an d   a  s p ec if ic  clas s r o o m   is   id en ti f ied ,   a  t w o - d i m e n s io n al  ar r ay   ca ll e d   th e  co m m o n - b r ea k - ar r a y   ( C B A )   is   g e n er ated .   First,  th e  i n s tr u cto r   ti m etab le  an d   th e  cl ass r o o m   ti m etab le   co n tain   th r ee   t y p es  o f   ti m e  s lo ts   as  s h o w n   i n   F ig u r e  1 (a )   an d   1 ( b ) :  ti m e  s lo ts   r eser v ed   f o r   th e   clas s r o o m   ( T SR C ) ,   ti m e  s lo ts   r e s er v ed   b y   t h e  i n s tr u cto r   ( T SR I )   an d   als o   th e  r e m ain in g   n o n - r eser v ed   ti m e  s lo ts   ( N R T S).   W h en   t h e  i n s tr u cto r   ti m e tab le  is   o v er lap p ed   w it h   a  cla s s r o o m   ti m etab le,   t h e  co m m o n   b r e ak   ar r a y   ( C B A )   w il l   b e  g en er ated   as  s h o w n   ag a i n   in   F ig u r e  1 ( c ) .   No w ,   t h e  g en er ated   C B A   h a s   t w o   t y p es  o f   T im e  S lo ts :   a  No n -   R e s er v ed   t i m e   s lo t  th at   is   r ep r ese n ted   b y   Y/Yes   an d   a  r eser v ed   ti m e  s lo t  ( b y   ei t h er   an   i n s tr u cto r   o r   a   class r o o m )   th at  i s   r ep r esen te d   b y   an   N /No   as ill u s tr ated   b y   ( 2 9 ) .     , =   , ,   ( 2 9 )     w h er e,   ,   is   i n s tr u cto r   i ’ s   ti m et ab le  an d   ,   is   cla s s r o o m   c ’ s   o c cu p an c y   ti m etab le  as  g i v en   in   ( 30 )   an d   ( 31 ) ,   r esp ec tiv el y .     4 . 2 . 2 .     T i m e  s lo t   s el ec t io n  ( ST S)  f un ct io n   T h e  ST S  is   an   im p o r tan t  f u n ct io n   th at  o f f er s   s e v er al  ad v a n ta g es  i n   th e  p r o p o s ed   tech n iq u e,   a m o n g s t   w h ic h   th a t  o f   m i n i m izi n g   t h e   s ea r ch   s p ac e,   p er   eq u atio n   3 0 ,   b y   av o id i n g   ti m e  s lo ts   w it h   a  lab el  o f   ( N)   in     th e  C B A ;  a s   a  co n s eq u e n ce ,   t h e  ex ec u tio n   ti m e  is   f u r th er   r ed u ce d .   Fu r th er m o r e,   t h e  ST S  f u n ct io n   a v o id s   s i m u lta n eo u s   clas s r o o m   a n d   in s tr u cto r   co n f lic ts   ( clas h es)  as   it  o n l y   s ea r ch e s   f o r   th e  s e t  o f   ti m e  s lo ts   t h at  s t ill   ex h ib it   t h e  lab el  ( Y)   i n   t h e  C B A ,   s a y   Y C B A ,   w h ic h   m ea n s   th at  th e s e   ti m e  s lo ts   ar e  s til l  No n - R eser v ed ,   as  i s   g iv e n   b y   ( 31 ) .      Ω ( , ) =   | , | × |  , |     ( 3 0 )      , , , ∶ ,   →  , ,       ,   → ,     ( 3 1 )   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       C o u r s es ti meta b lin g   b a s ed   o n   h ill climb in g   a lg o r ith m  ( A b d o u l R jo u b )   6565    , , ,  ,       w h er e  , ( , ) = 1 , … , ɖ   is   d a y s   t h at  h av e   , ( , ) = 1 , …   ,       n o n   r eser v ed   ti m e  s lo ts .           Fig u r e  1 .   C o m m o n - b r ea k - a r r ay   ( C B A )   i m p le m en tatio n       On ce   th e  C B A   is   g e n er ated   p er   s ec tio n   4 . 2 . 1 ,   th e  ( S T S)  ad o p ts   o n e  r an d o m   No n - R ese r v ed   T im e  Slo t   f r o m   t h e  C B A  in   o r d er   to   ch e ck   i f   a  p ar ticu lar   t i m e s lo t  i s   a p p r o p r iate  ( v alid )   f o r   th e  cla s s /co u r s e.   W h e n   t h i s   o cc u r s ,   th e  co u r s e  w ill  b e  ass i g n ed   to   t h is   ti m e  s lo t.  As  a  r esu l t,  th i s   ti m e  s lo t  w il l  b e  m ap p ed   to     th e  cla s s r o o m   a n d   in s tr u c to r   ti m etab les  a n d   u p d ated   in   t h e  C B A  w it h   a n   ( N ) ;  o t h er w is e  t h is   ti m e  s lo t  w ill  b e  u p d ated   b y   th e  C B A   w it h   a  ( U /Un d er   d e m an d ) .   T h is   p r o ce d u r e  w ill  b e  r ep ea ted   u n til   all  ti m e  s lo ts   s tar t   ex h ib it in g   eit h er   ( N   o r   U ) .   Fig u r e  2   ill u s tr ate s   an   e x a m p le  th at  s c h ed u l e s   a  P h y   C o u r s e  a t  th r ee   lect u r es  p er   w ee k .   S0 :  De s ig n ate  th e  C B A  ar r ay   th at  is   cr ea ted   p er   s ec ti o n   4 . 2 . 1 .   S1 :  Div id e  th e  C B A  in to   f iv e  n o d es  to   r ep r esen t  th e   w o r k i n g   d a y s   p er   w ee k .   S2 :  R e m o v e  all  ti m e  s lo ts   w i th   th e  lab el  N  ( R e s er v ed   T im e  Slo ts ) .     S3 :  I n   o r d er   to   s ch ed u le  t h e  f ir s t  lect u r e  o f   t h e  P h y   co u r s e,   th e  ST S  f u n ctio n   d es ig n ate s   T S3   f o r   T h u r s d a y ,   T S3   w ill  b e  i m p lic itl y   u p d ated   w it h   lab el  ( N )   an d   th en   r e m o v ed   f r o m   s ea r ch   s p ac e.   No te  th at  th i s   d a y   b ec o m e s   e m p t y ,   an d ,   co n s eq u en tl y ,   t h e  ST S  f u n ct io n   n e g le cts  a n y   f u r t h er   co n s id er atio n   o f   it   an d   th e   s ea r c h   s p ac e  is   r e s tr icted   o n l y   to   f o u r   d a y s .   I n   S4 :  T h e  ST S  co n tin u es  to   s c h ed u le  th e   s ec o n d   lectu r e  o f   t h e  P h y   co u r s e.   I t  d esig n ates  a s   T S4   f o r   Su n d a y ;  T S4   is   t h en   u p d ated   i m p licitl y   w it h   lab el  ( N )   an d   th e n   w ill,  a g ain ,     b e  r e m o v ed   f r o m   s ea r ch   s p ac e.   S5 :  T h e  ST S  d esig n ate s   T S2   f o r   T u esd a y   in   o r d er   to   s ch ed u le  t h e  la s t  lec tu r e   o f   th e  P h y   co u r s e.   T S2   is   f i n a ll y   i m p licitl y   u p d ated   w ith   a   l ab el  o f   ( N )   w h ich   w ill  co n s eq u en t l y   b e  r e m o v ed   f r o m   s ea r ch   s p ac e.   S6 :  Di s p l ay s   th e   e n d   r es u lt  o f   t h e   C B A   p r o ce s s .   I n   f ac t,  s u c h   s u b s et  o f   C B A   w o u ld   o n l y   b e  av ailab le  i f   t h e  co r r esp o n d in g   s u b s ets  o f   t h e  i n s tr u cto r   an d   clas s r o o m   ti m etab les  a r e  b o th   av ailab le,     s u c h   th a t        , , , =    , , ,  , , ,     ( 3 2 )     w h er e       , , , ,   r ep r esen ts   all  av ailab le  n o n - r eser v ed   ti m e  s lo ts   f o r   in s tr u ct o r   i’ s   ti m etab le  w h ic h   is   f il led   b y   a ( – ) d en o tatio n .    , ,  ,   r ep r esen ts   all  av ailab le  n o n - r eser v ed   ti m e  s lo ts   i n   class   c ’ s   ti m etab le  w h ic h   is   f illed   w it h   a ( – ) d en o tatio n .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 558   -   6 5 7 3   6566       Fig u r e  2 .   Select  t i m e  s lo t ( STS)   f u n ctio n       So ,   in s tead   o f   s ea r c h i n g   ∑ 5 = 1 ,   it  is   n e ed ed   to   s ea r ch   ∑ ᾽ ɖ = 1 ,   w h er e    is   th e  to tal  n u m b er   o f   tau g h t  ti m e  s lo t s   d u r i n g   d a y   d ,   an d   ᾽   is   t h e  n u m b er   o f   a v ailab le  n o n - r eser v ed   ti m e  s l o ts   f o r   d a y   d .     T h e  r elativ e  p er ce n t i m p r o v e m en t c an   b e  m ea s u r ed   as     R ela tive  P ercen t      ( ε ) =   | ∑   −   ∑ ᾽ ɖ = 1 5 = 1 | ∑ 5 = 1 × 100%     ( 3 3 )     T h e  w o r s t  ca s e  w il l  m an i f e s t  its el f   d u r i n g   t h e  i n itial   s tate  wh er e  all  t i m e s lo ts   f o r   b o th   t h e   in s tr u cto r   an d   t h e  cla s s r o o m   t i m e tab les   w o u ld   s h o w   as  n o n - r eser v ed   s tat u s .   On   t h e  o t h er   ex tr e m e ,   th e  b e s t  ca s e  w il l   ap p ea r   w h e n   b o th   ti m etab le s   r ef lect  t h e  s a m e  ti m eslo t,  i n   wh ich   ca s e  t h e  r elati v e  p er ce n t  i m p r o v e m e n t  w o u ld   ap p r o ac h   1 0 0 %.  A s   a  r esu lt,  t h e  r elativ e  p er ce n t i m p r o v e m e n t a ch ie v ed   is :     | ∑   −   ∑ ᾽ ɖ = 1 5 = 1 | ∑ 5 = 1 × 100%   < 100%     ( 3 4 )     No w   r ev er ti n g   to   th e  P h y   co u r s e  w h ich   h as  t h r ee   lectu r es  p er   w ee k ,   t h e  ST S  f u n ctio n ,   in   th is   ca s e,   w il l  b e  r ep ea ted   th r ee   ti m es   in   th e  p r o ce s s   o f   u p d atin g   t h e  t h r ee   tab les  ( I n s tr u cto r   T im etab l e,   C las s   T i m etab l e  an d   C B A ) .   I n   t h is   e x a m p le,   th e  ST S  f u n c tio n   co m m it s   T S4   f o r   S u n d a y ,   T S2   f o r   T u esd a y   a n d   T S3   f o r   T h u r s d a y ,   w it h   a  f i n al  r es u lt  a s   s h o w n   in   Fig u r e  3 ,   n o ti n g   t h at  t h e  r ed   s lo ts   ar e  u s ed   to   d en o te  th e   ti m e  s lo t s   th at  h a v e  b ee n   c h an g ed .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       C o u r s es ti meta b lin g   b a s ed   o n   h ill climb in g   a lg o r ith m  ( A b d o u l R jo u b )   6567       Fig u r e  3 .   Fin al  r es u lt a f ter   s ett in g   3   l ec t u r es o f   p h y   c o u r s e       4 . 2 . 3 .     Swa p  t i m e  s lo t s   f un ct i o n f o r  t w o   ins t ruct o rs  ( ST SI )   W h en   th e  ST S  f u n ctio n   f ail s   to   s elec t  ap p r o p r iate   ti m e  s lo ts   f r o m   C B A ,   t h en   it  w o u ld   b e  ess e n tial  to   ex ec u te  t h e  ST SI  f u n ctio n .   T h is   f u n ct io n   d ea ls   w it h   p o ten tia ll y   e m er g i n g   ca s e s   o f   t w o   in s t r u cto r s   s h o w i n g   at  th e  s a m e  ti m e   an d   s tr iv e s   to   s w ap   ar o u n d   th e   ti m e  s lo t s   b et w ee n   t h e m .   A s   a n o t h er   ex a m p le,   Fig u r e  4   o u tli n e s   th e  p r o ce s s   o f   s ch ed u lin g   a  M ath   co u r s e  w i th   f i v e  lect u r es  p er   w ee k   f o r   in s tr u cto r   ( Mr .   J a ck )   an d   class r o o m   ( C 6 ) .   T h e  f ir s t  f o u r   lectu r es  f o r   th is   Ma t h   co u r s e  ar e  alr e ad y   s ch ed u le d   th r o u g h   t h e  C B A   p r o ce s s   u s in g   th e  ST S  f u n ctio n   ( th o s e  co lo r ed   as  g r ee n ) ,   w h er e  t h e  last   lectu r e  is   s h o w n   to   h a v e  f ail ed ,   w h er e  it  w o u ld   r eq u ir e  th e  h elp   o f   t h e  ST SI   f u n ctio n .   T h e  f o llo w i n g   s tep s   s e r v e  to   o u tlin e  t h i s   p r o ce s s .   I n   S1 ,   th e  p r o ce s s   b eg in s   b y   l o ad in g   Mr .   J ac k ’ s   a n d   C 6   ti m etab les.  S2   s elec ts   a  No n - R e s er v ed   ti m e   s lo t  f r o m   Mr .   Ja ck   tim etab le   an d   f etch e s   th e  co r r esp o n d in g   co u r s e  f r o m   t h e  C 6   ti m et ab le,   in   w h ic h   ca s e     th e  T i m e  Slo t  w o u ld   b e  T S4   a s   co lo r ed   in   r ed   w h er e  th e  co r r esp o n d in g   co u r s e  is   A r t) .   T h is   is   f u l f illed   b y :     〈 ∗ , ∗ 〉 =    , 1  ,     ( 3 5 )     w h er e  i 1  r ep r esen ts   t h e   i n s tr u cto r   to   b e  s ch ed u led ,   w h ich   r ep r esen ts   Mr .   J ac k   in   t h i s   ca s e.   T h e  p r o ce s s   th en   f etc h es  th e   in s tr u cto r   w h o   tea ch es   th is   co u r s e  a s   s h o w n   i n   S 3 ,   w h o   h ap p en s   to   b e  M r .   Liu ).   Af ter   lo ad in g   M r .   Liu ’ s   ti m etab le,   t h e  alg o r it h m   p ick s   o n e  No n - R eser v ed   ti m e  s lo t  f r o m   M r .   Liu ’ s   an d   th e   C 6   ti m etab les  t h at   o v er lap s   in   s a m e   ti m e  s lo t;  h e r e,   th e  ti m e  s lo t  h ap p en s   to   b e   T s 2   w h er e  it  i s   co lo r ed   in   b lu e.   T h is   is   s u m m ed   u p   b y :     〈 , 〉 =    , 2  ,     ( 3 6 )     w h er e  i 2  r ep r esen ts   t h e   i n s tr u cto r   w h o s e  lectu r e  w i ll  b e  s wap p ed ,   w h ich   r ep r ese n ts   t h at  f o r   Mr .   Liu ,   i n   th is   ca s e.   I n   S4 ,   n o w   s w ap   t h e  co n ten ts   o f   T S4   an d   T S2   f o r   b o th   Mr .   Liu ’ s   a n d   th e   C 6   T i m e tab les  s o   t h at  T S4   b ec o m e s   No n - R eser v ed ,   w h er e  th e  A r t   co u r s e  w ill  b e  s et  f o r   T S2 .   Fin all y ,   i n   S5 ,   s et  th e  Ma th   co u r s e  in to     th e  t i m e s lo t  T S4   f o r   b o th   Mr .   J ac k   an d   C 6   ti m etab les.   A t  th e  en d   o f   t h is   p r o ce s s ,   t h e  la s t  l ec tu r e  f o r   th e   M at h   co u r s e  w ill b e  s ch ed u led ,   s u c h   th at:   Evaluation Warning : The document was created with Spire.PDF for Python.