WIXLIB

Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, Norway451Aspen Scheduler: a Web-based AutomatedMaster Schedule Builder for SecondarySchoolsBaiyun Tao, Rick DwyerFollett Software Company/X2 Development Corporation, Hingham, MA, com1 IntroductionBuilding a master schedule involves assigning courses, teachers and rooms to timeslots, maximizing usage of resources and fulfilling student course requests. It isone of most complex tasks performed by administrators at a school each year.This is particularly true for secondary schools in the United States where thenumber and variety of constraints (such as multi-day rotation, combined courses,room capacities, teacher teaming, and student grouping, etc.) increases thecomplexity of the scheduling process.Designed to accommodate both large and small schools with the most complexschedule needs, the system described here, Aspen master schedule builder,implemented by X2 Development Corporation, successfully deals with producinga satisfactory and efficient solution from the large solution space in a reasonableamount of time, while at the same time handling the usability, flexibility andcompleteness of the scheduling process (see Fig 1 for real life schedulingexamples).2 System OverviewsAspen master schedule builder is part of a Student Information System that iscompletely web-based (see Appendix A for terms we use in this paper). It is aJava 2 Enterprise Edition (J2EE) application that runs on Apache Tomcat webserver, uses Apache Struts framework, OJB and supports three database backend:MySQL, SQL Server and Oracle.

452Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, NorwayExample SchoolSchool - 1Scheduling ProfileSchedule terms: Full year academic courses, semester elective coursesNumber of days per cycle: 5Number of periods per day: 7Total number of courses:Total number of staff:Total number of rooms:Total number of Students:Number of requests per student:Total number of student requests:Total number of user specified rules:Total number of sections in master schedule:17253507007-105,60029370Time for building master schedule:Time for loading students:School - 2School - 32 minutes 1 minuteSchedule terms: All courses are semester lengthNumber of days per cycle:2Number of periods per day: 8Total number of courses:Total number of staff:Total number of rooms:Total number of Students:Number of requests per student:Total number of student requests:Total number of user specified rules:Total number of sections in master schedule:314102901,20089,600109800Time for building master schedule:Time for loading students:10 minutes5 minutesSchedule terms: All courses are semester lengthNumber of days per cycle:10Number of periods per day: 15Total number of courses:Total number of staff:Total number of rooms:Total number of Students:Number of requests per student:Total number of student requests:Total number of user specified rules:Total number of sections in master schedule:Time for building master schedule:Time for loading students:7522162534,2001667,2005253,50090 minutes45 minutes*A special constraint: 4 lunch waves splitting over 3 periodsFig.1. Real life scheduling examples

Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, Norway453There are four main objectives used by Aspen master schedule builder to build aschedule:1. Assign each section with an available teacher, an appropriate time slot and asuitable room.2. Satisfy all hard constraints.3. Maximize the satisfaction of student requests.4. Balance student distribution cross different sections of the same course.The system breaks the overall problem of building a master schedule into subproblems, find solutions for each of the sub-problem and combine them to reachan overall solution. An example of a sub-problem is to schedule a section group, agroup of sections that are related to each other because of blocking rules (seeFig.4.2) or tightly shared resources such as teacher and room.The system first orders all sections by their difficulty to schedule. A section'sdifficulty to schedule is determined by analyzing the related course's attributes,teacher availability, room availability and other constraints of the section.Sections are scheduled in rank order with the most difficult ones being scheduledfirst. Section group is formed when a section is chosen to be scheduled based onprevious analysis. A section group contains one or more sections.To schedule each section group, an iterative metaheuristic is used that combineshill-climbing, simple random and greedy algorithms. Three key functions aredefined: search, validation and evaluation. The search function first finds potentialsolutions to validate and evaluate. It starts with an initial solution and iterativelyworks to find better ones. A good solution must be a valid solution – one thatmeets all the hard constraints. A fitness function is used to check a solutionagainst all hard constraints to objectively determine its validity. Once a solution isdetermined to be valid, its quality can be measured and scored. The quality of asolution is determined by three primary measures: the number of student requestssatisfied, the enrollment balance cross sections of the same course, and theflexibility of the solution, i.e. the ability for students to change sections. Anobjective function evaluates the solution and assigns a value to the solution.

454Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, NorwaySolutions then can be compared and the solution with smallest value is consideredas the best solution and will therefore be chosen for the section group.While choosing a solution for the current section group, if the solution affects theranking of sections still to be scheduled, unscheduled sections are either reranked or required resources will be reserved for the future.When a solution cannot be found for the current section group without violating ahard constraint, the system attempts to repair the schedule by moving resourcesalready scheduled to make the resources needed by the current section groupavailable. If such repair attempt is not possible, the system stops with appropriatefeedbacks to the user.3 Key Features3.1 Time StructureSchools have their own unique ways to structure time based on the needs toschedule. Successfully building a master schedule depends on an efficient andflexible way to represent these unique time structures. The structure of a scheduleis defined by three core parameters: the number of terms per year (TPY), thenumber of days per cycle (DPC) and the number of periods per day (PPD).In addition, scheduling patterns are introduced to represent the valid ways toschedule a course of a particular shape. It helps users visualize their schedule (SeeFig. 2). Patterns with similar shapes are grouped together as pattern sets, thenassigned to courses to define the list of possible time slots a course can bescheduled into.3.2 Input and ConstraintsThere are five fundamental input components to build and load a schedule:Course, Student, Staff, Room and Request with each imposing a set of constraintson the schedule. See Fig.3. for the most common constraints associated with eachtype of input.

Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, Norway455Fig.2. Different types of schedule nt Number of sections Valid schedule patterns Balance type cross section and subject Load priority used for conflict resolution for individual student Student grouping code: house, team and / or platoon Unavailable time Load priority Enrollment weight Teacher assignments Preferred room and location Maximum number of rooms and locations allowed Maximum number of consecutive teaching periods allowed Max capacity Department and location usage Preferred section and / or teacher Partial content Inclusion Section typeFig.3. Common constraints for each type of input3.3 RulesRules are introduced to allow additional and more complex constraints on theschedule. Rules can be defined as either hard or soft. Hard rules must be satisfiedin order for the schedule to be valid. Soft rules are satisfied whenever possible - it

456Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, Norwayis at the discretion of the system. The system will decide which soft constraint todrop in the event of a conflict between soft constraints. The system can also dropa soft constraint if the impact on the overall schedule is too costly such as a validsolution cannot be achieved.The system currently provides 27 different types of rules for the schedulingprocess including both build rules and load rules (See Fig.4.1 and Fig. 4.2).Although the system separates the build and load process. All load rules areincluded and evaluated during the build process to ensure potential solution don'tviolate the load rules.3.4 Sandbox ApproachThe system takes a sandbox approach to allow users to create and save multiplescheduling scenarios within each school. Scenarios can be copied at any point toserve as a back-up. Each scenario can include different set of students, courses,teachers, and/or rules. Scenarios have their own master schedule that is built andloaded independently of all other scenarios. Users can use different scenarios toexperiment with different constraints and even different types of schedules (SeeFig.5.).Fig.5. Different scenarios

Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, NorwayRule Name457Rule DescriptionBell - Course RestrictionsRestrict courses for a particular bell scheduleBell - Room RestrictionsRestrict rooms for a particular bell scheduleCourse - AlternatesSchedule alternate courses for students upon conflictsCourse - BlockingSchedule a set of courses together following particular relationshipsCourse - Group ExceptionsSpecify the courses that can be excluded from any groupingCourse - Pattern Sets RestrictionRestrict usage of patterns for a courseCourse - Pull-outAllow student to be pulled out from one course to go to anotherCourse - Sequence ConcurrentSchedule two courses in the same term for a studentCourse - SequencingSchedule a courses in a student's schedule for completion before thestart of another courseCourse - Term LinkSpecify the list of courses that a student must be scheduled inspecified termsCourse - Terms RestrictionRestrict usage of terms for a courseRoom - Course RestrictionReserve rooms for a courseRoom - ExceptionsExclude rooms from being used by a courseRoom - ProximityDefine room proximityRoom - ReservationsReserve rooms for coursesRoom - UnavailableRoom is unavailable for scheduling during these time slotsRoom- Teacher RestrictionReserve rooms for a teacherStudent - Avoid TeacherStudent should not be scheduled with specified teacherStudent - Student RelationshipStudent should be/not be scheduled with specified studentTeacher - Avoid StudentTeacher should not be scheduled with specified studentTeacher - Common PlanningSchedule teachers on a team into a common planning timeTeacher - ConcurrentAllow a teacher to teach multiple courses concurrentlyTeacher - DovetailUse the minimum periods when schedule a teacher for partial courseTeacher - Max-in-a-row ResetReset teacher's max-in-a-row count after a specified periodTeacher - Part-timeSchedule part-time teacher with a minimum span of periodsTeacher - Reserve Time BlockReserve a time block in a teachers schedule from a list of possibleperiodsTeacher - UnavailableFig.4.1 Different types of rulesTeacher is unavailable for scheduling during these time slots