Solving the Examination Timetabling Problem in GPUs
Pourquoi ce travail est-il dans la base ?
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Aucune affiliation canadienne. Une base fondée sur la seule affiliation (le devis habituel) n'aurait jamais vu ce travail. C'est l'un des travaux qui justifient l'inversion de la base.
Le tri à trois modèles
les 1 000 travaux triés →Les trois modèles l'ont jugé hors champ.
Uses a GPU hybrid evolutionary algorithm to solve exam timetabling; the object is an optimization algorithm.
It develops an algorithm for examination timetabling, not a study of research.
GPU algorithm for university exam timetabling; combinatorial optimization of schedules, not study of research.
Résumé
The examination timetabling problem belongs to the class of combinatorial optimization problems and is of great importance for every University. In this paper, a hybrid evolutionary algorithm running on a GPU is employed to solve the examination timetabling problem. The hybrid evolutionary algorithm proposed has a genetic algorithm component and a greedy steepest descent component. The GPU computational capabilities allow the use of very large population sizes, leading to a more thorough exploration of the problem solution space. The GPU implementation, depending on the size of the problem, is up to twenty six times faster than the identical single-threaded CPU implementation of the algorithm. The algorithm is evaluated with the well known Toronto datasets and compares well with the best results found in the bibliography. Moreover, the selection of the encoding of the chromosomes and the tournament selection size as the population grows are examined and optimized. The compressed sparse row format is used for the conflict matrix and was proven essential to the process, since most of the datasets have a small conflict density, which translates into an extremely sparse matrix.
Conservé avec la notice de tri, où il sert de preuve aux étiquettes ci-dessus.
La notice
- Revue
- Algorithms
- Thématique
- Scheduling and Timetabling Solutions
- Domaine
- Decision Sciences
- Établissements canadiens
- —
- Organismes subventionnaires
- —
- Mots-clés
- Computer scienceComponent (thermodynamics)Selection (genetic algorithm)Tournament selectionGreedy algorithmPopulationGenetic algorithmEvolutionary algorithmMathematical optimizationProcess (computing)Matrix (chemical analysis)Class (philosophy)AlgorithmArtificial intelligenceMachine learningMathematics
- Résumé présent dans OpenAlex
- oui