Zamjena grupa zasnovana na željama studenata

master's thesis

• Title (english): Group Swapping Based on Student Preferences
• Author: Josip Kasap
• Mentor: Goran Delač (mentor)
• Committee member: Goran Delač (predsjednik povjerenstva)
• Committee member: Marin Šilić (član povjerenstva)
• Committee member: Siniša Srbljić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Organizacija izvođenja nastave je problem s kojim se suočavaju sve obrazovne ustanove. Taj problem je vrlo širok i mnogi dijelovi tog problema poput problema izrada rasporeda su bili predmeti mnogih istraživanja. Dodatan problem u rješavanju izazova u organizaciji izvođenja nastave nastaje zbog specifičnih zahtjeva svake pojedine obrazovne ustanove.
Zamjena grupa temeljena na željama studenata je dio problema organizacije izvođenja nastave u kojem je raspored predmeta već napravljen, a studentima je omogućeno da zamjenjuju grupe po vlastitim željama. Cilj problema je prebaciti grupe što većem broju studenata na temelju njihovih zahtjeva, a da se pri tom ne naruše uvjeti funkcioniranja nastave. Uvjeti funkcioniranja nastave su u ovom slučaju kapacitet učionica u kojima se održava aktivnost grupe, koji mora biti ograničen maksimalnom vrijednošću kapaciteta te učionice. Drugi uvjet funkcioniranja nastave je da se studentima ne smije omogućiti da prihvaćanjem njihovog zahtjeva oni ima preklapanje u satnici između grupa koje slušaju.
Cilj ovog rada je bio osmisliti i implementirati algoritam za zamjenu grupa temeljen na željama studenata, za Fakultet elektrotehnike i računarstva. U suradnji s Centrom informacijske potpore na fakultetu (CIP), algoritam će biti implementiran i korišten na fakultetu za tu svrhu. Osmišljeni algoritam se temelji na evolucijskom računarstvu (konkretno genetskom algoritmu) te je programski ostvaren u jeziku Java.
Kako bi se dobio dojam o kvaliteti algoritma, u radu je provedeno vrednovanje s kojim se usporedio rad službenog rješenja, s drugim algoritmima koji rješavaju isti problem. Vrednovanje je provedeno nad $3$ testna primjera koji predstavljaju stvarne primjere u zamjeni studentski grupa. Vrednovanje je trajalo $60$ minuta prilikom čega se pratila funkcija dobrote svakog rješenja i broj ostvarenih zahtjeva. Službeni algoritam pokazuje bolju vrijednost funkcije dobrote, kao i veći broj ostvarenih zahtjeva za svaki testni primjer u odnosu na svaki drugi algoritam korišten u vrednovanju.
Vremensko trajanje algoritma nad stvarnim primjerima je otprilike $10$ minuta, što je prihvatljivo za korištenje nad ovim problemom. Ovaj rad prikazuje jedno moguće rješenje ovog problema. Algoritam na nikoji način ne jamči optimalnost dobivenog rezultata, te je u stvarnim primjerima vrlo malo vjerojatno da je dobiveno rješenje algoritma stvarno globalni optimum. Zbog svih navedenih razloga ima dosta prostora za unapređenje algoritma.

Abstract (english)

Organization of school activities is a problem faced by all educational institutions. This problem is very common and many of the subproblems of this problem, such as the scheduling problem were already the subjects of researches. An additional problems in solving the challenges in organization of school activities comes from the specific requirements of each individual educational institution.
Replacing groups based on student preferences is part of the problem of organization of school activities where the course schedule has already been made and students are allowed to replace the groups according to their own preferences. The goal of this problem is to replace groups to as large number of students as possible based on their preferences, without violating the terms of educational institution. In the case represented by the work this thesis, the conditions are the capacity of classrooms where the activity of the group is maintained, which is limited by the maximum capacity of the classroom. The second requirement is that there should not be any overlaps between working schedules of any $2$ groups. for all of the students, after the requests have been approved.
The goal of this thesis was to devise and implement a group replacement algorithm based on student preferences, for the Faculty of Electrical Engineering and Computing. In co-operation with the Center for Information Support at the Faculty, the algorithm will be implemented and used at the Faculty for that purpose. The designed algorithm is based on genetic algorithm and is implemented in Java programming language.
In order to get an impression on the quality of the algorithm, an evaluation was carried out to compare the work of the official solution, with other algorithms that solve the same problem. Evaluation was conducted over $3$ test samples that represent real examples in replacing student groups. The evaluation lasted for $60$ minutes. The evaluation process recorded the goodness function of each solution and the number of requests made. The official algorithm shows a better value of the goodness function, as well as a greater number of realized requests for each test example compared to each other algorithm used in the evaluation.
The time duration of the real-case student replacement problem with this algorithm is around $10$ minutes, which is acceptable for the problem. This thesis presents one possible solution to this problem. The algorithm in no way guarantees the optimum of the result obtained, and in real instances it is unlikely that the algorithm solution is really a global optimum. Because of all the above reasons, there are plenty of room for improving the algorithm.

• Keywords: zamjena studentskih grupa; rasporedivanje nastavnih obaveza; algo- ¯ ritmi poboljšavajucih metaheurstika
• Keywords (english): student groups replacement; assignment of school activities; improving metaheuristics algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:168:317646
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 19:00:42