An Immune-Based Approach to University Course Timetabling:Immune Network Algorithm

Muhammad Rozi MalimFaculty Info. Tec hnology &Quantitative Science, UiTM40450 Shah Alam, Malays ia

rozi@tmsk.uitm .edu .my(Te l: 0 19-2 124374)

Ahamad Taj udin KhaderSchoo l of Computer Science

Univ. of Science MalaysiaI 1800 Penang, Malaysia

tajudin @cs.usm.my(Te l: 04-6533646)

Adli MustafaSchoo l of Math. Science

Univ. of Science Malays iaI 1800 Penang, Malaysia

adli@cs .usm.my(Te l: 04-6533968)

Abstract- The university course timetabling is knownto be a highly constrained optimization problem. Themain difficulty is to obtain a conflict-free schedulewithin a limited number of timeslots and rooms. Manydifferent approaches, including evolutionary algorithms,tabu search, simulated annealing, and their hybrids aredeveloped for solving many different types of coursetimetabling problems. The immune network algorithm,an algorithm insp ired by the immune system, hassuccessfuIIy been applied to fault recognition, dataanalysis, and optimization. This paper presents animmune network algorithm for the university coursetimetabling with the ma in objective to show that thealgorithm may be tailored for educational timetabling.The experimental results, using three benchmark coursedatasets, have significantly shown the effectiveness of thealgorithm by producing good quality course timetables.For future work, other artificial immune algorithms,such as negative selection, will be applied to universitycourse timetabling using the same course datasets.Keywords - Artificial Intelligence; Course Timetabling;Artificial immune system; Immune Network algorithm.

l.INTRODUCTION

University course timetabling problem is known tobe a highly constrained combinatorial optimizationproblem (NP-hard). The problem is periodically facedby virtually every college and university in the world.Usually it involves taking the previous seme ster 'stimetable and modifying it so it wiII work for the newsemester. The course timetabling problem (CTP) canbe viewed as a multi-dimensional assignment problem[1]. In a timetable, a number of courses are assignedinto classrooms and a limited numb er of timeslots(periods of time) within a week. Given a set ofcourses, a set of lecturers, a set of timeslots, a set ofroom s, and a set of student enrollments to courses, theproblem is to assign lecturers to courses, courses totimeslots, and courses to room s satisfying a set ofhard and soft constraints. The main difference fromexamination timetabling that makes the CTP morecomplex is that in course timetabling there cannot bemore than one event per room, but in examinationtimetabling there can be more than one exam.

Conflicting objectives and the changing set ofconstraints in different institutions makes the coursetimetabling problem very challenging. Many differentapproaches, including evolutionary algorithms (EA),tabu search (TS), simulated annealing (SA), and theirhybrids are developed for solving many differenttypes of course timetabling problems.

Artificial immune system (AIS), a new branch ofArtificial Intelligence [2], is a new intelligentproblem-solving technique that being used in

1-4224-0220-4/06/$20 .00 © 2006 IEEE.

optimization and scheduling problems [10]. AISshave been more successful than genetic algorithms(GA) and other methods in pattern recognition,computer and network security, and dynamic tasksscheduling due to the applicability features of naturalimmune systems. Furthermore, the solutions producedby the AIS are observed to be robust than solutionsproduced by a GA [11].

This paper presents an artificial immune algorithmcalled immune network algorithm for universitycourse timetabling (lNACT). The main objective is toshow that the algorithm (INA) may be tailored forsolving course/lecture timetabling problems. Anotherobjective is to show that INACT is an effectiveoptimization algorithm; capable of producing goodquality course timetables. Three benchmark coursetimetabling datasets have been used to implement andtest the algorithm. The experimental results using thedatasets have significantly shown that INACT is aneffective optimi zation algorithm; has successfullyproduced good quality course timetables with ' low'fitness values for most trials and datasets.

2.COURSE TIMETABLING PROBLEM

