University Lecture Timetable Scheduling Corey Goynes Joe Heins Alan White Abstract: The problem of Lecture Timetabling We will examine three different (LTTP) was selected because it is algorithms to compile course offerings or computationally difficult and it is relevant in the schedules based on variables of the real world in a variety of applications. This environment of the Computer Science paper will examine the lecture timetabling department at UNCW. Optimal schedules will problem from the perspective of a university be generated using a genetic algorithm, a graph attempting to maximize the student's coloring algorithm, and a simulated annealing opportunity to attend required courses. Three algorithm. different algorithms were implemented to A schedule will consist of lectures, given generate possible schedules and the relative by professors during predetermined day/time merits of each algorithm are presented. periods. Sixteen courses will be scheduled with Keywords: twelve professors over 6 day/time periods. To measure the validity or optimality of each optimization, objective function, genetic schedule, 9 constraints will be implemented algorithm, graph coloring, backtracking, using an objective function. Of the 9 simulated annealing constraints, 5 will be "hard" constraints, which a schedule must meet to be deemed feasible. Introduction: Four additional "soft" constraints will provide a Registering for classes at University of measure of a schedule's optimality or fitness Carolina Wilmington (UNCW) is often a rating. critical process where the fate of the student's future depends on course availability. Courses fill up quickly and students may be required to attend their backup or tertiary courses. With thousands of students and faculty, numerous Informal Problem Statement: departments and areas of study, building an Given a set of instructors, a set of optimal schedule quickly transforms into an courses, and a set of day/time periods, find overwhelming task. Limitations and needs of schedules which consist of instructors paired the university, faculty, and students all with courses, matched to day/time periods that influence the possible combination of course meet given requirements. offerings. Each professor can only teach one course per day/time period and each course is taught once per schedule. No more than four
University Lecture Timetable Scheduling Corey Goynes Joe Heins Alan White Abstract: The problem of Lecture Timetabling (LTTP) was selected because it is computationally difficult and it is relevant in the real world in a variety of applications. This paper will examine the lecture timetabling problem from the perspective of a university attempting to maximize the student's opportunity to attend required courses. Three different algorithms were implemented to generate possible schedules and the relative merits of each algorithm are presented. Keywords: optimization, objective function, genetic algorithm, graph coloring, backtracking, simulated annealing Introduction: Registering for classes at University of Carolina Wilmington (UNCW) is often a critical process where the fate of the student's future depends on course availability. Courses fill up quickly and students may be required to attend their backup or tertiary courses. With thousands of students and faculty, numerous departments and areas of study, building an optimal schedule quickly transforms into an overwhelming task. Limitations and needs of the university, faculty, and students all influence the possible combination of course offerings. We will examine three different algorithms to compile course offerings or schedules based on variables of the environment of the Computer Science department at UNCW. Optimal schedules will be generated using a genetic algorithm, a graph coloring algorithm, and a simulated annealing algorithm. A schedule will consist of lectures, given by professors during predetermined day/time periods. Sixteen courses will be scheduled with twelve professors over 6 day/time periods. To measure the validity or optimality of each schedule, 9 constraints will be implemented using an objective function. Of the 9 constraints, 5 will be "hard" constraints, which a schedule must meet to be deemed feasible. Four additional "soft" constraints will provide a measure of a schedule's optimality or fitness rating. Informal Problem Statement: Given a set of instructors, a set of courses, and a set of day/time periods, find schedules which consist of instructors paired with courses, matched to day/time periods that meet given requirements. Each professor can only teach one course per day/time period and each course is taught once per schedule. No more than four
University%20Lecture%20TimetablingFinal.docx