Repository logo
 
Publication

A cellular memetic algorithm for the examination timetabling problem

2018-06Journal article Restricted access
Simple item page
dc.contributor.authorLeite, Nuno
dc.contributor.authorFernandes, Carlos M.
dc.contributor.authorMelicio, Fernando
dc.contributor.authorRosa, Agostinho
dc.date.accessioned2018-02-27T11:04:16Z
dc.date.available2018-02-27T11:04:16Z
dc.date.issued2018-06
dc.description.abstractThe timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a cellular memetic algorithm is proposed for solving the examination timetabling problem. Cellular evolutionary algorithms are population-based metaheuristics. They differ from non-cellular algorithms in that the population is organised in a cellular structure, providing for a smooth actualisation of the populations that contributes to improving the population diversity. The proposed cellular evolutionary algorithm is hybridised with the threshold acceptance local search metaheuristic. The implemented algorithm uses feasible genetic recombination and local search operators, thus limiting the exploration to the feasible solution space. The effect of the threshold acceptance used in the hybrid algorithm for the examination timetabling problem is studied. It is shown that a low threshold decreasing rate is needed in order to rearrange the most difficult exams in better periods, allowing for the easy set of exams to be placed in good periods as well. The approach was tested on the public Toronto and ITC 2007 benchmark sets. The proposed hybrid is able to attain four and three new upper bounds for the Toronto and ITC 2007 benchmark sets, respectively.pt_PT
dc.description.versioninfo:eu-repo/semantics/publishedVersionpt_PT
dc.identifier.citationLEITE, Nuno; [et al] – A cellular memetic algorithm for the examination timetabling problem. Computers & Operations Research. ISSN: 0305-0548. Vol. 94 (2018), pp. 118-138pt_PT
dc.identifier.doihttps://doi.org/10.1016/j.cor.2018.02.009pt_PT
dc.identifier.issn0305-0548
dc.identifier.urihttp://hdl.handle.net/10400.21/8140
dc.language.isoengpt_PT
dc.peerreviewedyespt_PT
dc.publisherElsevierpt_PT
dc.relationProject UID/EEA/50009 /2013pt_PT
dc.relationSFRH/PROTEC/67953/2010pt_PT
dc.relationMassive and Adaptive Parallel Computation
dc.relation.publisherversionhttps://ac.els-cdn.com/S0305054818300455/1-s2.0-S0305054818300455-main.pdf?_tid=spdf-6cae64f2-e90d-4352-b647-33580586dbaa&acdnat=1519728843_45fd34caed9b2fb37150e5d01aec91d8pt_PT
dc.subjectCellular evolutionary algorithmpt_PT
dc.subjectExamination timetablingpt_PT
dc.subjectITC 2007 benchmark setpt_PT
dc.subjectMemetic algorithmspt_PT
dc.subjectThreshold acceptance algorithmpt_PT
dc.subjectTimetablingpt_PT
dc.subjectUncapacitated Toronto benchmark setpt_PT
dc.titleA cellular memetic algorithm for the examination timetabling problempt_PT
dc.typejournal article
dspace.entity.typePublication
oaire.awardTitleMassive and Adaptive Parallel Computation
oaire.awardURIinfo:eu-repo/grantAgreement/FCT/3599-PPCDT/PEst-OE%2FEEI%2FLA0009%2F2013/PT
oaire.awardURIinfo:eu-repo/grantAgreement/FCT//SFRH%2FBPD%2F111065%2F2015/PT
oaire.citation.endPage138pt_PT
oaire.citation.startPage118pt_PT
oaire.citation.titleComputers and Operations Researchpt_PT
oaire.citation.volume94
oaire.fundingStream3599-PPCDT
person.familyNameLeite
person.familyNameMelicio
person.familyNameRosa
person.givenNameNuno
person.givenNameFernando
person.givenNameAgostinho
person.identifier.ciencia-idA81D-4C44-1F8F
person.identifier.orcid0000-0001-6328-3579
person.identifier.orcid0000-0001-7825-2687
person.identifier.orcid0000-0001-5165-3114
person.identifier.ridJ-8337-2012
person.identifier.scopus-author-id55894265100
person.identifier.scopus-author-id9336035900
project.funder.identifierhttp://doi.org/10.13039/501100001871
project.funder.identifierhttp://doi.org/10.13039/501100001871
project.funder.nameFundação para a Ciência e a Tecnologia
project.funder.nameFundação para a Ciência e a Tecnologia
rcaap.rightsclosedAccesspt_PT
rcaap.typearticlept_PT
relation.isAuthorOfPublicationa30c7dc8-db92-4fb2-8700-5ba093cdb74c
relation.isAuthorOfPublication204f288e-1618-482d-ad30-4b86afc47d25
relation.isAuthorOfPublication6afb41da-b4e3-4dde-878f-b44a6b7b4a76
relation.isAuthorOfPublication.latestForDiscovery204f288e-1618-482d-ad30-4b86afc47d25
relation.isProjectOfPublication9e152db9-9776-4b55-aedf-203a6dc11d8a
relation.isProjectOfPublication6338b14d-e915-4bdd-808c-1b317268bf76
relation.isProjectOfPublication.latestForDiscovery9e152db9-9776-4b55-aedf-203a6dc11d8a

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
A cellular_NLeite_ADEETC.pdf
Size:
1.47 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

ISEL - Eng. Elect. Tel. Comp. - Artigos