Course timetabling problem is a specific case of themore general timetabling problem. At its simplest,course timetabling is the problem of scheduling a setof events (lectures, tutorials or labs) to a set ofclassrooms in a set of times lots, and taught by a set ofteachers, such that no student or teacher is expected tobe in more than one room at the same time and thatthere is enough space available in each classroom forthe number of students expected to be there. The setwo main (hard and soft) constraints, and many others,combine to make course timetabling a classically hardproblem to solve.

Hard constraints must be satisfied in order toproduce a feasible timetable, whilst violation of softconstraints should be minimized. The main hardconstraints in course timetabling are usuallyrepresented by the following:

i) A teacher or student can only attend one event ata time.

ii) A teacher must not be assigned to events in thetimeslots during which he/she is unavailable.

iii) The numb er of timeslots that assigned to eachevent must equal to the event's weeklyfrequency.

iv) Two events of the same course must not bescheduled at the same timeslot.

v) The number of events occurring simultaneouslyin a certain timeslot must not exceed the numberof available rooms in that timeslot.

vi) A room can only host one event at a time.

Individual institutions may have their ownspecialized hard constraints based on their needs andrequirements. Any timetable which fails to satisfythese constraints is deemed to be infeasible.

Soft constraints are generally more numerous andvaried and are far more dependent on the needs of theindividual problem than the more obvious hardconstraints. It is the soft constraints which effectivelydefine how good a given feasible solution is so thatdifferent solutions can be compared and improved viaan objective (fitness) function. The common softconstraints in course timetabling are:

i) Each teacher should be assigned to theirpreferred courses.

ii) Events of the same student group should beassigned in consecutive timeslots.

iii) All tutorials or lab sessions of any course shouldoccur later in the week than the week's firstlecture on that course.

iv) An event should (or should not) take place in acertain timeslot.

v) There should be sufficient seats in each room tohouse all the students present.

vi) Events are assigned to rooms in such a way thatthe room utilization can be maximized, or spareseats in each room are minimized.

The course timetabling problem can be seen asconsisting of three subproblems; 'course-teacherassignment', 'event-timeslot assignment', and 'event­room assignment' [13]. In 'course-teacherassignment', the teachers (lecturers and tutors) arescheduled to a number of events in all the courses; in'event-timeslot assignment', all events for all thecourses in all student academic programs arescheduled into a fixed number of timeslots; and in'event-room assignment', these events are assigned toa fixed number of rooms. Hence, in a coursetimetabling problem, an assignment is an ordered 4­tuple (a, b, c, d), where aEE, bE T, cER, and dEP. Anassignment has the straightforward generalinterpretation: 'event a starts at timeslot b in room c,and is taught by teacher d'. For some institutions, theallocation of courses to teachers is carried outmanually, and the allocation events in a given timeslotto rooms is a secondary problem (the number ofrooms may be large) and can be done later as aseparate activity. For real-life situations, these threesubproblems can be solved separately.

Malim et al. [13] presented a general model foruniversity course timetabling. The model may be usedto formulate various kinds of course timetablingproblems as 0-1 integer programming. The paper hasconsidered all possible hard constraints and softconstraints for course timetabling. This general modelwill be used to formulate the three benchmark coursetimetabling problems before applying the INACT.

2

3.ARTIFICIAL IMMUNE SYSTEM AND IMMUNE

NETWORK ALGORITHM

The 'artificial immune system' is an approachwhich uses the natural immune system as a metaphorfor solving computational problems, not modeling theimmune system [14]. The main application domainsof AIS are anomaly detection, pattern recognition,computer and network security, fault tolerance,dynamic environments, robotics, data mining,optimization, and scheduling.

The 'immune system' (IS) can be considered to be aremarkably efficient and powerful informationprocessing system which operates in a highly paralleland distributed manner [9]. It contains a number offeatures which potentially can be adapted in computersystems; recognition, feature extraction, diversity,learning, memory, distributed detection, self­regulation, threshold mechanism, co-stimulation,dynamic protection, and probabilistic detection. Fromthe perspective of information processing, it isunnecessary to replicate all of these aspects of the ISin a computer model, rather they should be used asgeneral guidelines in designing a system.

