2021/02/12 by Joshua S. Friedman, Friedman, Joshua S.
Decision Sciences · Computer Science · #Scheduling and Timetabling Solutions #Constraint Satisfaction and Optimization
paper · pdf · doi:10.48550/arxiv.2102.06743
In many schools, courses are given in sections. Prior to timetabling students need to be assigned to individual sections. We give a hybrid approximation sectioning algorithm that minimizes the number of edges (potential conflicts) in the student conflict graph (SCG). We start with a greedy algorithm to obtain a starting solution and then continue with a constraint programming based algorithm (CP-SAT) that reduces the number of edges. We apply the sectioning algorithm to a highly constrained timetabling model which we specify.