1.Thesis 1


 

 

 

 

 

 

Proceeding softhe 2013 ORSSA An nual Conferen cepp. 31–39

 

www.orssa.org.za/wiki/uploads/Conf/2013ORSSAConference Proceedings.pdf


ORSSA  Proceedings

 

ISBN

 

xxx-xxxxx-xxxxx-x

 

©2013

 

 

A Comparative Study of Genetic

Algorithms Using  a Direct  and  Indirect Representation in Solving the  South African  School Timetabling Problem

 

 

Rushil  Raghavjee1        Nelishia  Pillay2

 

 

Abstract

 

Previous    wor applying  genetic    algorithms   t solv th schoo timetabling proble hav generally  use a  direc representation i whic eac chromosomerepresent  timetable  directly Thi study    proposes    an evaluate  genetic algorithmemploying  an  indirect  chromosomerepresentation.  Each  chromosome  isastring  comprised   ofinstructionswhich  are  used  to  build  a  timetable.The  fitness  of each  chromosome  is  a  function  of  the  har and  soft  constraint  violationsof  thetimetableconstructedusing  the  chromosome.Tournament  selection  isused  tochooseparentswhich  the  mutationand  crossover  operatorsare  applied  toinorder  to  create successive   generations.The  performanceof  the  genetic  algorithmusing  an  indirectrepresentation(IGA)  was  comparedto  thatusing  a  direc representation(DGA)  in solving  the  school  timetablingproblem  fora  South  African  primaryand  high  school. Both  genetic  algorithmswere  able  toproduce  feasible  timetablesof  good  qualitywith the  IGA  performingbetterthan  the  DGA.  The  difference  inperformancewas  foundtobestatisticallysignificant.

 

Key  words:School  timetabling,geneti algorithms,  indirect  representations

 

 

1. Introduction

 

The  school  timetablingproblem  isan  optimizationproblem  faced  ball  schools.    It  essentiallyinvolves  the  allocationofclasses,  teachers,venues  and  other  resources  toa  school  timetableinamannersuch  thatthe  requirementsspecified  by  the  school  have  been  met A  single  meeting

 

1SchoolofManagement,InformationTechnologyandGovernance,  UniversityofKwaZulu-Natal,  Pietermaritzburg,  KwaZulu-Natal,SouthAfrica,email: raghavjee@ukzn.ac.za

2       Schoo of  Mathematics,  Statistic and  Compute Science Universit o KwaZulu-Natal Pietermaritzburg,

KwaZulu-Natal,SouthAfrica,email: pillayn32@ukzn.ac.za

 

 

31

 

between  aclass  and  ateacher thatinvolves  asubject  and  avenue  isreferred  toasa  tuple  and all tuples  specified  bythe  school  must  beal located to aperiod  onthe  timetable.    Require ments specifie by  th schoo ar divide int tw categories namel har constraints  an softconstraints.  Hard  constraints specified  bythe  school must  bemetinorder  forthe  timetable to beusable.    Soft  constraints specify  the  requirements thataffect  timetable quality The  greater the number  of softconstraints satisfied,  the better the quality  of the timetable.

 

Several  techniques have  previously  beeapplied  tothe  school  timetabling problem Abramson[1],Avella  etal.[4],and  Liuetal.[14]used  simulated  an nealing to solve the  school  timetablin gproble for  schools  in  Australia,  Ital and  Greec respectively.      Tab searc was  used  byAlvarez-Valdezetal.[3],Schaerf  [15]and  Desefetal.[10]  while Beligiannis  etal.[6]solved  them school  timetabling problem  using  a  particle  swarm optimization approach Colorni    et  al.  [9] compared     simulate annealin approach  wit  tabu    searc whe solvin th school timetabling problem  while  Jacobsen[13]comparedtabu  search  with  a  constraint  programming approach.

 