There are a number of different algorithms that canbe applied to many domains, from data analysis toautonomous navigation [3]. These immune algorithmswere inspired by works on theoretical immunologyand several processes that occur within the IS. TheAISs lead to the development of different techniques,each one mapping a different mechanism of thesystem. For examples, the Artificial Immune Networksas proposed by Farmer et al. [7], the Clonal SelectionAlgorithm proposed by de Castro and Von Zuben [5],and the Negative Selection Algorithm introduced byForrest et al. [8]. The immune network models aresuitable to deal with dynamic environments andoptimization, algorithms based upon the clonalselection principle are adequate to solve optimizationand scheduling problems, and the negative selectionstrategies are successfully applied to anomalydetection.

CLONALG [5] is the most abstraction of clonalselection algorithm. de Castro and Von Zuben [6]presented an AIS combining CLONALG with theimmune network theory introduced in Jerne [12]. Thismodel named aiNet has been successfully applied toseveral data compressions and clustering applications.The same rationales that led to the development ofCLONALG were motivations for the implementationof an optimization version of aiNet [4]. aiNet is anextension of CLONALG with steps involving theinteraction of the network cells with each other. deCastro and Timmis [4] presented an immune networkalgorithm for multimodal function optimization usingthe optimization version of aiNet.

3.1 Immune Network Theory

The immune network algorithm (INA) is based onJerne's idiotypic network theory [12]. According tothis theory, immune cells have portions of theirreceptor molecules that can be recognized by otherimmune cells in a way similar to the recognition of aninvading antigen. This results in a network ofrecognition between immune cells. When an immune

cell recognizes an antigen or another immune cell, itis stimulated. On the other hand, when an immunecell is recognized by another immune cell, it issuppressed. The sum of the stimulation andsuppression received by the network cells, plus thestimulation by the recognition of an antigencorresponds to the stimulat ion level S of a cell.

3.2 Immune Network Algorithm for CourseTimetab ling (INACT)

Figure I shows the INA developed for the coursetimetabling problems. This algorithm, called INACT(Immune Network Algorithm for CourseTimetabling) , was developed based on the generalimmune network algorithm proposed by de Castro [3]and the optimization version of aiNet developed by deCastro and Timmis [4].

4 .B ENCHMARK DATASETSThe three course timetabling datasets used in the

implementation are available on Internet fromhttp://www.diegm.uniud.it/schaerf/projects/coursett.

These datasets are the real-world course timetablinginstances from the School of Engineering at theUniversity of Udine, called Schaerf datasets. Thesedatasets provide a reasonable benchmark problems forcomparison with other approaches or algorithms. Thedatasets (and characteristics) are shown in Table 1.

TABL E ICO URSE DAT ASETS AND CHA RACTERISTICS

1. Initialization :initialize a network/population of'immune celb (feQ:,ibls timetables}for eQch immune cell (course timetable}

randomlY J616ct courS6 one by oneassign lectures (one by one ) olthe course to random timeslotsand rooms (JQti-ttVing all hard constra int s)ifno idenn'cal immune cells (duplicat e course timetab18J)

add immune cell (COUYJ6 timetable) to the pop ulationelse eh"min ate immune cell (COU.rJ6 timetable}

2. Population loop :for each n6two rk {gen eration} ofim mune cells (fiaJible nmetobles)2,1 Network interactions and Stimulatio n :

for each immune c,ll {course tlm'tabl,)d,t,rmin, th,jitn.'JJ of tmmune c,ll via afimessfuncnoncalculat' th, stim ulation l,v,l ofimm une c,ll (courJ' timetable}(, tim. lotion 1••• 1= Jlji tnm)

