A New Greedy Algorithm for the Curriculum-based Course Timetabling Problem

Abstract

This study describes a novel greedy algorithm for optimizing the well-known Curriculum-Based Course Timetabling (CB-CTT) problem. Greedy algorithms are a good alternative to brute-force and evolutionary algorithms, which take a long time to execute in order to find the best solution. Rather than employing a single heuristic, as many greedy algorithms do, we define and apply 120 new heuristics to the same problem instance. To assign courses to available rooms, our proposed greedy algorithm employs the Largest-First, Smallest-First, Best-Fit, Average-weight first, and Highest Unavailable course-first heuristics. Extensive experiments are carried out on 21 problem instances from the benchmark set of the Second International Timetabling Competition (ITC-2007). For 18 problems with significantly reduced soft-constraint values, the proposed greedy algorithm can report zero hard constraint violations (feasible solutions). The proposed algorithm outperforms state-of-the-art greedy heuristics in terms of performance.

Keywords

• course-timetabling
• greedy algorithms
• heuristics
• optimization
• ders zaman çizelgesi oluşturma
• açgözlü algoritmalar
• buluşsal yöntemler
• eniyileme