A  genetic  algorithm  is  an  algorithm  based  on  Darwin’ theor of  evolutio [11].    An  initial  popula tionofindividual siscreated  and  is then  iteratively refined  overa  number  of generations.This  process  continue suntil  either   a  generation limihas  beereache or  when  a  solutio is found.    During  each  generation,  individuals are  selected  as  parentsand  genetic  operator sareapplied  to  the  selected  parents  resultingin  the  creatio ofoffspring.    These  offspring  become individuals  in  the  new  generation.                The  most  commo methods  for  selectio of  parents  areeithe fitnes proportionat selectio or  tournament  selection.         Offsprin are  create usinggenetic  operators  suc as  reproduction,  crossove an mutation.  Beligianni e al.  [7]  andBedoya  etal.[5]have solved the school timetabling problem  usingagenetic  al gorithm with  only amutation operator.  Abramsonetal.[2]solved  an Australian school timetabling problem  usinga  paralle genetic  algorithm Wilke  et  al.  [16]solved  the  German  school  timetabling problem  wit  geneti algorithm  tha use hybri repai operators.                       Fo eac of  thes genetic algorithms,  a  direct  representation  was  used  where  each  individual  was  represented  using  a timetable.

 

This    paper    evaluate the    performanc o two    genetic    algorithms on using    a    direct  representation  (DGA and  the  second  an  indirecrepresentation  (IGA)  in  solving  the  school timetabling problem.  The  performan ceofboth  GAs  wastested  ona  South  African  primary  and high  school  timetabling  problem The  IGA  was  found  to  perfor better  tha the  DGA  insolving  these  problems.  Section  2describes  the  DGA  and  section  3the  IGA Section  4coversth methodology  use an describe th tw schoo timetabling  problems    that  th two approach eswereapplied  to Section  5provides  the results  founand adiscussion  of the results.Finally,Section  6provide sconclusions  made  inthis  study  an doutlines  ideas for future  research.

 2.    A   Direct  Representation  Genetic  Algorithm  (DGA)  to

Solvethe  School Timetabling Problem

 

This  genetic  al gorithm approach consists  oftwo  phases.    Phase  uses  a  genetic  algorithm   tosearch  fofeasible  timetables Phase  2uses  a  genetic  algorithm to  improve  the  qualit of thefeasible timetables found during  Phase  1.

 

Th population  is  comprise of  individuals  representing  a  timetable.                 Individuals  are   also referred  to  as  chromosomes  or  candidate  solutions.Each  individual is represented  using  a  two dimensional  matrix The  rows  of  the  matri representhe  periods  of  the  week  and  column srepresent the  classes.    Each  cell  stores  the  teache thatwill  teach  a  particularclass  during  aspecific  period.    The  cellwillalsostore  the  subject  thatis  being  taught as well as the  venue  (ifapplicable).    An  initia population  is  created  using  a  sequential  construction  metho (SCM) where  for  each  individual in  the  initial  population,a  group  of timetable sare  create and  thebest  (fittest)timetable  is addedtotheinitial  population The  number  of elements  in the group is referred  toasthe  SCM  sizeand  isthe  same for each  group This  value  is problem  dependentand  is  seathe  beginnin o each    run.  Each    timetable in  the  group  is  create by  firstly ordering  alllessonusing  thsaturationdegree  heuristic  [8].The  saturationdegree  is  calculated to bethenumber offeasible periods,  i.e.periods  that donot  result in hard constraintviolations,available to which the tuple  canbeallocated.  Tuples  are the nallocated to a feasible   period Ifthere  ismore  than  onfeasible  period,  the  tuple  is  allocatedtothe  period  which  results  inthe lowest  soft  constraintcost.  Ifthere  are  no  feasible  periods  availablethe  tuple  is allocated to  arandomly  selected  period.

 

Eac timetable  is  evaluated  by  countin th numbe of  constraint  violations.         A   feasible timetable is one that has  no(zero)  hard  constraintviolations.  Interms  of  timetable  quality,alowersoft constraint costindicate sabetterquality  timetable.  Thus the objective  is to minimize the softconstraint cost.

 

   For  Phas 1,  tournament  selectio is  used  when  selectin parents  and  mutation  is  the  onlygeneti operator  applied.       For  Phas 2,  two  tournament  selectio methods  were  considered,namel th standard  tournament  selectio an  varian tournament  selectio wher the selected  individual is not  always  the  fittestin dividual.   When  comparing in dividual sinvariant tournament  selection an  individual  is  selected  eithe by  its  fitnes or  by  chance Like  the standard tournament selection,  variant tournament selection  returnsa  single  parent Selection  is  wit replacement thu an  individual  ca be  chose mor tha once  as  a  parent.  The

algorithm for the variant tournament selection  is shown below:

 

Input Tournament sizetand current population P(t  <|P|)Output:Parent

 best=Individual randomly  chosen  from P

 forJ=2 to   t

3       next=Individual randomly  chosen  from population

4       n=Random  number from1to3

5       Ifn=1

6      best  =fitter  individual between  best  an next

7       Elseifn=2

8        best  =next

9    endfor

10  return best

Figure1:Variant tournament selection  algorithm

 

 

3 Note the loop begin sat 2 as the first element of the tournamen tisselected priorto the loop.

 For  Phase  1,four  mutation operator swere  tested  and  involved  searching  for tuples  that  cause constraint violations and  swapping  them  with randomly  chosen  tuples.    The  four operator swere named  1VH,  2VH,  1VNH  and  2VNH.    The  1VH  operator  searches  for  a  constraint  violating tuple  and  swaps  it  with  a  randoml chosen  tuple.    The  2VH  operator swaps  two  constraint violating tuples.    Both  these  operator suse  hill climbing  where  only  swaps  thatreduce  the  cost of the timetab learaccepted.    The 1VNH and 2VNHoperator sarsimilar  to the 1VH and 2VH but  donot  use hillc limbing.

 

For  Phas 2,  four  mutation  operator swere  also  teste and  involved   the  swappin of  tuples between  periods.    The  four  mutation  operator sconsidered foPhase  2were  a  random  swap,  arowswap  as well as the  1VH and  2VH operator sused in Phase  1 All the operator sincorporate hill climbing.

 

 3. An  Indirect Representation GeneticAlgorithm (IGA) to Solve the  School Timetabling Problem

 

   Similar  tothe  DGA,  the  IGA approach also consists  of two phases  that separately  address  hard  constraints and softconstraints.  Phase  1will attemptto findafeasible timetable  while Phase  2 (ifneeded)  will focusonimproving  the quality  of the feasible timetable found in Phase  1.

 

Each  individual in the  population is representedby  a  string  of characters The  length  of each chromosome  israndomly  chosen  tobeinthe  inclusive  range  of1and  the  maximum number  of tuples  to  be  allocated.Each  character  represents an  instruction  thatiscapable  of building  or modifying  a  timetable The  following  list  of characters  in  Table  1represent each  of the  low-level heuristics that arerandomly  allocated to each chromosome.

 

Table1:Instructionsusedbythe IGA

 

 

A

 

Allocation    –   Add    a unallocate tuple    t thetimetable

 

D

 

De-allocationRemove  an  allocatedtuple  from  thetimetable

 

1..4

 

SetofmutationoperatorsforPhase  1

 

5..8

 

SetofmutationoperatorsforPhase  2

 

The  “Ainstruction,when  called,  allocate a  tuple  with  the  lowest  saturation  degree  to  thetimetable.  Ifthere  arenotuples  to beallocated this  operator has noeffect and  is  essentially an intron,i.e.redundant code.  The  “Dinstruction  randomly selects  a  tuple thathas  already  been allocated and removesit from the timetable.  The remaining instruction sare mutation operators (discusse in  the  section  on  the  DGA)  thatmake  changes  to  the  timetabl by  moving  tuples  betwee periods If  the  timetable  is  empty,  i.e.  ther are  no  allocations,  the  deallocate  and mutation operators have   no                effect.         An                    examplof     an            instruction                      string             is ADA3DA4AA12DDDA.  The  first  instruction  executed is  “Aand  a  tupl is  allocated  to  the timetable The  “Dinstruction is then  executedand  as aresult,  the  tuple  is removed  from  the


 

timetable.        This   is  followed  by  the  “Ainstruction  and  a  tupl is  the re-allocated  to  thetimetable.    The  3”  instruction indicates that  one  of the  mutation operators,  namely  the  1VH mutation  operator,  will  be  executed.  Thi is  followed  by  a  de-allocation,  an  allocation,  the execution of  mutation  operator  “4 (2VH) 2  mor allocations,  th execution  of  mutation operators1(1VNH)  and2(2VNH),  3de-allocations and finally an allocation in struction.

 

Th initia population  is  create by   randoml generating  eac strin (individual).                   Each individual  is  evaluated  base on  the  cost  of  the  timetabl that has  been  created  using  theinstructions of the  string.    Similar  to the  DGA,  the  timetable  cost  (and  thus  the  fitness  of theindividual)  is  calculated  b counting    th number    o har constraint  an sof constraint violations.  Sincethere  is apossibility that  incomplete timetables could  beinduced,the  numberof  unallocated  tuple is  include in  th har constraint  cost i.e chromosome producing timetables that donot containall the required  tuples  arepenalized  and have apoorfitness.

 

Tournament selection  is  used  when  selecting  individuals as  parentsand  the  genetic  operators applie are  mutation  an crossover.                                                                           For  mutation,  a  single  instruction  is  selecte an is replaced  by arandomly  chosen  instruction.  For  crossover,  the  cut-and-splicecrossover  operator[12]isimplemented.    A  crossover  point  isselected  foreach  individual and  thestring  fragment sare  swappe as  shown  in  Figur 2.  Each  parent  is  selecte using  tournament  selection.                                                                           A crossover  point  in eacparentis randomly  chosen  to be between  1and  the  length  ofthe  parent chromosome Note  thatthe  last  instructionin  the  first  offspring  is  the  deallocatein struction which will result  in anincomplete  timetable being formed  and  the chromosome  will be penalized accordingly Also note  that application of the crossover  operator produces  off spring  of variable

length,  with the off spring  possiblbeing of different lengths.

 

Parent1:  AD1234AAA|DDD121ADAAA                  |=crossover  point Parent  2:  12ADDAAA343|4AD                                                                                              |=crossoverpoint Resultantoffspring  A:  AD1234AAA4AD

ResultantoffsprinB 12ADDAAA343DDD121ADAAA

Figure2:Cut-and-SpliceCrossover

 

The  Phase  1genetic  algorithmends  when  anindividual  string  produces  afeasible  timetable,i.e. atimetable  withnohard  constraintviolations.  This  feasible  timetableis  carried  over  toPhase

2  which  follows  a  similar  approachto  Phas 1.    The  objectiv of  Phas 2  is  to  improve  the

qualit of  the  feasible  timetable  found  in  Phas 1.    An  initia population  of  individuals  arerandomly  generated.                Th set   of  instructions  ar th allocatio instruction,  de-allocation instruction and  the  soft  constraint mutation operators  considered when  using  the  DGA.    Each instruction  withi an  individual  is  applie t th feasibl timetable  produced  in  Phas 1.Parentsare  selected  using  tournament selection  and  the  genetic  operatorsare  mutation and  the cut-and-splicecrossover  operator.  The genetic  algorithmin Phase  2 continue suntil  ageneration limitis reached.

 

 

4. ExperimentalSetup

 

The  main  aim  ofthis  study  istcompare  two  genetic  algorithm approaches that  use  different representations The  two  genetic  algorithm approaches describe inthe  two  previous  sections  are  each  applie to  two  South  African  school  timetabling  problems.    The  first  proble is  a

 primar schoo proble wit 19  teachers,  16  classe an 14  subjects.            A  schoo week  iscomprised  of5days  and  a  maximum of 11periods  (the  number  ofperiods  per  day  varies  foreach  day  and  for  each  grade) The  hard  (HC)  and  soft  (SC)  constraints for  this  problem  arelisted  below:

 

      Note acherclashes,  classclashes  and forsome problem  instan cesvenuclashes  (HC)

      Forall classes,  mathematics must  be taught in the morning  periods  (HC)

      Co-teaching requirements must  be met  i.e.  forcertain  lessons,  classes  are  allocated two teachers insteadofone(HC)

      Double  period  requirements must  be met(HC)

      Subjects  taughtto each class must  bee venlydistributed through out the week(SC)

 

The  second  problem  is asecondarys chooproblem  with  30classes,  40 teachers and  44  subjects. Aschool  week  is comprised  of seven  periods  ina  day  and  there  are  sixdays  ina  school  week.The hard  and soft constraints for the problem  areasfollows:

 

      Note acherclashes  orclassclashes  (HC)

      Allsubclass  and  co-teaching requirements must  be  met Subclasses  occur  when  several classes  of  the  same  grade  are  split  into  two  or  more  group with  each  group  being taught by adifferent  teacher.(HC)

      Class-period allocation preferences  should  bemet(SC)

      Teacher-periodpreferences  should  bemet(SC)

      Co-teaching-period and subclass-period preferences  should  bemet(SC)

 

For  the  DGA,  trial  runs  were conducted to determinethe  best  mutation operatortouse  as well as  the  best  geneti parameter  values  to  use.                                                                                The  1VH,  2VH,  1VNH  and  2VNH  mutation operators  were  all  teste individually  and  the  1VH  operator  performed  the  best  in  terms  offinding  feasible  timetablesforthe  secondary school  problem.    For  the  primary  school  problem,  a combination of 1VH,  2VH  and  a  random  swap  performe best  in  terms  of producing feasible timetables For  Phase  2,  a  randomswap  operator  performedthe  best  for  the  primary  school problem  whilea  combination of the  1VH operator and  the  rowswapperformedthe  best  forthe secondaryschoolproblem The listof processes  and genetic  parameter sused are istedbelow:

 

Table2:Processes  and Parameter values  used-DGA

 

 

Primaryschoolproblem

Secondary  schoolproblem

 

SelectionMethod(Phase  1)

 

Standardtournamentselection

 

Standardtournamentselection

 

Mutationoperator  (Phase  1)

 

1VH,2VHandrandomswap

 

1VH

 

SelectionMethod(Phase  2)

 

Varianttournamentselection

 

Standardtournamentselection

 

Mutationoperator  (Phase  2)

 

Random  swap

 

1VHrowswap

SCM  Size

20

20

PopulationSize

500

750

TournamentSize

10

10

Numberof  swaps

200

150

Numberof  generations

75

50


 For  the  IGA,  the  set  of instruction sused  forthe  primary  school  problem  were  A  (Allocate),D(De-allocate),2(2VNH),  3(1VH)  and  4(2VH).    For  the  secondary  school  problem,the  set  ofinstructions  used  were  A,  D,  1  (1VNH) 2  (2VNH) 3  (1VH)  and  4  (2VH).     The  parameter values  were  the  same  as the  values  used  bythe  DGA  (seeTable  2above)  and  were  determine dusin tria runs Pleas not tha th Numbe of  swaps refer to  th numbe of  swapsper formed by asing leapplication of amutation operator/instruction.

 

Bot approaches  wer develope using   Visua C++  2010.   Th rando numbe generator function  availableinC++  was  used  togenerater andom  number Thirty  runs  were  performed with  each  run  using  a  differen rando number  generator seed.  The  DGA  was  run  using  an Intel  Core  i7870CPU  @2.93GHz,  4.00GB  RAM  on  Windows  7 The  IGA was run  using  the Centerfor HighPer formance Computing[17].

 

 

5    Resultsand  discussion

 

This  section  covers  the  performance of both  the  DGA  and  IGwhen  solving  the  two  school timetabling  problems.              Thirty  run wer performed  for  eac approach.                                                                        Th succes rates indicating  the  number  of  feasible  timetables  found  over  thirty  run as  well  as  the  average  timetable quality  (average  number of softconstraint violations) is show ninthe table  below.

 

Table3:SuccessRate  andAverage  Quality

 

 

Primaryschool

Secondary  school

 

Success rate

Average

Quality

Maximum  Soft

ConstraintCost

Success

Rate

Average

Quality

MaximumSoft

ConstraintCost

DGA

60%

10.83

113

67%

4.5

20

IGA

93%

7.61

113

100%

2.37

20

 

Ascan  be seen from Table  3,the  IGA performs  farbetter than  the  DGA Hypothesis  tests  (Z-tests)  were  conducted totest  whetherthese  results  were  significant Table  4  lists  the  levels  ofsignificance,  critical  values  and decision rules for the hypothesistests.

 

Table4:Hypothesistest  conditions

 

P

CriticalValue

Decision  Rule

0.01

2.33

Reject  H0ifZ>2.33

0.05

1.64

Reject  H0ifZ>1.64

0.10

1.28

Reject  H0ifZ>1.28

 

A  single  hypothesiswatested  forfeasibility  foreach  problem,  namely,  thatthe  IGA  performs better than  the  DGA  i.e.  the  IGA  produce fewer  constraint  violations than  the  DGA.    A  Z-value  of2.9  (for  the  primary  school  problem and  3.61  (for  thsecondaryschool  problem isobtained indicating that forboth  school  timetabling  problems  the  IGA performs  better than  theDGA.               Thi was  found  to  be  significant  at  all  levels  of  significance Reason for  the  IGA performin better than  the  DGA  could  include  the  possibility  ofthe  size  ofthe  search  spacebeing  reduce when  using  the  IGA  as  there  are  fewer  combinations making  up  chromosomes than  when  using  an  indirect representation.  Further more,the  indirect representation could  alsoresul i a  less  rugge landscape  thereby  reducin the   chance of  premature  convergence. Finally,small  changes  made  in  the  space  using  the  indirect representation  may  map  to  larger


 

changes  ithe  actua solution  space,  enabling  the  GA  to  be  more  explorative These  reasons  will be investigated furtheraspart  offuture  extensionsof this  work.

 

The  timetables producedusing  the  DGA  and  IGA were compared  tothe  actual  timetablesused bythe  schools For  the  primary  school  problem,  the  best  timetable  produced by the  DGA  was feasible  with  6  soft  constraint  violations The  best  timetable produced  by  the  IGA  was  alsofeasible  and  contained3  soft  constraint  violations The  actua timetableused  by  the  school contained noclashes  but  there  was  one instan ceofadouble  period  violationnot  being  met.  In addition the double periods  had to be allocatedmanually by astaffmember.  For  these condary school  problem the  best  timetableproduced  by  both  the  DGA  and  IGA  were  feasible  and contained2 soft constraint violations.  The  actual  timetableused  by the  school  was  feasible  and also contained2 soft constraint violations.

 

 

6    Conclusion

 

This  research  lookeatusing  two  different  representations forgenetic  algorithms when  solvingthe  school  timetabling problem.  The  results  showed  thatthe  genetic  algorithm  approach using an indirect representation,where  each  individual is astring  consisting  of instructions capable  of building  a  timetable,performed far  better than  the  genetic  algorithm approach using  a  direct  representation,where  each  individual represented a  timetabledirectly.The  results  found  were statistically significant.  It is hypothesized that this  could possibly  beattributed to theuseof an indirect representation resulting in areductionin search  spacesize,asmoother  fitness  landscape and  greater  exploration of  the  search  space.    Futurere searc will  include  a  more  theoreticalanalysis  ofthe  search  area  being  covered  forboth  the  IGA  and  DGA Another possible  reasonthat  will  be  include in  future  researc isthe  fitness  landscapeof the  problems  and  how  the IGAandDGAcover this  area.

 

 

References

 

[1]Abramson,D.(1991) Constructing School Timetable susing Simulated Annealing:Sequential and Parallel algorithms.Management Science 37(1):98–113.

 

[2]Abramson,D.,Abela,  J.(1991) AParallel  Genetic  Algorithmfor Solvingthe School Timetabling Problem.  Proceedingsofthe15th   AustralianConference:   Division  ofInformation  Technology 1-11.

 

[3]Alvarez-Valdez,R.,Martin,G.,Tamarit,J.M.  (1996).  Constructing Good Solutions forthe

Spanish  School Timetabling Problem.Journal  of the Operational Research  Society 47(10):

1203-1215.

 

[4]Avella,  P.,  D’Auria,  B.,Salerno,  S.   (2007) AComputational Studyof Local Search

Algorithms for Italian High-SchoolTimetabling.  Journal  of Heuristics.13(6):543-556.

 

[5]Bedoya,  C.F.,  Santos  M.(2004).  ANon-Standard Genetic  Algorithm Approachto Solve Constrained School Timetabling Problems.ComputerAided  Systems Theory   Eurocast  2003,Lecture  Notes  inComputer  Science.  2809:  26-37.

 [6]Beligiannis,G.N.,  Tassopoulos,I.X.(2012) Solving Effectively  the School Timetabling

Problem  Using Particle Swarm Optimization.Expert  Systems  with Applications.39:6029-

6040.

 

[7]Beligiannis,G.N.,  Moschopoulos,C.N.,  Kaperonis,G.P.,  Likothanassis,S.D.,(2008)Applying  Evolutionary Computationtothe School Timetabling Problem The Greek  Case.Computer sand Operations Research.   35:  1265-1280.

 

[8]Carter,M.W.,  Laporte,G.(1996 Recent  Developments in Practical Examination Timetabling.  Practice  andTheory  of Automated Timetabling:    Lecture  Notes  in  ComputerScience 1-21.

 

[9]Colorni,  A.,Dorigo,  M.,Maniezzo,  V (1998) Metaheuristics for High School Timetabling.

Computational Optimization andApplications.  9:  275–298.

 

[10]Desef,T.,Bortfeldt,A.,Gehring,H.(2006).ATabu  Search  Algorithm for Solvingthe Timetabling-ProblemforGerman  Primary  Schools(Abstract).Proceedingsof the  International Conferenceonthe

Practice  and Theory  of Automated Timetabling  (PATAT).Online.  Available: http://www.asap.cs.nott.ac.uk/external/watt/patat/patat 04/465.ps[Cited  October

28,2013].

 

[11]Goldberg,D.E.  (1989) Genetic  Algorithmsin Search,  Optimization and Machine Learning.Addison-Westley.  ISBN 0-201-15767-5

 

[12]Goldberg,D.E.,  Korb,  B.,Deb,B (1989) MessyGenetic  Algorithms Motivation,Analysis  andFirst  Results.  Complex  Systems.3(5):  493-530.

 

[13]Jacobsen,F.,Bortfeldt,A.,Gehring,H (2006).  Timetabling at German  Schools TabuSearch  versus  Constraint  Programming.  Proceedingsof the International  Conferenceon the Practice  and Theory  of Automated Timetabling.439-442.

 

[14]Liu,Y.,Zhang,  D.,Leung,  S.C.H.  (2009).  A Simulated Annealing Approach with a new Neighbourhood Structureforthe Timetabling Problem.  Proceedingsof  GEC2009,FirstACM/SIGEVOSummiton Genetic  and Evolutionary  Computing.381-386.

 

[15]Schaerf,  A (1996)  Tabu-Search Techniques for LargeHigh-School  Timetabling Problems.

IEEE  Transaction son Systems,Managementand Cybernetics Part  A.363-368.

 

[16]Wilke,  P.,  Grobner,M.,Oster,  N.(2002) AHybrid  Genetic  Algorithm for School Timetabling.Advancesin Artificial Intelligence,Lecture  Notes  in  Computer Science.2557/2002:  455-464.

 

[17]Center for High Performance Computing.Online.  Available: www.chpc.ac.za/sun[Cited

October  28th,  2013].

 

 

 

 

เป็นเนื้อหาของบทความหรือสินค้าโดยละเอียด

กรุณาใส่ข้อความ …

Visitors: 121,232