determine th, total stimulation ofth, n'tw ork (population)for 'ach imm une c,ll (courJ' timetable}

calcz.llat' th, In"mz.llan'on probability(In'mz.llan·on probab2'Uty =Jnmz.llan·onltotal In'mulan'on)

2,2 MetadjJnamics (ktigens and Genetic variations) :for ' ach immune c, ll {course n'm' tabl, )

cloning - g,n,rat' a number of clones(nz.lmb,r ofclones = population J'iz, ,>''Jtimulatfon probability)for ' ach cIon'

determine th, mutation raM{m utation rat, =1- stimulation probabiUi}')g,n,rat, a random probabiUtyifa random probability <:;=mutation raM

mutate - g,n,rat' a n, w non-identical im m une c, ll{non-dup licate course n'm'tabl,)mutation =fa tlz.lr,whil, mutation =fa ilz.lr,

selecta course at randomreassign all Iectures to random timeslots and best roomJifall hard oonnrainn ar, Jan'Jji'd & no duplicaM nmetobtes

mutatio n =J UCC' J J

determine th,jitn.'JJ ofth, n,w cIon'ifth,jitn'JJ (n,w cIon,) :=- th,jitn'JJ {or iginal clone}

mutation =failz.lr, . and r'J,t th, reassignmentend whz'l,

,lJ, (no mutation} assign a larg,jitn'JJ to immune c,ll [timetable }2,3 Network djJnamics 6mmune cells and antigens interactions.and~

update}:gath,r all immune c,llJ (currmt population and clonedc~~~Jon immune c,llJ according to stimulation l,v,l {descending order}J,l ,ct th, best (high stimulation) immune c,llJ (fiaJibl, COUr..B~~

(numb,r ofseleoted imm une c, llJ =n'tw ork or pop ukmon J'iz')

update th, n'tw ork {population} ofimmun, cdlJ { simetables} with th,J,l,ct,d c,llJ

3. CJc1, :r' p ,at St,p 1 until a given conv,rg,nc, or Jtopping criterion is m, t.

Fig. I: Immune Network algorithm for CourseTimetabling (CSACT)86 .25%

92 .92%

3949

'- ~o <U. -5

o '"Z <Uf-

207223

4420

201212

4652

'- '"o ~. ...o ::Z 0

U

2

5 .IMPLEMENTATI0N

First of all, before implementing the algorithm, thecourse timetabling problem may be formulated as 0-1integer programming model. The model would assistin encoding the algorithm into C++ programmingcodes.

Each of the datasets comes in five files; course.datcontains the information about the courses (course,teacher , number of lectures, minimum number ofdays, and number of students) , periods.dat containsthe list of timeslots of the timetabling horizon (day,start time, and end time), curricula.dat contains theinformation about groups of courses that sharecommon students (group, size, and members) ,constraint.dat contains additional constraints abouttimeslot unavailabilities (course, and unavailabletimeslots), and room.dat contains information aboutrooms (room, and size). The ' occupancy ' indicates thepercentage of timeslot-room required to schedule allthe lectures.

3 56 13 20 4 252 51 96 .92%5.J Math ematical Model

Using the general model [13], the formulation may becarried out as follows:

Five hard constraints are considered for all datasets:i) All lectures of all courses must be scheduled.ii) Two distinct lectures cannot take place in the

same room in the same timeslot.iii) Lectures of courses of the same group

(curriculum) must be all scheduled at differenttimeslots.

iv) Lectures of courses taught by the sameprofessor must be scheduled at differenttimeslots.

v) Lectures of some courses must not be assignedto certain timeslots as given in course-timeslotrestriction matrix.

Three soft constraint are considered for all datasets.These constraints will be used to evaluate thefitness value of each feasible timetable:vi) The number of students that attend a course

must be less than or equal to the number ofseats of all rooms that host its lectures.

3

2:Z~l2:~~lX(ci,tj,rk) = 0

LZ~lxC(Ci,Cj) = 0

L~~lxp(Ci,Cj)==O

