{"entities":{"Q1736620":{"pageid":1747361,"ns":120,"title":"Item:Q1736620","lastrevid":72381516,"modified":"2026-04-14T04:31:22Z","type":"item","id":"Q1736620","labels":{"en":{"language":"en","value":"Solving the examination timetabling problem in GPUs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042208"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$938C59E3-D614-486E-8D36-3A1D2C148CFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73e117c7cd157021e9fb106be10ee2f8cd27d19b","datavalue":{"value":{"text":"Solving the examination timetabling problem in GPUs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736620$00D7B18F-C6E5-4E0C-9C56-5429C59B9CC4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b550072e71f47b1dcfa0f6aa15098e7bb31bb5e8","datavalue":{"value":"1461.90179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736620$5DD0710A-D9BD-4A54-A23D-13B45658D4AF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be1114f712a264b465345067e3c20e68e352a491","datavalue":{"value":{"entity-type":"item","numeric-id":1736619,"id":"Q1736619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$2130DE27-52E7-4E94-A3B1-E38B99B4F822","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"148c3761831889267f2211e9aa7c7ba2501c7c90","datavalue":{"value":{"entity-type":"item","numeric-id":439700,"id":"Q439700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$2E4047A5-60E9-4DF2-AF29-961A2E81D212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b176d117918a0ec4c2343a9f5c1633e3d9483c0","datavalue":{"value":{"entity-type":"item","numeric-id":439699,"id":"Q439699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$574FFC77-303F-4B24-9201-0C57F3EA6BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"649ad6c1432af8eb6d4e3f80f8ac0936b5b6052b","datavalue":{"value":{"entity-type":"item","numeric-id":181232,"id":"Q181232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$E07D0F22-6358-48F7-8BE6-46A2EAD3564B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d38d6f0cc3c294c39446358bcd33804cf74ff48b","datavalue":{"value":{"entity-type":"item","numeric-id":223535,"id":"Q223535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$988D7F49-6910-4144-B35F-B8CB092397ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$7109E721-6607-4033-8899-9128BDEF12E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736620$E1BA3985-16AB-4238-A24F-E0256E90A2B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ae5cb314951b1747d8890ef6454b8b08b0d8dcb","datavalue":{"value":"Summary: 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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736620$62AD59DC-9B55-42F6-BF56-7F59397CAEDA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736620$7495E465-632A-4C8A-9002-E46E1BFDDF02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736620$B1FB052D-6C06-437C-9B95-E21E0D525A1A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c85970e62047aaab0522b58f201ea87434736fc3","datavalue":{"value":"7042208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736620$AC75A1E5-0A68-41C1-8884-711298B6142C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c4895020ac6165be16ea61f818ca2e9f8f88c2f","datavalue":{"value":"evolutionary algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736620$E15028BE-745E-4B48-BA8E-7192D4DD1235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0dcee69c5e0fa1b039d89f560043561d25dc942","datavalue":{"value":"examination timetabling problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736620$E9ACF4CA-39B2-4BEC-B5A3-D0A699328EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"768a0ee841965c37db6a9196fc972ca1c4e60029","datavalue":{"value":"GPU computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736620$6CFBEDEB-1014-4739-A28F-F74AEA3372F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8fd07f1d71589a66f37ce986e7b2e4ddaba95ea","datavalue":{"value":"CUDA","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736620$C4DD7D4A-979A-4D1A-9A21-0CDB0154E13A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"5cc28bfe42783bf21dcf131ea39a2388643e15b9","datavalue":{"value":{"entity-type":"item","numeric-id":19117,"id":"Q19117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$B7F8D0BA-D550-4FDA-BB6A-95764BBEDD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"f3a054baa4efca75beada6ac9f2f664c52ac32a0","datavalue":{"value":{"entity-type":"item","numeric-id":15791,"id":"Q15791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$40739661-4C68-4B5A-9C21-CCE31F97A13A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$488D4342-D959-4E41-B4D1-AA6665A683C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"72a617b9166fc6d566be9f8f9604430fbbf85d54","datavalue":{"value":"https://doi.org/10.3390/a7030295","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736620$48784E94-8890-4F73-817B-A39921AA2396","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"74d49bc43cf243f12a9f68fa48403a98e0d3d23b","datavalue":{"value":"W2080574925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736620$9031D184-4B2C-4571-AF34-263AA21BA7B2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8f51123d4849920c0bd477136f67ae685bea6fb","datavalue":{"value":{"entity-type":"item","numeric-id":4821526,"id":"Q4821526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$C77EFDA5-4492-4330-BF21-1909791064AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf8997ef07509768424633ea061630fea458207d","datavalue":{"value":{"entity-type":"item","numeric-id":4225802,"id":"Q4225802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$95629E8B-3974-4CF2-8B0E-70F83124A93F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cb59c9df56380ae61b0d0a013f7f99004353956","datavalue":{"value":{"entity-type":"item","numeric-id":5917497,"id":"Q5917497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$59DB72AB-2F9A-4E78-AAEA-5C282B3A598E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"598523ed81c9c46737a0dca70cede1f2a4eb9511","datavalue":{"value":{"entity-type":"item","numeric-id":4692508,"id":"Q4692508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$7780654B-7D8A-4918-B63B-16BCBF569ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca02c48bbc5c6c9045bf62ee3dff815f6a3da63d","datavalue":{"value":{"entity-type":"item","numeric-id":4079017,"id":"Q4079017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$F872B458-6E51-4847-8B0B-ACDC4F638FC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb86e532ce7b70eb2e9701abec52cd4c07812b12","datavalue":{"value":{"entity-type":"item","numeric-id":2899043,"id":"Q2899043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$1C1DB5E1-B26B-4685-87DC-64A55EF91A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ee60a63503ba9dca3282d1def1583cc587e31d","datavalue":{"value":{"entity-type":"item","numeric-id":1761902,"id":"Q1761902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$7B35FDFB-E56A-4F93-9726-31E4852A473B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53a5e4602a61db42c4ba8d21cc59b64fdb4bd5ca","datavalue":{"value":{"entity-type":"item","numeric-id":835639,"id":"Q835639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$5264AA3E-9995-422F-B936-951F353C9BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d22e95cfb08114972c1514e26bef4d87d04d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5524918,"id":"Q5524918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$F1F24823-0489-4DF6-AAA7-1D6960D82C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9536c371133943d4a7dc5a44ff34629f29ca667","datavalue":{"value":{"entity-type":"item","numeric-id":596455,"id":"Q596455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$48F9A520-212A-4076-93D9-4C206C539C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e26c11a7c4d1e7acee6ac3836c3e45ffa5e36008","datavalue":{"value":{"entity-type":"item","numeric-id":1809839,"id":"Q1809839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$44AAF565-9E89-4C5E-8EF1-708C062F6CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5839b2c1b8b6731382df3bfd8ac776d898b6b707","datavalue":{"value":{"entity-type":"item","numeric-id":2779804,"id":"Q2779804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$267D6307-F028-4A5C-A38B-C1FE5EE30D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc2731f8e1362ec6cd083f49ee7cb74c211a9333","datavalue":{"value":{"entity-type":"item","numeric-id":1417490,"id":"Q1417490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$9258F392-8B08-472F-89D5-392706723439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26cbe9c915341cf27facc58278f356a05733f1fc","datavalue":{"value":{"entity-type":"item","numeric-id":1406667,"id":"Q1406667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$239B1605-AB5C-44D8-9FD9-4401D59D79C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18060bb4bd18f550f4633e138859911252ae95ca","datavalue":{"value":{"entity-type":"item","numeric-id":2779807,"id":"Q2779807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$2E34CEC5-8A73-4607-866C-314A544772D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a6bfb85c4de9c08bfea5d16c326cf23429ba777","datavalue":{"value":{"entity-type":"item","numeric-id":1014945,"id":"Q1014945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$32D4DABD-435F-479B-A30B-403E5497D76D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c778f3721bace5f6179161cf18650a3f38a7ce","datavalue":{"value":{"entity-type":"item","numeric-id":3161783,"id":"Q3161783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$E2046519-3A46-425A-839A-43A9E0C5D023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7de9dd5275f5e79cdb27c738e76d5d7e1051df44","datavalue":{"value":{"entity-type":"item","numeric-id":4921253,"id":"Q4921253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$5BCAA26A-09D6-43CD-9239-48A6CE5B44C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932b2e2a1e51d07f327a68fa2e37670635a3b68b","datavalue":{"value":{"entity-type":"item","numeric-id":5274281,"id":"Q5274281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$5BE626F0-9141-4CCA-96BC-C3AA78632C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c8966ac1e8218287c4f0bc86f4bbd3dfb09957","datavalue":{"value":{"entity-type":"item","numeric-id":3578834,"id":"Q3578834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$FB3A9C83-D248-4218-9578-7140902821C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f43283ebb697ee7a5ae46ddbbca77309e999a5","datavalue":{"value":{"entity-type":"item","numeric-id":3058737,"id":"Q3058737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$CF926296-9118-46C4-A21B-9707249DA69D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3616ff2c1f75d884e7a9df7b932ffbc8ec564fa","datavalue":{"value":{"entity-type":"item","numeric-id":2460072,"id":"Q2460072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$7EB3EDF5-C91D-400C-91B8-1EFDE2D12D5C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e1f94863e78cf268e00dc7fef070136cf17f18c","datavalue":{"value":"10.3390/A7030295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736620$7A92A0DB-86A3-447D-B97A-B97AF05675B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"863e1fea3537be4f7457b4831a71d74a36822093","datavalue":{"value":{"entity-type":"item","numeric-id":499342,"id":"Q499342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ca0cae9b83287377ff1acdbcb459d83730f3e26","datavalue":{"value":{"amount":"+0.8581277","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736620$48EA696B-AAB9-414A-8DFA-391D58147CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68f5353d6f003c43ea2edfd0f4414d3f903a3fa3","datavalue":{"value":{"entity-type":"item","numeric-id":4577952,"id":"Q4577952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"106e68ae07991425898818a4b8dbe7a4b27d15dd","datavalue":{"value":{"amount":"+0.84506536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736620$B8B73634-C338-4B88-8429-99297BC4BA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"850937993e3f48a98a673c900bc345d87ed82e24","datavalue":{"value":{"entity-type":"item","numeric-id":991105,"id":"Q991105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef10c0fa41f9a0c7a7e7f125ae9f943ec81121aa","datavalue":{"value":{"amount":"+0.8416406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736620$14A5EBBC-0E0E-452D-912E-BD60DD9B5006","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736620$8F0A18A0-9080-4994-8727-A6505DED7925","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving the examination timetabling problem in GPUs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_the_examination_timetabling_problem_in_GPUs"}}}}}