Browsing by Author "SAY, Bilge"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item New Greedy Algorithms to Optimize the Curriculum-based Course Timetabling Problem(2022-01-14) Coşar, Batuhan Mustafa; SAY, Bilge; Dökeroğlu, TanselThis thesis presents a set of new greedy algorithms for the optimization of the well-known ”Curriculum-Based Course Timetabling” (CB-CTT) problem, which is a subtype of the ”Course Timetabling” problem. The main goal of the study is to minimize the total number of soft constraint violations while preserving the satisfaction of hard constraints (feasible solutions). Since the problem is NP-Hard and large instances of the problem cannot be solved in practical times, greedy algorithms that work to produce acceptable results in a few seconds are good alternatives to brute-force and evolutionary algorithms that spend hours of execution times to search for an optimal solution. Instead of using a single heuristic as it is performed by many greedy algo rithms, we define and execute 120 greedy heuristics on the same problem instance simultaneously and report the overall best result, which would produce better results than which is obtainable by using a single greedy heuristic algorithm. The best results with respect to the No Free Lunch Theory, which states that the costs of greedy heuristics should be comparable on average, are reported. Our proposed greedy algorithms use the Largest-First, Smallest-First, Best-Fit, Average-weight first heuristics, and the Highest Unavailable course-first heuristics simultaneously while assigning the courses to the available rooms that are ordered by their capacity according to the above four different criteria. In order to evaluate the performance of our proposed algorithm, we carry out experiments on 21 problem instances from the Second International Timetabling Competition (ITC-2007) benchmark set. The experimental results verify that the proposed greedy algorithms can report zero hard constraint vio lations (feasible solutions) for 18 problems with significantly reduced soft-constraint values.