vii) The lectures of each course must be spread intonot less than a specified minimum number ofdays. Each course that assigned to less than theminimum number of days will be incurred apenalty of 5.

viii) The daily schedule of lectures of the samegroup (curriculum) should be as much compactas possible, avoiding gaps between lectures.Each gap will be incurred a penalty of 2.

- Since there are five sets of variables (course,teacher, group, times lot, and room), only thematrices course-teacher preassignment, course­group allocation, course-timeslot restriction, group­conflict, teacher-conflict, and course-timeslot-roomassignment need to be constructed; the first five areinput matrices and the other is the output matrix(timetable). The course-teacher assignment hasbeen carried earlier and given in course-teacherpreassignment matrix.

- The 0-1 integer programming model (course­timeslot-room assignment) for each of the datasetsmay be formulated as follows:

minimize I~~l x(c., r j ) + 5 X (I7~1 x(c i »d;)) +

(

n4 n, -1 n, b ik b jk J2x Lk=lLi=l Lj=i+1-·_· X ( Ci ,c j ,t(c) )

Si S j

+ (total violations of hard constraints) x 1000; (1)

subject to 2:7:1 x(ci , t j) = 0 (2)

(3)

(4)

(5)

(6)

all variables are integers 0-1;

where ~C;,1j)==L;l rij . Si -nc(rj), if :I7~1 rij . Si >

nc(rj) (0 otherwise); x(c i , d i ) == 1 if the numberof days assigned for course c, > d, (0 otherwise);

x(ci,cj,l(c)) = 1, If(cj

) -f(cj) 1= 2, t(cj

) indicates

the assigned timeslot for event c.; c, and Cj belong

to the same group; x(c i , t j) == 1 if L~~l tij < Ii ;

xc(ci,c j)==1 if 2:7:~12:~~i+ltik·tjk·dij>0;

and xp(ci,c j ) == 1 if L7:~lL~~i+ltik ·t jk 'eij == 1.

5.2 Implementation ofthe INACT

For each dataset, the Immune Network Algorithm(INACT), presented in Figure 1, has beenimplemented as follows:

Initial timetables:Ten (10) initial feasible timetables are generated

using a simple random selection algorithm, i.e. eachcourse is selected at random and all lectures of thecourse are assigned to random selected timeslots and

4

rooms, satisfying all hard constraints. However, thethird hard constraint (group-clashing) is relaxed(considered as a soft constraint) since it is almostimpossible to generate 10 initial feasible timetablesthat satisfy all five hard constraints. The third hardconstraint will be satisfied during the optimizationprocess (cloning and mutation). For each group, ifthere are lectures that scheduled at the same times lot,a penalty of 1000 will be incurred. For the thirdinstance (with highest occupancy rate), the secondhard constraint (room-clashing) is also relaxed inorder to produce the initial feasible timetables andwill be satisfied during the optimization process.

Population loop:Network interactions and stimulation: The fitness

value of each timetable in the current population isevaluated via a fitness function. This functionrepresents the total violations of the soft constraints.Since three soft constraints are considered, the totalviolations is equal to the number of students without aseat, plus the number of courses that assigned to lessthan the minimum number of days multiply by 5, plusthe number of gaps between lectures of the samegroup on the same day multiply by 2, and plus thetotal violations of the hard constraints multiply by1000. Then the stimulation level of each timetable isevaluated by taking the inverse of the fitness value.The stimulation probability is directly proportional tostimulation level; equal to stimulation level divide bythe total stimulations of the population.

Metadynamics (Antigens and Genetic variations):Each of the timetables is selected for cloning andmutation. Good timetables (high stimulation/lowfitness) will have more clones than bad ones. In thecloning process, the number of clones is equal topopulation size multiply by stimulation probability.Each cloned timetable will be mutated to produce anew timetable. For a population size 10, on average,the number of clones generated in each generation isequal to 10. But not all clones will form a newpopulation for the next generation, depending on thestimulation level (fitness value) and the mutation rate.

