COURSE SCHEDULINGWITH PREFERENCE …

1 The Pennsylvania State UniversityThe Graduate SchoolCOURSE SCHEDULING WITH PREFERENCEOPTIMIZATIONA Thesis inComputer SciencebySiddharth Dahiyac 2015 siddharth DahiyaSubmitted in Partial Fulfillmentof the Requirementsfor the Degree ofMaster of ScienceMay 2015 The thesis of siddharth Dahiya was reviewed and approved by the following:Thang N. BuiAssociate Professor of Computer ScienceChair, Mathematics and Computer Science ProgramsThesis AdvisorOmar El ArissAssistant Professor of Computer ScienceJeremy J. BlumAssociate Professor of Computer ScienceSukmoon ChangAssociate Professor of Computer ScienceLinda M.

2 NullAssociate Professor of Computer ScienceGraduate Coordinator Signatures are on file in the Graduate university COURSE timetabling problem is a well-researched NP-hard problemwhere the goal is to create a COURSE timetable with a given number ofprofessors,courses, and time slots. There are certain constraints that needto be followed toensure that professors are not over booked and that courses,which may be scheduledby a student in the same semester, are not scheduled during overlapping time new perspective of preferences for courses and professors ispresented and uponit a new problem is introduced called COURSE scheduling with PREFERENCE optimiza-tion.

3 The focus of this problem is, given sets of courses, professors, time slots, andpreferences in terms of time of day for each professor and each COURSE , a schedule isgenerated where maximum possible preferences are satisfied. To solve this problem,a hybrid genetic algorithm called COURSE Scheduling Algorithm is also COURSE Scheduling Algorithm returns a schedule where the preferences for pro-fessors and courses are maximized, and the difference between the number of creditsthat may be assigned to a professor and the number of credits actually assigned toa professor is kept to a of ContentsList of FiguresviiList of AlgorithmsviiiList of TablesixAcknowledgementsxiChapter 1 Introduction1 Chapter 2 Problem General Formulation of CSPOp.

4 Terminology .. Problem Constraints .. COURSE Scheduling with PREFERENCE optimization .. Background .. Genetic Algorithms .. Related Work .. 10 Chapter 3 COURSE Scheduling Encoding .. Population Generation .. Fitness Function .. CSA Overview .. Schedule Mutation .. Schedule Repair .. Time Slot Constraint Repair .. Professor Credit Constraint Repair .. Local optimization .. Replacement .. 23 Chapter Random Input Instances .. Analysis of Results with Tolerance Value 0.

5 Analysis of Results with Tolerance Value 1 .. Analysis of Results with Tolerance Value 2 .. Real World Schedule .. 33 Chapter 5 Conclusion35 Appendix AData Statistics .. Professor Count of 100 .. Professor Count of 200 .. Professor Count of 300 .. Initial Schedule PREFERENCE Statistics .. Professor Count of 100 .. Professor Count of 200 .. Professor Count of 300 .. Real World Schedule .. 44vReferences55viList of CSA Encoding .. 13viiList of Simple Genetic Algorithm .. CSA Overview.

6 ScheduleMutation .. ScheduleRepair .. ProfessorCreditConstraintRepair .. LocalOptimization .. Replacement .. 24viiiList of Constraint Parameters and Their Weights .. Professor Credit Limit Distribution .. Mean Penalty Per COURSE For Random Input Instances .. Comparison of COURSE PREFERENCE Satisfaction for = 0 .. Comparison of Professor PREFERENCE Satisfaction for = 0 .. Mean CPU Time in Seconds Used Per Instance for = 0 .. Comparison of COURSE Meeting PREFERENCE Level for = 1 Over aComplete, Partial, and Empty Initial Schedule.

7 Comparison of Professor Meeting PREFERENCE Level for = 1 Over aComplete, Partial, and Empty Initial Schedule .. Mean CPU Time in Seconds Used Per Instance for = 1 .. Comparison of COURSE Meeting PREFERENCE Level for = 2 Over aComplete, Partial, and Empty Initial Schedule .. Comparison of Professor Meeting PREFERENCE Level for = 2 Over aComplete, Partial, and Empty Initial Schedule .. Mean CPU Time in Seconds Used Per Instance .. Mean Penalty Per COURSE For Real Schedule .. % of Courses Meeting PREFERENCE Levels.

8 % of Professors Meeting PREFERENCE Levels .. Mean CPU Time in Seconds Used Per Instance .. Statistics for Data Sets of 100 Professors With Balanced COURSE Load Statistics for Data Sets of 100 Professors With COURSE Overload .. Statistics for Data Sets of 100 Professors With COURSE Underload .. Statistics for Data Sets of 200 Professors With Balanced COURSE Load Statistics for Data Sets of 200 Professors With COURSE Overload .. Statistics for Data Sets of 200 Professors With COURSE Underload .. Statistics for Data Sets of 300 Professors With Balanced COURSE Load Statistics for Data Sets of 300 Professors With COURSE Overload.

9 Statistics for Data Sets of 300 Professors With COURSE Underload .. PREFERENCE Statistics for 100 Professors with Balanced COURSE Load . PREFERENCE Statistics for 100 Professors with COURSE Overload .. PREFERENCE Statistics for 100 Professors with COURSE Underload .. PREFERENCE Statistics for 200 Professors with Balanced COURSE Load . PREFERENCE Statistics for 200 Professors with COURSE Overload .. PREFERENCE Statistics for 200 Professors with COURSE Underload .. PREFERENCE Statistics for 300 Professors with Balanced COURSE Load.

10 PREFERENCE Statistics for 300 Professors with COURSE Overload .. PREFERENCE Statistics for 300 Professors with COURSE Underload .. Input Data Statistics .. Comparison of Complete Input Schedule and Resultant Schedulefor = 1 .. Comparison of Complete Input Schedule and Resultant Schedulefor = 2 .. 54xAcknowledgementsIn Star Wars, Yoda is the key for Luke s success in the rebellion against the would like to thank my Yoda, Dr. Thang N. Bui, for guiding me as I learned aboutGenetic Algorithms and for being the one to destroy the walls when I hit them.