TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.4, April 201 4, pp. 2985 ~ 2 9 9 4   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i4.4798          2985     Re cei v ed Se ptem ber 9, 2013; Re vi sed  No vem ber 1 3 ,  2013; Accep t ed De cem b e r  1, 2013   An Intelligent Course Scheduling Model Based on  Genetic Algorithm      Guofeng Qin 1 , Haibin Ma* 2   Dep a rtment of Comp uter Scie nce an d T e chnol o g y , T ongji U n iversit y , Sha n gha i 20 180 4, Chin a   *Corres p o ndi n g  author, e-ma i l : gfqing @al i y u n .com 1 , sunn y_mhb@ 16 3.co m 2       A b st r a ct   W i th the unive rsity expans ion ,  how  to maintain t eac hin g  or der usi ng li mit ed reso urces  mak e  th e   intell ig ent c our se sch ed uli n g  bec o m e  a  mu ltipl e -co n straint an d mu lti - obj ective opti m i z at io n  pr ob l e m.   Traditio nal  inte llig ent co urse  sched uli ng a l g o rith m is i neffi cient, can not s o lve curr icul u m  co nflict qu e s tion   and  me et the requ ire m e n ts  of the mo dern  university ed ucatio n mana g e ment. Given this situatio n, thi s   pap er a naly z e s  the u n iv ersity timetabl in g p r obl em,  an d e s tablis hes  a g ener al c ourse   sched uli ng  mo del ;   then  prop oses  an  i m pr oved   gen etic a l g o rit h m to sov l e  th e int e ll ige n t co urse sc hed uli n g pr obl e m . It can   me et a ll  of th e  educ atio n res o urces ’   constra i nts an d th e te a c hers ’   pers o n a l  de man d s as   muc h   as  possi ble.   T e st the perfo rma n ce of b e tw een the i m pr oved g e n e ti c alg o rith m an d  simple  gen etic  algor ith m  un d e r   different sce n a rios, the  exp e ri ment al res u lts show  that the i m pr ove d  ge netic  alg o rith m h a s b e tte r   perfor m a n ce, can sche d u l e co urses reas ona ble.      Ke y w ords : int e lli ge nt course  sched uli ng, ge netic al gor ith m ,  multi p l e -constr aints, multi-o b j e ctive         Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  With the  uni versity expa n s ion  and  the  develop men t  of edu catio n , tradition al  manu al  cou r se sch e d u ling an d co mputer-aid ed  cou r se sc he duling h a s  already ca nnot   meet the practical  need s [1]. Intelligent course sched uling  whi c h al so  ca lled Unive r sit y  Timetabling  Problem (UT P ),  is a  combin atorial  optimi z ation  proble m  that  sch e dule  cu rri cul u m effectivel y usin g limit ed  teac her,  c l ass r oom  and time resourc e s [3]. It in volvs many fa ctors and  ha s  gre a t co mplexity.   In  1975, Even.S  proved that   UTP i s   NP-complete prob lem,  ann oun c ed the  a c ad e m ic  statu s  a n d   difficulty of this sp ace-time  combi nato r i p r oble m  [4, 9].  The ge netic  algorith m (GA )  is a  kind o f  sear ch al g o rithm in spi r ed by the proce s s of  biologi cal  evolution. It ca n self-ad apt t o  glob al  o p timization  an d  often be en  use d  to find   near- optimal soluti on of optimi z ation an d sea r ch  probl em s.  It has al rea d y  widely u s ed  to re solve th e   UTP. But th e  Simple  Ge n e tic Alg o rith m (SGA ) al so ha s its li mits: rand om i n i t ialization  me thod   and fixed pro bability of cro s sover an d m u tation etc.  T hese limits ca n easily lea d  to high  colli si on  rate, prem ature and  slow  conv ergence phenomena  [5], will affe ct the result of  course  sched uling.   In ord e r to i m prove th e  efficien cy an d su cce s s ra te of GA, co mbining  with  intelligent   cou r se  sche duling  pro b l e m, this p a per im prove  the gen etic algorith m   encodin g  m ode,  initialization   method  and  cro s sover  and  mutatio n  p r oba bility. This can  sp eed  up  the   conve r ge nce  spee d, avoid prematu r e ph enom e non. The n  test the alg o rithm throu gh  experim ent. The re sult sh ow that impro v ed geneti c  a l gorithm redu ce the collisi o n rate, enh an ce   effcien c y whil e satisfy the  con s trai nts, a nd ca n solve  the intelligen t course  sche duling p r obl e m   well.       2. Intelligent Course Scheduling Model Based on GA  2.1. Intelligent course scheduling Problem Anal y s is  Intelligent co urse sche dul ing is a mul t i-dimen s io na l assi gnme n t proble m  in  which  stude nts, tea c he rs  (or fa culty menbers) are a s si gne d to course s  or cla s se s, events (individ ual  meeting s  bet wee n  stude nts and tea c he rs) are as sig n ed to classro o ms an d times. Becau s e of   its   large  scale a nd many fact ors it involvs,  it is a  compl e x work. As a probl em that must be fa ce d in   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2985 – 2 994   2986 the pro c e ss  of teachin g  in colleg e s a n d  universitie s, it is a Time  Table Probl e m  research e d  in   operation s  re sea r ch,    ha s  been   de eply   studie d  and   i s  kn own to be   NP p r obl em .  A timetable is a pla c eme n t of a set of event gs in time. A event is a combin ation of  resou r ces  (e g roo m s, pe o p le and ite m s of equipm en t), some  of which m a y be  spe c i fi ed by t h e   probl em, a n d  so me of  which  must  be   allocated  as  part of  the  solution. Tim e tabling  ha s l ong   been  kn own t o  belon g to th e cla s s of pro b lems  call ed  NP-compl ete, ie no meth od  of solving it i n   a rea s on able  amount of time is kn own [11].  The   chall eng e of time tabl e problem  is t o   sche dule  e v ents ove r  li mited re so urces  so  as  to avoid collisions and to satisfy a number of si de-constraint s . The  colli si ons  will occur whenever   a timetable re quire s any re sou r ce to be i n  two pl a c e s  at the same ti me. The time tabling proce ss  is made m o re  dif fi cult by the fact that so many  peopl e are affe cted b y  its outcome .  Timetablin g constraints are varied   an d  many. Here are some  of the mo st comm o n   types :  1) Re sou r ce  A s signm en:   A  reso urce  may  be a s sign ed t o  a  re so urce  of a diffe rent  type, or to  a   meeting. For  example, a le cture r  p r efers to teach in a particula r roo m .  2) Time  Assign ment:   A even t or a resou r ce may be assigned to a time.  3)  Time Con s traints b e twe e n  Meeting s :   Comm on exa m pleof this  class of con s traint a r e that   one pa rticul ar meeting mu st take place b e fore an othe r one.  4) Event  Sprea d :   Events sh ould be spre ad out in time.  For examp l e, no studen t should hav e  more tha n  on e exam in an y day.  5) Event  Cohe rence:   Thi s  constraint is d e sig ned to produ ce mo re orga nised an d conve n ient   timetables, a nd often run  contra ry  to “meeting spre ad ” con s traints.   6) Room  Cap a ci ties:   Th e num ber of stu dent s in a roo m  m a y not excee d  the room’ s   cap a city.  7) Contin uity:   Any con s traint s wh ose m a i n  purp o se is to  ensu r e that  certain featu r es of stu den t  timetables a r e con s tant or  predi ctabl e.  Con s trai nts shown above  can b e  divide d into “ha r d”  and ”soft” categori e s:   1)  Hard con s trai nts: A timetable whi c h b r e a ks a  ha rd constraint is n o t a feasibl e  solutio n , an d   must b e  rep a ired  or rej e cted  by the  timet abling a l gorithm  [6]. Hard con s tra i nts  in clud e  “ fi rsto rde r  co n fl i c ts”, i e  no  perso n may  be requi red  to  attend m o re than  one  m eeting at  any   time.  2)  Soft con s trai nts: Soft con s traint s a r e l e ss impo rtant  than ha rd  constraint s,  an d it is u s ually   impossibl e to  avoid b r ea king at lea s t  some  of the m . Whi c heve r  timetablin g  method i s   applie d, timetable s  are u s ually rated b y  a penalty  functio n , whi c h cal c ulate s   the extent to   whi c h a  timetable h a s violated its  soft  constraint s.  S o me  sof t  co n s t r aint s a r e  more i m po rt a n t   than others, a nd this is ofte n spe c i fi ed  wi th a priority value.     2.2. Intelligent Course S c heduling Mathematical  Model   Given co mpl e xity of intelligent co urse  sched uling p r oblem, there  is great pote n tial for  comp utationa l tech niqu es  to help  e a se  the ta sk of   university timetabling.  Firstly, we e s tabl ish  mathemati c al  model for it.  Den o te the  n u mbe r  of  we ek  of one  term  as WK, n u m ber of cl asses  as  CL, th e  numb e r  of co urse s a s  CR, the n u m ber  of tea c he r a s  TE , th e nu mb er  o f   c l ass r oo m  a s  R M ,th e  n u m be r   o f   time silce in  one we ek i s  TS. So one term ha s  TS* W K time slices, then set  POINTS = T S *WK.  A ssu me t hat  clas s  colle ct ion of  co ur se  is  12 n ,, l cl cl c ,time coll ection of  cou r se i s   12 ,, n p tp t p t , and cla s sro o m colle ction  allocated for i t  is  12 ,, n rm rm rm .   Array ClassM [CL] [POI NTS], Teac herM [T E] [P OINTS], RoomM [RM] [P OINTS] are  use d  to rep r e s ent cl ass, teach e r an d cla s sroo m  co nst r aint data mo del. They are  used to reco rd   the resou r ce allocation re sult and dete c t collisi on. For example Equ a tion (1 ).    1 c l a s s  i   ha s  be e n  a r r a nge d  c o ur s e  i n  p o i n t  j [] [ ] 0 o th erw i s e C l a ssM i j                                     (1)    So when all o cate time and  classroom re sou r ces fo r course, co nst r aint data mod e l can  be used to gu arante e  the result satisfy constr aints of t i me table pro b lem. For exa m ple:  1)  Students in th e same  cla ss  can b e  only a rra nge d one  cou r se at the same time. it is a event  spread  con s traint, we use Eq.(2) to ma ke resou c e all o catio n  meet it.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Intelligent Cou r se Sch e duling Mo del  Based o n  Ge netic Algo rith m  (Guofeng  Qin)  2987   11 [] [ ] 1 nn ij ij C l a ssM cl p t                                                                                                        (2)    2)  One tea c he r can o n ly be a rra nge d one  cou r se at the same time, we use Equ a tio n  (3).     1 [] [ ] 1 n j j Te a c h e r M i p t                                                                                                      (3)    3)  One cl assroo m can only b e  arrang ed o ne co ur se at the sam e  time , we use Equ a tion (4 ).    1 [] [ ] 1 n j j Ro o m M i p t                                                                                                                       (4)    From a bove, we kno w  cl ass,  teacher a n d  cla s sro o m  con s trai nt dat a model  can  be  used  to detect colli sion a nd re co rd data: wh en  allocate time  slice a nd cla s sroo m re sou r ce s for  cou r se,   then ch eck whether Eq uati on  (2 )-(4)  are  satisfied. If so, the res ource allo catio n  is co rrect, then   record the re sult in con s traint data mod e l;  if not, it shows that reso urce allo catio n   caus e   colli sion  and shoul d re allocate re so urces.   From the ma thematical m odel, it’s kn o w n t hat intell igent co urse  sched uling i s  multi- con s trai nt an d multi-o b je ctive   optimization p r oble m . Becau s e  of   the con s t r aints, algo rithm  efficien cy will  be ve ry lo w and  collisi o n rat e   will b e  very  high   if we  use traditional  cou r se  sched uling a l gorithm.   Ge netic alg o rith m is intellig ent heuri s tic algorithm t hat simulate  the  biologi cal me cha n ism s  of biologi cal evolution.  It’s i n telligent, pa ra llelism  and  robu stne ss while  solving com b inatorial opti m ization   p r ob lem. So we  use a daptive  genetic  alg o rithm to sol v e   intelligent cou r se  sched ulin g probl em.     2.3. Design  of GA   in Cou r se Sched u ling Problem  Since SGA  h a s its drawb a cks, e n codi ng an d ge ne tic mani pulati on mo de a n d so  on   must be  corre c tly defined while solve the  intelligent cou r se  sched ulin g probl em.     2.3.1. Gene  Encoding M ode   Gene i s  the basi c  exe c uti on unit of the  genetic ma ni pulation s . Encodi ng and d e co ding   mode affect s the expressi on of inform ation,  desi g n  and implem entation effici ency of gen e t ic   manipul ation  and the spee d of converge nce.   SGA use bi n a ry en codi ng  mode. It can not expre s s cou r se sch e d u ling  informat ion well  becau se of th e com p lexity of intelligent  cou r se sch e d u ling p r oble m . So we use n a tural e n codi n g   mode: ea ch  chromo som e  rep r e s ent cu rri culum  of o ne cl ass. Ea ch g ene of o ne chro mo so me   con s i s ts of t w o p a rts: I D  of cou r se a nd ID of   cla s sro o m. So th e pop ulation  is on e result  of  cou r se sche d u ling.The  ch romosome  structure is  sho w n in Figu re  1.      Figure 1. Chromosome Structure       2.3.2. Collision Detection  Re sou r ce all o catio n  may l ead to  collisi on. Co nstrain t  data model  can  be u s ed  to detect   colli sion. Whi l e  allo cate re sou r ce  fo r  ev ery  cou r se, we sh ould   ch eck wheth e r hard   con s trai nts  are satisfied.  If not, it shows that coll isi on exi s t and re sou r ce  shoul d be reallo cated. F o r  example, we  can u s e Equ a t ion (5)-(7) to  che c k the co nstrai nts liste d in 2.2.   11 [] [ ] 0 nn ii ij Cl a s s M c l wk                                                                                                              (5)  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2985 – 2 994   2988   1 [] [ ] 0 n j j T e ac he r M i w k                                                                                                                (6)    11 [] [ ] 0 nn ij ij R oom M r m w k                                                                                                          (7)    2.3.3. Population Initializa t ion   In the pro c e s s of popul atio n initializatio n ,  we  allocate time and cl assro o m resource s for  every cou r se  and then init the ch rom o so mes u s ing th e time and cl assro o m information.   Random initialization  m ode  will  cause lots of colli si ons, so  we im prove  the initial i zation  mode: when i n itialize the  p opulatio n, detect and  avoid  the colli sion t o  gua rante e  the Initializatio n  result is feasi b le. The improved algo rith m of  populati on initializatio n is sh own as follows:   Begin   for each co urse {   do {   allocate time s lice res o urce for c o urs e ;                        detec t c o llis i on;   } while (colli son exsits);   do {   allocate c l assr oom resour ce for  c o urs e ;   detect collisi o n;                   } while (c ollis i on exs i ts );           initialize the ch rom o so mes u s ing  re sou r ce allo ca tion informati on;          record inf o ramtio n in constraint data  model to sho w  re sou r ce s allocated  are not availa ble anymo re;   }  End    2.3.4. Fitnes s Functio n     In the evolution pro c e s s of the genetic al go rithm, fitness function determin e s th e   evolution di rection.   Th ere f ore the  fitne s s fun c tion d i rectly d e termines the  co urse  sched uli ng  optimizatio n speed.     De sign  of fitness fu nction  and fitne s s  values  cal c ul ation de pen d s  o n  soft co n s traint s.  Soft constrain t s are d enote d  as soft 1 ,... ,s oft n . Fitness functio n  is de signed a s  follo ws:     Total sco r e  o f  every soft constrait is 10 0.Se t weight  for every s o ft  c o ns traint, rec o rded   as w 1 ... w n , and  1 1 n i i w .    Re cord the  score of  soft i  a s  Score O fSoft(i),so  sco r e  of cou r se j  ca n be  cal c ulat ed u s ing   Equation (8).     1 () ( ) * n i i Scor eOfC ourse j S c o re OfSoft i w                                                                               (8)    A ssu me t o t a l  numb e r  of  c our se s of  a   cla ss i n  o ne  wee k  i s   CO UNT, so  score  of this  cla ss  k re co rd as Equatio n  (9).     1 0 () ( ) COU N T j Sc ore O f C l a ss k S c o r e O f C ours e j C O U N T                                                   (9)    And then, fitness value of  class k Adapta b ility(k)  =  ( ) 100 Score O fClass k .      2.3.5. Geneti c Manipulati on  Geneti c  mani pulation s  of the GA mainly  c ontain s  sele ction, cro ssov e r and m u tation.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Intelligent Cou r se Sch e duling Mo del  Based o n  Ge netic Algo rith m  (Guofeng  Qin)  2989 Selection:  we  use  roul ette  method, i ndiv i dual  with gre a ter  fitne s s  v a lue have a greate r   cha n ce to b e  sele cted. In orde r to  calcul ate t he  prop ortio n  of  the individ u a l's fitne s s v a lue,  record the  p opulatio n si ze as Individu alCo unt,  fitness value  of cla ss  k i s  A daptability(k).  So  prop ortio n  of the individual' s  fitness va lu e can b e  cal c ulated u s ing  Equation (10).    1 0 Pr ( ) ( ) ( ) I ndiv i du alCount i Ad ap tio n o p o rt ion k Ada p ta bi lit y k Ada p t a b ili ty i                (10)    Cro s sove r: this pap er ta ke  curriculum of   one cl ass a s  one individ u a l, so for a  g ene, we  only exch ang e the time  sli c e a nd  cla s srooms info rm ation, not the  entire  gen e. The p r o c e s s  of  cro s sove r is shown as follo ws:     Begin   find two ch ro moso me s ran domly, record ed as  C1 an d  C2;  cho o se one g ene from  C1  and C2 re spe c tively, reco rded a s  R1 a n d  R2;   if (classroom s’ type and capa city are the same )            exchang e cla s sroo m of R1 and  R2 ;  else {                   realloc a te c l ass r oom for R1 and R2;                   detect collision;  }  End  Mutation: mutation will mut a te gene of chrom o some. Mutation ope ration is cond ucive to  increa sing div e rsity of the p opulat io n.The  process of m u tation is:   Begin   find one chro moso me a s  C1, and  cho o s e on e gen e as R1;  define an a r ray temp [] to  save the course’ s  ideal tim e  slices a nd 0 - 19;   cho o se one n u mbe r  from temp [] rando mly, reco rd correspon ding  gene a s  R2;  detect collisi o n betwe en R1 and R2;  if (collisi on not exsit )            exchang e cou r se and  cla s sroo m of R1 an d R2;         els e              mutation  end;   End    Control pa ra meters: cont rol pa ramete rs  mai n ly contain cro s sover proba bi lity and   mutation pro bability. Fixed crossove r  and mutati o n  prob ability will de crea se  the diversity o f   evolution po pulation, lea d  to local o p timal solutio n  [2]. So we use ad aptive cro s sove r and   mutation probability, shown in Figure 2.     1 c 1m a x ma x 2 2m a x m ma x C r os s o v e r  P r oba l i t y  P () () M u tatio n  P r o b al ity  P l av g av g l av g l av g av g av g kf f kf f f f ff kf f kf f ff ff     Figure 2. Con t rol Param e te rs      P c  and P m  re pre s ent s the  cro s sove r probability and  mutation p r o bability.f l  is the bigge r  fitness value  of the two  cro s sove r ind i viduals,  f re pre s ent s the  variation of individual fitness  value, k 1  and  k 2  are rand o m  numbe r be tween (0, 1) [10].  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2985 – 2 994   2990 2.3.6. End Condition   It’s very impo rtant that  wh en to te rmina t e t he GA. If  GA is te rmin ated p r ematu r ely, the   algorith m  ha s not been con v ergen ce, the  results ar e n o t optimal; when termi nate d  too late, time   and  hardware re so urce s  will be  wast e d  [8]. The r efo r e, we  set two en d conditi ons of the  ge netic  algorith m :   1)  Whe n  the averag e fitness value of popu la tion meets t he expe ctatio n, the algorith m   end s;  2)  The pop ulatio n evolutiona ry algebra  rea c h to the larg est alge bra, the algo rithm  end s.    2.4. Algorithm Flo w   of Intelligent Course Scheduling Model   Geneti c  algo rithm sim u lat e s the  genet ic pr ocess b y  sele ction  operation, crossover  operation an d mutation operatio n. Individuals a r e se lecte d  base d  on the fitness value, ma king   individual tha t  have gre a ter fitness val ue have  a  g r eate r  chan ce to exist. Evaluating ea ch   individual  through  fitness f unctio n  reali z e the  “sur viva l of the fitte st”. After g eneti c  m anipul atio n,  the individual  colle ction form the next generation po pulation, then  put them into the next ro un d   of evolve.  Acco rdi ng to geneti c  mani pulation s , wo rkflo w  of intelligent co urse  sched uling m odel  based on GA  is as follo ws:  1)  Cou r se  sch edulin g  solu tion initiali za tion:allocate  re so urce s for  co urse , and  re co rd   informations  in;  2)  Comp ute fitness value of popul at ion u s ing the fitness functio n ;  3)  Cho o se bette r individual s u s ing roulette  method, and   gene rate the  next   gen erati on;  4)  Carry o u t ge netic m anip u l a tions to g e n e ra te  ne w in dividual s u s ei ng the  ada ptive crossove r  and mutation  prob ability ;  5)  Jud ge wh eth e r algo rithm meet the end  conditi on s. If so, we get the global opti m al solutio n ,  jump to 7); if not, jump to 2);  6)  Get info rmati on from th e  popul ation,  dec o d ing the informatio n and output the sch eduli n g   result;  7) Algorithm  en ds.   Flow cha r  of of Intelligent Cou r se Sch e duling i s  sh o w n in Figu re  3.          Figure 3. Wo rkflow of Intelli gent Co urse  Sched uling B a se d on xx GA  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Intelligent Cou r se Sch e duling Mo del  Based o n  Ge netic Algo rith m  (Guofeng  Qin)  2991 3. Experient  and An aly s is  To prove the reliability of the algorithm , we  conduct  simulation experiment to validate   the alg o rithm .  Experiment  is  divided i n to three   mo d u les:  pro b le m sp ecify, course  sche d u ling  para m eter  se tting and perf o rma n ce com pari s on.     3.1. Problem Specif y   Acco rdi ng to  establi s h ed  mathemati c al   model  an d a nalysi s  of time table po ble m , while  taking i n to a c cou n t the  different e d u c ati on sy stem , we sh ould  spe c ify the pro b l e m: cla ssify t h e   cou r se,pa r tition the time and sum m ary t he co nstraint s.      3.1.1. Cours e  Classific a ti on  Different  kin d  of course  ha s different p r i o rity  and  feat ure,  we  ca nn ot take  them  as th e  same. In this pape r, the co urse is divide d into six  levels of the class A-F. The priority of courses  incr ea se f r om  clas s A  t o  cl as s F.  Cla ssif i cat i on of  c o u r se s is  sho w n  in Table 1.       Table 1. Co urse Cl assification   Class Name   A PE  class 、 experimental course  B  Public basic course  C Compulsory   course  D Selective  course   E  Professional practice course   F  Public elect i ve course       3.1.2. Partition of Time Slice   We  divide  on e day i n to five time  slices.  So on e  wee k   contai ns twenty five time sli c e s   while Saturd ay and Sun day are not  used to arrange cou r se,denote d  as  S0-S24. So one   chromo som e  contai ns 2 5  g ene s. Time sl ice pa rtition is sho w n in Ta ble 2.      Table 2. Time  Slice Partition    Monda y Tuesda y Wednesda y  Thursda y   Frida y   morning   S0 S4  S8  S12  S16  S1 S5  S9  S13  S17  afternoon   S2 S6  S10  S14  S18  S3 S7  S11  S15  S19  evening S20  S21  S22  S23  S24      3.1.3. Cons tr aint Con d itio ns   Becau s e  of the ma ny ele m ents  and th e co nst r ai nt s  the time table  pro b lem invo lved, we   sho u ld arra ng  the curriculu m  rea s on able  to satisfy the con s traint s.   Con s trai nts  contain h a rd  a nd soft con s t r aint.   Ha rd constraint sho u ld  be sati sfied  when  alloc a t e  t i me  sli c e a nd  cl as sro o m  re s our ce s f o r  co urs e s.   I t gu arantee s   the cor r e c t ness  of t h e   result [7]. Hard con s trai nts  are sho w n in  Table 3.       Table 3. Ha rd  Con s traint s    Hard Co nstraints  1  The same class can onl y  be a rra nged one cou r se at the same time   2  The same teach e r can onl y  b e  ar ranged on e cour se at the same time  3  The same classroom can onl y  be  arrang ed one co urse at the same  time  4  The classroom capacity   needs to  meet the re quire ments of the cou r se  5  T y pe  of classroom meet the nee d  of course    6  Class A courses  must be arra nge d in section 3-4 of the morning o r   afternoon   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2985 – 2 994   2992 Soft constrain t  is to meet humani zed  req u ire s   of different factors, a nd sh old be  satisfied  as far a s  po ssible to ma ke  the result more  hum ane. Soft const r ain  are sho w n in  Table 4.       Table 4. Soft Con s trai nts    Soft Constraints   1  Different times of  one course in on e week should b e  in different da ys   2  Tr y to ar range co urses in their best time slice s   3  Classroom capacity  should matc h w i th t he deman d, to avoid resou r ce  w a ste     4  Tr y to ar range t h e course in the ideal building  5  Tr y to ar range t h e course on the i deal floor  6  Different times of  the same course   should be arra n ged in the same  classroom       3.2. Cours e  Scheduling  Parameter Setting   Acco rdi ng to the actu al nee d, param eters  of the impro v ed geneti c  a l gorithm  can  be set,  as sho w n in  Table 5.     Table 5. Para meter Setting   Parameter  value  Largest algebr a   1000   Ideal fitness valu e  90  Crossover prob a b ility   Self-adapting   Mutation proba bility   Self-adapting       3.3. Perform a nce Compa r ison   To ma ke t h e  simulat i o n  r e sult s mo re  conv in cin g ,  w e  t a ke  co mp aris on ex p e ri ent  usi n g   improve d  ge netic alg o rith m and SGA to solve the i n telligent cou r se  sched ulin g prob elm. Then  comp are the  performan ce  of them in three  as pe cts: only cro s so ver and m u tation ada ptively;  only initialize  the po pulati on with  collision dete c t an d cro s sover  and m u tation  adaptively a nd  initialize the p opulatio n with  collisi on dete c t at the sam e  time.  While only crossover a nd mutation ada ptively in  the  improve d  gen etic algo rithm ,  fitness  value of po p u lation  comp arison b e twe en imp r oved  geneti c  alg o r ithm an d S G A is  sho w n  in  Figure 4.          Figure 4. Performa nce Co mpari s o n       While only initialize the population  with co lli sion dete c t in the improved GA, performan ce  comp ari s o n  b e twee n impro v ed GA and  SGA is sho w n in Figure 5.  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 123 4 5 67 8 9 1 0 1 1 Algebra Fitness  Value improved GA SGA Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Intelligent Cou r se Sch e duling Mo del  Based o n  Ge netic Algo rith m  (Guofeng  Qin)  2993     Figure 5. Performa nce Co mpari s o n       From  Figure  4 and Figure 5,  we find that adaptive cros sover and  mutation probability   can  ma ke th e ge netic al gorithm  conv erge s fa st e r , and  op ulati on initiali zati on  with  colli sion  detectio n  will  make the  result h a s  a  better fitne s s value. Both  of them ca n elevate th e   perfo rman ce  of the genetic algorithm.   While  solvin g the intellig ent cou r se  sched uling p r oble m , if th e improve d  geneti c   algorith m  cro s sover  and  m u tation ad apti v ely and initia lize the  pop ul ation with  coll ision  dete c ts  at  the same tim e , the algorit hm will conv erge faster  and get a better result  then simple genetic   algorith m  as  sho w n in Fi g u re 6. Fin a lly we c an con c lud e  that the improve d  g enetic al go rithm  has b e tter p e rform a n c e t han si mple  geneti c  al go rithm while  solve the intelligent course  sched uling p r oblem.           Figure 6. Performa nce Co mpari s o n       4. Conclusio n   Intelligent co urse  sched uling is a very i m porta nt pa rt of university teachi ng. T r aditional   cou r se sche d u ling metho d  is inefficient , has hi gh  collision rate and  cannot allocate  teaching   resources reasonably. All of these factors w ill affect the teachi ng quality of university.  Analyzing the characteri stics  of intelligent  course  scheduling pr oblem  and  combined   with ch ara c t e risti cs of g enetic alg o rit h m, this  pap er use gen e t ic algorithm  to resolve  this   probl em. Me anwhile imp r ove the SG A aiming  at  the limits  of it, find adaptive ge n e tic  manipul ation  mode an d po pulation initial i zation meth o d  with colli sio n  detect.   The exp e rim ent re sult s show th at, the  improved  geneti c  alg o rithm ca n sol v e the   intelligent cou r se  sche dulin g pro b lem in  a ce rtain exte nt, redu ce th e wo rkl oad of  acad emi c  st aff.  It can play a very importan t  role in intelligen ce of the   university educatio n mana gement an d  ha s  a certai n pop ulari z ation val ue.  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 123 45 6 7 8 9 1 0 1 1 Algebra Fi tness Value improved GA SGA 0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 0. 8 0. 9 1 123 45 678 9 1 0 1 1 Al ge br a F itn ess  Va lue im pr ov ed  G A SG A Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2985 – 2 994   2994 Referen ces   [1]  Z ong W e i. Res earch a nd R e a lizatio n of  Un iv ersit y  T i metabl e S y stem A l gor ithm.  C o m p u t er Si mu l a tion.   201 1; 28(1 2 ): 389-3 92.   [2]  Lia o  Yu an, Hu ang Qi n, Gao  Pei x i a . Appl ica t ion of  S e lf-ad aptive Ge netic  Algor ithm Bas ed o n  T h ree - dime nsio n Co d i ng i n  Curric u lu m Schedu lin g S y stem.  Co mp uter and Mo der ni z a ti on . 20 08; (12): 23-2 8 .  [3]  Li Yu ji, Lu  Cai w u,  Li u Guan.  A ppl icatio n of  Ant-colo n y  Ge netic Al gorithm  in Smart C our se sche dul e   S y stems of Co l l eg es.  Modern Electron ics  T e chni que . 2 012;  (14): 121-1 23.   [4]  A Schaerf. A surve y   of autom ated timetab l i n g.  Artificial Inte lligence Review . 1999; 87- 127.   [5]  Z hu Jian bin g , Li Z han hu ai, Z hao N a . Rese a r ch on the Pro b lem of Auto-c ompos ing T e st Paper Base d   on H y br id Gen e tic Algor ithm.  Co mp uter Si mulati on.  20 09; (5): 328-3 31.   [6]  R Le w i s,  B Pa echter.  App lica t ion of the Gro upi ng Gen e tic  Algorit h m  to U n iversity C ours e  T i metabl in g.   In proce edi ngs  of the 5 Inter n at ion a l C onfer ence  on R e ce nt Advanc es  i n  Soft Computi n g. 200 4; 18 9- 194.   [7]  Jian  Ni, N i ng- Ning  Ya ng. Ge netic Al gor ithm   an d its A ppl ic ation  in  Sche d u lin g Ststem.  TELKOMNIKA  Indon esi an Jou r nal of Electric al Eng i ne eri ng.  2013; 1 1 (4): 1 934- 193 9.   [8] Gotlieb.  T h e Constructi on o f   Class-T e ach e r  T i meta bles.  Proce edi ng  IF IP Congr ess, Amsterdam .   196 3: 73-7 4 .  [9]  S Even, A Itai, A Shamir. On T he complex i t y   of timeta ble   and  multic om modit y  fl o w   pr obl ems.  SIAM  Journ a l on C o mp utin g . 197 6; (5): 691-70 3.  [10]  Xi a Bi ng. A  N e w  Ge netic A l gor ithm  an d Its App licati on  i n  Eva l uati n g   Chor us C ours e . 20 13;  11(8) :  451 7-45 22.   [11]  EK Burk, KS Jackson, JH Ki ngston, RF  W eare. Au tom a ted Un iversit y   T i met abling: T he State of th e   Art.  T he Comp uter Journ a l.  1 997; 40( 9): 565 -571.     Evaluation Warning : The document was created with Spire.PDF for Python.