The mutation operator, based on a mutation rate,works by taking one course at random and reassignall lectures of the course to randomly selectedtimeslots and best rooms, always maintaining afeasible timetable. The mutation rate is equal to oneminus the selection probability of the current clonedtimetable. A random probability is generated, then themutation is performed if the random probability is lessthan mutation rate. Since the selection probability issmall, on average 0.1 for population size 10, this givea high mutation rate for each immune cell (timetable),called hypermutation. For a population size 10, onaverage, the mutation rate is 0.9, and hence 90% ofthe cloned timetables will be mutated. For eachmutated clone, if all hard constraints are satisfied andthere are no duplicate timetables in the currentpopulation, the mutation is a 'success' and the fitnessvalue is then determined. If the fitness value of thecurrent mutated clone is greater than the fitness valueof the original clone, the mutation is a 'failure', andthe reassignment is then reset. If the mutation is a'failure', the same mutation process must be repeateduntil the process is a 'success'. If no mutation is

performed, the timetable will be assigned a largefitness value ('0' stimulation level) so that it will beeliminated during the population update.

Network dynamics (immune cells and antigensinteractions, and population update): Finally, gatherall current and cloned timetables to form a populationof all feasible timetables in the current generation.Sort the timetables according to stimulation level(fitness value) in descending (ascending) order. Selectthe best 10 timetables (high stimulation/low fitness),and update the population with these selected feasibletimetables. A new population of feasible timetablesfor the next generation is now produced, with one ormore (or none) new feasible timetables. Hence, thetimetables with low stimulation (high fitness) will beeliminated during the process.

Cycle:The process (population loop) will be repeated until

the maximum number of generations (1000) isreached.

6.ExPERIMENTAL R ESULTS

The INACT has been implemented on the threedatasets (Schaerf datasets). The following (Table 2)are the first experimental results on solving coursetimetabling problems using immune networkalgorithm. The algorithm was run on each dataset forfive trials, and the maximum number of generations1000 was used. The fitness values, equation (1), forall trials and the best fitness values (based on the fivetrials) for all datasets have been recorded.

TABLE 2FIRST R ESULTS ON SOLVING UCTPs USING INACT

