## 5 Methodology
### Initial Construction of Solutions  
The process of finding quality initial solutions is done at the CPU side as a pre-processing step. The starting population consists of a pool of algorithmically-computed solutions and a set of randomly-created solutions. The algorithmically computed solutions are very few in number (less than 250), and for their construction, the following approach is used. Examinations are ordered according to their largest degree (LD) values, which in effect brings the examinations with the most conflicts on top, and in each step, a specific examination is selected using roulette selection [58] of the 20 or less still unscheduled examinations giving preference to higher LD values. Then, a period is selected randomly from the periods that do not already have examinations in conflict with the selected examination. If no such period exists, then a period has to be selected in which offending examinations should be removed before placement of the newly selected examination. This occurs by exploiting an extra field (removals) that tracks the removals of examinations that each examination is responsible for during the process of solution construction. Therefore, when an examination supersedes other examinations, the number of dislocated examinations is added to the removal field of the examination to be inserted. In order for the process of solution construction to progress, a period is selected based on the aggregate value of the removals field of all examinations that have to be removed and belong to this period. The basic idea is  
Figure 2: Indirect encoding: single-point crossover between two chromosomes after the first gene. Examinations in bold red are missing or appear twice. E1–E5: examinations; T1–T3: timeslots. that the dislocation of examinations with a great total value of removals should be discouraged. This is achieved by organizing a tournament between periods that should be relieved from certain examinations where periods having a high removal value due to the examinations that are scheduled in them tend not to be selected. Algorithm 1 shows the pseudocode of this process. ```
//Eisthestofexaminations,Pisthestofperiods \(pendingExaminations\gets E\); forallthe\(e\in E\)do \(removals[e]\gets 0\); end for //sortexaminationsbyLargestDegree \(sortExaminationsByLD(pendingExaminations)\); while\(pendingExaminations\
eq\emptyset\)do //selecttheexaminationamongamaximumof20 pending  examinationsgivingahigherprobabilitytothehighlargestdegreevalues \(selectedExam\gets rouletteSelect(pendingExaminations)\); \(validPeriods\gets getConflictFreePeriodsFor(exam)\); ifvalidPeriods\(\
eq\emptyset\)then \(selectedPeriod\gets selectRandomly(validPeriods)\);  end if else forallthe\(p\in P\)do \(totalRemovals[p]\gets 0\); forallthe\(e\in\)examinationsscheduledinperiodpdo \(totalRemovals[p]\gets totalRemovals[p]+removals[e]\);  end if  end for //selecttheperiodamongallperiodsgivingahigher probabilitytotperiodswithlowtotalremovals \(selectedPeriod\gets rouletteSelectPeriod(totalRemovals)\); \(removals[selectedExam]\leftarrow\) \(removals[selectedExam]+totalRemovals[selectedPeriod]\); \(conflictingExams\gets getConflictingExams(selectedPeriod,selectedExam)\); \(pendingExams\gets pendingExams\cup conflictingExams\);  end for \(schedule(selectedExam,selectedPeriod)\); \(pendingExaminations\gets pendingExaminations\setminus selectedExam\);  end for
```  
**Algorithm 1**Construction of the initial solutions. ```
//Eistheestofexaminations,Pistheestofperiods \(pendingExaminations\gets E\); forallthe\(e\in E\)do \(removals[e]\gets 0\); forallthe\



### Evaluation

The evaluator is based on Equation (1). The division with \(S\) is dropped, since \(S\) is a scaling factor that does not add at all to the solution approach, while by omitting it, the computations are fully based on integer arithmetic instead of slower floating point arithmetic. Equation (1) has to be calculated for all of the members of the population. The cost evaluation of every member is independent of the computation of the other members.