Yapay Zeka Hızlı Bakış & Çıkarımlar
AI InsightYapılan testeler sonucunda Genetik Algoritma ile ders çizelgeleme probleminin kısa sürede çözülebildiği görülmüştür.
📌 3 Maddede Bu Makale
Özet
Üniversitelerin her dönem başında yaptığı ders çizelgeleme problemi kombinatortal optimizasyon problemlerindendir. Çizelgeleme problemleri NP-Hard sınıfına giren ve çözümü zor problemlerdendir. Determinist bir yaklaşımla olası bütün ihtimallerin denenmesi gibi algoritmalarla çözüm mümkün olsa da çok zaman alıcı bir işlem olduğundan pratikte bu algoritmalar kullanılmamaktadır. Özelikle probleme ait veriler arttıkça ve çözülmesi gereken çok fazla kısıt olması durumunda çözüme ulaşmak daha da güçleşmektedir. Bu çalışmada ders çizelgeleme problemi çözülmesi gereken katı ve esnek kısıtlar olarak ele alınmıştır. Katı kısıtlar ders çakışması, derslik çakışması, kapasiteye uygun olmayan dersliğe şube atanması gibi kesin olarak çözülmesi gereken kısıtlardır. Esnek kısıtlar ise derslerin istenmeyen zaman dilimlerine atanması bir kısmı ihmal edilebilen kısıtlardır. Bu çalışmada probleme ait katı ve esnek kısıtlar belirlenmiş ve bu kısıtları ihlal edilen durumlara ceza puanları atanarak en az ceza puanına sahip çözümler aranmıştır. Problemin çözümü için çizelgeleme problemlerinde sıkılıkla kullanılan Genetik Algoritma kullanılmıştır. Yapılan testeler sonucunda Genetik Algoritma ile ders çizelgeleme probleminin kısa sürede çözülebildiği görülmüştür.
Abstract
The course scheduling problem that universities do at the beginning of each semester is one of the combinatorial optimization problems. Scheduling problems are NP-Hard problems and difficult to solve. Although it is possible to solve with algorithms such as trying all possible possibilities with a deterministic approach, these algorithms are not used in practice because it is a very time-consuming process. Especially when the data of the problem increases and there are too many constraints to be solved, it becomes more difficult to reach a solution. In this study, the lesson scheduling problem is considered as hard and soft constraints that need to be solved. Hard constraints are constraints that need to be resolved, such as course conflict, classroom conflict, assigning a branch to a classroom that is not suitable for capacity. Soft constraints, on the other hand, are constraints that can be neglected by assigning courses to undesirable time slots. In this study, the hard and soft constraints of the problem were determined and the solutions with the least penalty points were sought by assigning penalty points to the situations in which these constraints were violated. Genetic Algorithm, which is frequently used in scheduling problems, was used to solve the problem. As a result of the tests, it was seen that the course scheduling problem could be solved in a short time with the Genetic Algorithm.