Q;Total Fitness Value [SCIISC2ISC31

'"c ~ M M

""'"on

~.... Oil Oil Oil Oil Oil Best'".s .;: .;: .;: .;: .;:E- E- E- E- E-

1 265 279 290 332 316 265

2 11 16 28 23 26 11

3 53 73 55 50 131 50

In all trials on all datasets, all the five hardconstraints were satisfied, and the total fitness valuefor each trial represents the total violations of softconstraints at generation less than 1000. The bestfitness value for each dataset may be furtherminimized if more trials and a maximum generationnumber larger than 1000 were considered.

For dataset 'instance 1', the best fitness value is265; i.e. 200 students without a seat, 7 coursesscheduled less than a specified minimum days, and 15free gaps between lectures of the same group on thesame day [200 + 5(7) + 2(15) = 265].

For dataset' instance 2', the best fitness value is 11;i.e. 0 student without a seat, 1 courses scheduled lessthan a specified minimum days, and 3 free gaps

5

between lectures of the same group on the same day[0 + 5(1) + 2(3) = 11].

For dataset 'instance 3' , the best fitness value is 50;i.e. 18 students without a seat, 4 courses scheduledless than a specified minimum days, and 6 free gapsbetween lectures of the same group on the same day[18 + 5(4) + 2(6) = 50].

The results from three different course timetablingdatasets have significantly shown that INACT is aneffective optimization algorithm; can successfully beapplied to solve (and optimize) various kinds ofuniversity course timetabling problems.

7.DISCUSSION AND FUTURE WORK

This paper has presented an immune-basedoptimization algorithm for course timetabling, calledINACT (immune network algorithm for coursetimetabling). The algorithm shows great promise inthe area of educational timetabling , particularly in itsability to consider, solve, and optimize the widevariety of different course timetabling problems. Thealgorithm can handle the hard constraints and softconstraints very well.

The experimental results on three benchmarkcourse timetabling datasets, available on the internet,have significantly shown that INACT is an effectiveoptimization algorithm, can successfully be applied tosolve various kinds of course timetabling problems.The datasets may also be considered as multiobjectivecourse timetabling problems since three softconstraints were considered. Hence, it may also beconcluded that INACT may successfully be applied tosolve multiobjective optimization problems.

For future work, other artificial immune algorithms,such as negative selection algorithm, will be appliedto university course timetabling using the same coursedatasets .

REFERENCES

[1] M.W. Carter, and G. Laporte, "RecentDevelopments in Practical Course Timetabling",(PATAT'97), EX. Burke, and M.W. Carter(Eds.), Lecture Notes in Computer Science, 1408,pp: 3-19, Springer Verlag, 1998.

[2] D. Dasgupta, Z. Ji, and F. Gonzalez, "ArtificialImmune System (AIS) Research in the Last FiveYears", Proc. of the International Conference onEvolutionary Computation (CEC2003), Canberra,Australia, December 8-12, 2003.

[3] L.N. de Castro, "Immune, Swarm, andEvolutionary Algorithms, Part I: Basic Models",Proceeding of the ICONIP, Workshop onArtificial Immune Systems, vol. 3, pp: 1464-1468,Singapore, 18-22 November, 2002.

[4] L.N. de Castro, and J. Timmis, "An ArtificialImmune Network for Multimodal FunctionOptimization", Proceedings of IEEE Congress onEvolutionary Computation (CEC'02), vol.1, pp:699-674, Hawaii, May 2002.

[5] L.N. de Castro, and F.J. Von Zuben, "The ClonalSelection Algorithm with EngineeringApplications", Proceedings of The Genetic andEvolutionary Computation Conference 2000(GECCO'OO), pp: 36-37,2000.

[6] L.N. de Castro, and FJ. Von Zuben, "aiNet: AnArtificial Immune Network for Data Analysis",Data Mining: A Heuristic Approach. H.A.Abbass, R.A. Sarker, and C.S. Newton (eds.),Idea Group Publishing, USA, Chapter XII, pp:231-259, 2001.

[7] J.D. Farmer, N.H. Packard, and A.S. Perelson,"The immune system, adaptation, and machinelearning", Physica, 22D, pp: 187-204,1986.

[8] S. Forrest, A.S. Perelson, L. Allen, and R.Cherukuri, "Self-nonself discrimination in acomputer", Proceedings of the 1994 IEEESymposium on Research in Security and Privacy,pp: 202-212, Los Alamitos, CA: IEEE ComputerSociety Press, 1994.

[9] E. Hart, "Immunology as a Metaphor forComputational Information Processing: Fact orFiction?", PhD Thesis, University of Edinburgh,2002.

6

[10]E. Hart, and P. Ross, "An Immune SystemApproach to Scheduling in ChangingEnvironments", Proceedings of the Genetic andEvolutionary Computation Conference 1999(GECCO '99), pp: 1559-1566,1999.

[11]E. Hart, P. Ross, and J. Nelson, "ProducingRobust Schedules Via An Artificial ImmuneSystem", Proceedings of the InternationalConference of Entertainment Computing 1998(ICEC'98),1998.

[12]N.K. Jerne, " Towards a Network Theory of theImmune System", Ann. Immunol. (Inst. Pasteur)125C, pp: 373-389, 1974.

[13]M.R. Malim, A.T. Khader, and A. Mustafa,"University Course Timetabling: A GeneralModel", Proceeding of the Second InternationalConference on Research and Education inMathematics (ICREM2), , UPM, Bangi, 25-27May, 2005.

[14] J. Tirnmis, "An Introduction to Artificial ImmuneSystems", Research Notes. ES2001, Cambridge,University of Kent at Canterbury, England, UK,December 2001.