Group 1: 
Kuwar
Colman
Alex
Toby

Group 2:
Youngjun
Joaquin
Ronsher
Tony

Group 3: 
Andy
Danny
Veronica
Sana


Group 4:
Luke
Timothy
Yufei
Victoria

The learning outcomes of this project are to teach you:

Goal 1: to research a complex problem and propose a solution

As someone working in computer science, you will often be faced with problems that for which there is no best solution, but a solution is needed nonetheless. Problems like this often have a number of different known approaches to finding a workable solution. You are encouraged to use Chat GPT and/or other AI tools for this project.

Goal 2: to test, analyze, and refine a solution with multiple iterations

Because your first one will be terrible.

Goal 3: Choose the best tool for the job

You will decide upon which platform to solve this problem. You may use any language or platform providing you can run it on school computers as they currently are (I am not waiting for IT to install new software for you. One year I asked them to install Android Studio for this project and 6 months later it still didn't work.)

Goal 4: Collaboration

Defined as "the action of working with someone to produce or create something." A number of soft skills that employers look for in CS related jobs, including communication and leadership, require collaboration. You will be assigned teams of 4ish for this project. You will be assessing yourself and your team at the end of the project.

Goal 5: to use Github

3 Reasons Why You Should Learn Github, 'nuf said.

This "Term Project" portion of your grade is 20% of your total mark on the final report card.

The school timetabling problem is a classic optimization problem in which a schedule needs to be created for various resources (such as classrooms, teachers, and students) over a set time period. The goal is to assign classes to specific time slots while satisfying a range of constraints and objectives.

Here are some key aspects and challenges of the school timetabling problem:

1. Constraints: There are numerous constraints that must be considered when creating a school timetable. These constraints can include:
   • Classroom availability: Each class requires a suitable classroom with adequate capacity and necessary facilities.
   • Teacher availability: Teachers can only teach a certain number of hours per week and may have preferences or restrictions on which classes they can teach.
   • Student preferences: Students may have preferences or constraints regarding the timing of their classes.
   • Subject dependencies: Some subjects may have prerequisites or co-requisites that need to be scheduled accordingly.
   • Avoiding conflicts: It's important to avoid scheduling classes at overlapping times for both teachers and students.
2. Objectives: In addition to satisfying constraints, there are various objectives that can be optimized in school timetabling, including:
   • Minimizing gaps between classes to maximize efficient use of time.
   • Balancing teacher workload to ensure fairness and prevent overloading.
   • Minimizing the number of classrooms needed to reduce resource usage and costs.
   • Maximizing student satisfaction by accommodating their preferences when possible.
3. Complexity: The school timetabling problem is known to be NP-hard, meaning that finding an optimal solution becomes increasingly difficult as the size of the problem grows. As a result, exact algorithms often struggle to find solutions within a reasonable time frame for large instances of the problem.
4. Approaches: Various approaches can be used to tackle the school timetabling problem, including:
   • Exact algorithms: These algorithms aim to find the optimal solution by exhaustively searching through all possible schedules. However, they can be computationally expensive and impractical for large instances of the problem.
   • Heuristic algorithms: These algorithms use rules of thumb or "good enough" strategies to quickly generate feasible solutions, though they may not guarantee optimality.
   • Metaheuristic algorithms: These are higher-level strategies that guide the search for good solutions by exploring the solution space in an intelligent way, such as simulated annealing, genetic algorithms, or tabu search.
5. Software Solutions: There are specialized software tools available for solving the school timetabling problem, which often incorporate a combination of algorithms and techniques to efficiently generate high-quality schedules.

Overall, the school timetabling problem is a challenging optimization task that requires balancing numerous constraints and objectives to create a feasible and efficient schedule for educational institutions.

Author: chatgpt 3.5

Testing, analyzing, and refining a solution to a programming problem are essential steps in the software development process for several reasons:

1. Verification of Correctness: Testing allows developers to verify that the solution behaves as intended and produces the expected results. This ensures that the program functions correctly and meets the specified requirements.
2. Identification of Bugs and Errors: Through testing, developers can uncover bugs, errors, or unexpected behaviors in the solution. By identifying these issues early in the development process, they can be addressed and fixed before the software is deployed or released to users.
3. Improvement of Performance: Analysis of the solution's performance can reveal inefficiencies, bottlenecks, or areas where optimization is needed. By analyzing the performance of the solution under various conditions and workloads, developers can identify opportunities to improve speed, efficiency, and resource usage.
4. Validation of Assumptions: Testing helps validate the assumptions made during the design and implementation of the solution. It ensures that the solution works as intended in real-world scenarios and that any assumptions made about the environment, inputs, or user behavior are accurate.
5. Enhancement of User Experience: By gathering feedback from testing and analysis, developers can refine the solution to better meet user needs and expectations. This may involve improving usability, adding features, or addressing pain points identified during testing.
6. Adaptation to Changing Requirements: As requirements evolve or new use cases emerge, it may be necessary to refine the solution to accommodate these changes. Testing and analysis help identify areas where the solution needs to be adapted or extended to support new requirements or use cases.
7. Continuous Improvement: Software development is an iterative process, and refining the solution based on testing and analysis is crucial for continuous improvement. By iteratively testing, analyzing, and refining the solution, developers can gradually improve its quality, reliability, and performance over time.

Author: chatgpt 3.5

Google "School Timetabling Problem" and research all aspects of the problem. Ask ChatGPT. Get to know the problem in general.

Ask Ms. Wear for the data you will be provided. Look at the data. Get to know the data. Data Q&A.

Learn from what previous groups have done: Previous Group Project Presentations

Decide what kind of solution you would like to try.

Java? Python? PHP? Pick a platform to solve this problem in. You will need to be able to read in text files and write to text files.

What is Git vs Github? Git is an open-source tool developers install locally to manage source code, while GitHub is an online service to which developers who use Git can connect and upload or download resources.

1. Watch What is Github
2. Watch Branches
3. Watch Forks and Pull Requests
4. Watch Github Issues - key to managing complex software collaboration.
5. Join Github.
6. How to Eclispe with Github or try this one
7. VS Code and Git integration

1. Use a Github repository
2. Use a shared Google Doc to document the progress of your project. In this document record all your ideas and useful resources you've found. Document everything you try, and if it succeeds or fails.

• There is no "I" in team.
• To be a valuable member of a group project, always ask yourself, what can I do to help the team succeed.
• This is not about you, it is about the team.
• As soon as you ask "What am I getting out of this?" you have stopped being a part of the team.

Read the assessment below and write methods to assess the success of your solutions.

In the context of the school timetabling problem, metrics play an important role in assessing the quality and effectiveness of a scheduling solution. Here are some specific metrics that can be used to evaluate a timetabling solution:

1. Schedule Completeness: This metric assesses how well the timetable covers all required classes and activities without conflicts. It measures the percentage of scheduled classes out of the total number of classes that need to be accommodated.
2. Resource Utilization: Resource utilization metrics evaluate how efficiently resources such as classrooms and teachers are utilized in the timetable. This includes metrics like classroom occupancy rate (percentage of time classrooms are occupied) and teacher workload (average number of teaching hours per teacher).
3. Student Satisfaction: Student satisfaction metrics gauge how well the timetable aligns with student preferences and constraints. This can be measured through surveys or feedback mechanisms to assess factors such as class distribution throughout the week, alignment with student preferences for specific times of day, and overall satisfaction with the schedule.
4. Teacher Satisfaction: Similar to student satisfaction metrics, teacher satisfaction metrics evaluate how well the timetable accommodates teacher preferences and constraints. This can include factors such as workload distribution, alignment with teacher availability and preferences, and overall satisfaction with the schedule.
5. Minimization of Gaps: Gaps between classes can impact the efficiency of the schedule and the student experience. Metrics related to minimizing gaps measure the total duration of gaps between classes and aim to reduce idle time for both students and teachers.
6. Conflict Resolution: Conflict resolution metrics assess the extent to which scheduling conflicts, such as double bookings of classrooms or overlapping teacher assignments, are resolved in the timetable. This includes metrics such as the number of conflicts resolved and the severity of conflicts remaining in the schedule.
7. Optimization Objectives: Depending on the specific objectives of the timetabling problem, additional metrics may be used to evaluate the solution. For example, if the goal is to minimize transportation costs, metrics related to the distance traveled between classrooms for students or teachers may be relevant.

By analyzing these metrics, stakeholders can assess the quality of the timetable solution, identify areas for improvement, and refine the schedule to better meet the needs of students, teachers, and the educational institution as a whole.

Final Project Evaluation

• Milestones - 50%
• Presentation - 30% (Presentation Assessment Criteria)
• Self and Peer Assessment - 20%

General Goals for Final Results:
Hard Constraints

1. No double bookings
   • No classroom can host more than one class in the same block
   • No student can be scheduled into two courses in the same block
2. Class capacity constraints
   • Science Labs, Auto, Wood, Robotics, Comp Sci can have max 24 students
   • All other courses are max 30 students
3. Valid room assignments
   • courses may only be assigned to approved rooms. (Woodworking - shop, Comp Sci - computer lab, Drafting - drafting lab)
4. Blocking Rules followed
   • Example: If CS 11 and CS 12 are blocked together as a split class, they must appear in the same timetable block
5. Sequencing Rules followed
   • Example: If CS 11 and CS 12 are requested by the same student, CS 11 must be placed in Semester 1 and CS 12 in Semester 2

Optimization Goals (Soft Constraints)

4. Student Request Fulfillment
   • ≥ 90% of all requested courses placed
   • ≥ 80% of students receive 8/8 courses
   • ≥ 95% of students receive at least 7/8 courses
5. Fairness
   • Minimize the number of students with incomplete timetables.
6. Balanced Master Timetable
   • No block should contain more than 4 additional classes compared to another block.
7. Appropriate room assignments
   • 100% of specialty courses placed in valid specialty rooms
   • Maximize placement of regular academic courses into preferred rooms
8. Runtime expectation
   • Produce a valid timetable in under 60 seconds

Optimization Score: Calculate a score for your solution

Metric	Points
Requested course placed	+10
Student gets full timetable	+50
Room Conflict	-1000
Student Conflict	-1000
Invalid Room Assignment	-500
Overfilled Class	-1000
Balanced Block Distribution	+1 per balanced section

/5 - Data Handling and Representation

• Student requests are loaded correctly: print student data structure and size of data structure
• Courses are represented in usable data structures: print course data structure and size of data structure
• Basic timetable structure exists: print timetable data structure and size of data structure

/5 — Valid Schedule Generation
A timetable is produced that:

• Assigns courses to blocks for students, that is, students will have an individual timetable structure.
• Avoids obvious impossible assignments (e.g. course assigned twice in same block for same student)
• Unplaced course requests must be explicitly marked as "unassigned" or null.
• Runs without crashing (even if slow or incomplete)
• Evaluation: To mark this I will pick one student with a timetable and ask you to show me their full timetable

/3 - Output Format (Readability)

• Master timetable is clearly displayed (table / Excel / CSV export)
• Student timetables can be inspected for at least some students
• Output is organized and understandable by a human reviewer.

/2 — Basic Metrics (Early Evaluation Only)
For the generated timetable, compute and display:

• % of all requests successfully placed (placed course requests ÷ total requested courses)
• % of students with 8/8 requested courses (no alternates)
• % of students with ≥50% of requested courses placed (no alternates)
• Show optimization score

Bonus (/2)

• Correct timetable for a randomly selected student (fully 8/8 with no alternates)

Build on Milestone 1 by improving your scheduler so that the master timetable has:

1. the correct number of sections for each course,
2. Follows all blocking rules. For example If CS 11 and CS 12 are blocked together as a split class, both sections must appear in the same timetable block.
3. assigns room numbers to each section
4. never has more than the max number of students in a course
5. and never runs a class with less than 50% of its max.

Student Metrics:

• % of all requests successfully placed (placed course requests ÷ total requested courses)

• % of students with:

  • 8/8 requested courses
  • 7–8/8 requested courses
  • 8/8 courses (requested or alternate)
• The number of students with timetable conflicts
• The number of unassigned course requests

Enrollment Metrics

• The number of students registered in each section of each course displayed in the master timetable
• Total number of sections
• Number of full sections
• Number of sections with less than 50% enrollment

Timetable Metrics

• Number of room conflicts (2 courses in the same room in the same block)
• Number of student conflicts (2 courses in the same block)
• Number of invalid room assignments
• Distribution of classes across blocks (number of courses per block)
• % of blocking rules successfully implemented
• Optimization score

Assessment (/15)

/5 - Section Creation, Room Assignment and Enrollment Management - Instructor will inspect some random courses for correct number of sections, appropriate room assignments, and enrollments

/5 - Blocking Rules Followed - Instructor will inspect 2 random courses for implemented blocking rules

/5 - Metrics - Output must be readable and understandable by a human reviewer.

Bonus (/2) : you can show any 3 students with 8/8 requested courses (no alternative)

Add to Milestone 2: Sequencing Rules, Linear Courses, Minimum Enrollment, and Algorithmic Improvement.

You must demonstrate a clear improvement in how your system schedules students and courses. Simple parameter tweaks are not sufficient.

Required System Features

Add to Milestone 2:

1. Sequencing Rules

Example:

• If a student requests CS 11 and CS 12:

  • CS 11 must be scheduled in Semester 1
  • CS 12 must be scheduled in Semester 2

2. Linear Courses

Linear courses must be properly handled as linked course sequences.

This means:

• They must follow required ordering across semesters
• They must be treated as a connected pair during scheduling decisions (not independently scheduled)

3. Valid Scheduling Constraints (still required)

Your system must continue enforcing:

• No student double-bookings
• No room double-bookings

• Course capacity limits

  • Specialty courses max 24
  • Other courses max 30

• NEW: Minimum enrollment rule:

  • No section runs below 50% capacity unless absolutely unavoidable
• Valid room assignments only
• No invalid course-to-room mappings

4. Required Improvement

In this milestone, you must make a meaningful change to your scheduling approach compared to Milestone 2.

• Runtime must be under 60 seconds for the full dataset

This improvement must be clearly explained and must fall into at least one of the following categories:

Allowed Improvement Strategies (choose at least one)

• Improved greedy ordering strategy (e.g., schedule hardest-to-place students/courses first)

• Constraint-first scheduling redesign (e.g., enforce blocking/room constraints earlier in the algorithm)

• Backtracking or repair-based scheduling (fix conflicts after initial assignment using systematic repair logic)

• Optimization pass after initial schedule (swap students, rebalance sections, or improve placement quality)

• Heuristic scoring system (assign a “best placement score” to decisions instead of first-fit)

• Multi-pass algorithm (build initial schedule → repair → optimize)

• Collaboration merge strategy (integrate another group’s timetable or algorithmic approach)

5. Required Metrics

You must compute and display the following clearly.

Student Metrics

• % of all requests successfully placed (placed course requests ÷ total requested courses)

• % of students with:

  • 8/8 requested courses
  • 7–8/8 requested courses
  • 8/8 courses (requested or alternate)
• The number of students with timetable conflicts
• The number of unassigned course requests

Enrollment Metrics

• The number of students registered in each section of each course displayed in the master timetable
• Total number of sections
• Number of full sections
• Number of sections with less than 50% enrollment

Timetable Metrics

• Number of room conflicts (2 courses in the same room in the same block)
• Number of student conflicts (2 courses in the same block)
• Number of invalid room assignments
• Distribution of classes across blocks (number of courses per block)
• % of blocking rules violations
• NEW: % of sequencing rule violations
• NEW: Runtime for full timetable generation
• Optimization score

7. Improvement Requirement (Before vs After Comparison)

You must output a comparison between Milestone 2 and Milestone 3 for the following metrics ONLY:

• Request fulfillment %
• % of students with 8/8 requested courses
• % of students with 8/8 (requested or alternate)
• Total number of conflicts
• Runtime
• Optimization score

Immediately after this report is output, clearly state:

• what changed in your algorithm
• what improvement you expected
• whether the metrics improved (and by how much)

Assessment (/15)

/5 — Sequencing, Blocking, and Linear Rules

Your system correctly enforces:

• sequencing rules
• blocking rules
• linear course requirements

Instructor will test:

• 1 random sequencing rule
• 1 random blocking rule
• 1 random linear course

/5 — Algorithmic Improvement and Optimization

Your project demonstrates a meaningful improvement over Milestone 2.

Evaluation is based on:

• algorithmic change explained
• evidence of improvement in metrics

/5 — Metrics, Testing, and Output Quality

Your output must be:

• clear and human-readable
• complete (all required metrics included)
• supported by before/after comparison

Bonus (/2)

A random student selected by the instructor must have:

• 8/8 requested or alternate courses
• no timetable conflicts
• no violations of any scheduling rules (including sequencing, blocking, room, and capacity constraints)

---

At this stage, your scheduler should be a fully functional, large-scale timetabling system. The focus is now:

• maximizing student satisfaction
• ensuring system stability
• producing balanced and realistic timetables
• maintaining strict rule compliance

1. Required Metrics:

Student Metrics

• Requested courses placed ÷ total requested courses > 70%
• % of students with:
  • 8/8 requested courses > 30%
  • 8/8 courses (requested or alternate) > 50%

Course Completion Breakdown

• % of students with:

  • 0–2 unfulfilled courses > 50%
  • 3–8 unfulfilled courses < 15%

(Unfulfilled = requested OR alternate not assigned)

Timetable Balance Metrics

• Number of courses per block
• Difference between largest and smallest block must be ≤ 4 courses
• Number of sections per block distribution

Hard Constraint Verification

* Your final timetable must have:

• no student double-bookings
• no room double-bookings
• no over-capacity sections
• no invalid room assignments
• no blocking rule violations
• no sequencing rule violations
• no linear course violations

You must explicitly report:

• number of violations for each (should be 0)

2. Performance Requirement

Display the following:

• Timetable generation must complete in under 60 seconds
• Report runtime in final output
• Total optimization score
• Breakdown of major penalties (conflicts, overfills, etc.)

Assessment:

/10 All metrics provided

/10 All constraint requirements and % values met

Bonus (/2) 1 random student selected, all get 8/8 requested ONLY and the schedule breaks no rules.

• Presentation - 30% (Presentation Assessment Criteria)
• Self and Peer Assessment - 20%