Introduction
Scheduling is a fundamental problem encountered in various domains, including education, healthcare, sports, and transportation. In academic institutions, exam scheduling is a complex task due to the numerous constraints involved, such as student availability, professor schedules, room capacities, and course requirements.
Traditionally, exam schedules are created manually, which can be time-consuming and prone to errors. To address these challenges, I developed a mathematical model based on Integer Linear Programming (ILP) to automate and optimize the exam scheduling process at the Faculty of Electrical and Computer Engineering, University of Prishtina.
The Challenge of Exam Scheduling
Exam scheduling involves assigning exams to specific time slots and rooms while ensuring that:
- Students do not have overlapping exams.
- Professors are available for supervision.
- Room capacities are not exceeded.
- Exams are fairly distributed over the exam period.
- Various administrative and curriculum constraints are met.
Given the increasing number of students and exams each semester, manually creating a feasible schedule in Excel is inefficient and often results in conflicts.
Solution Approach: Integer Linear Programming
To solve this scheduling problem efficiently, I developed a model using Integer Linear Programming (ILP), a mathematical optimization technique that finds the best solution while satisfying a set of constraints. The model was implemented in Python using the PuLP library, a powerful tool for solving linear programming problems.
Model Structure
The model defines several key components:
Sets:
- Students
- Exams
- Professors
- Rooms
- Days and time slots
Constraints:
- Each student can take only one exam per time slot.
- A professor cannot supervise multiple exams at the same time.
- Room assignments must not exceed capacity.
- Exams should be optimally distributed over the available exam period.
Objective Function:
The model aims to minimize conflicts and distribute exams as evenly as possible.
Implementation & Testing
The model was tested using real data from the Computer Engineering department at the Faculty of Electrical and Computer Engineering. The input data, including exam lists, student registrations, and room details, were read from Excel files and processed by the ILP model.
With thousands of possible combinations, the model efficiently computed optimal exam schedules in a significantly shorter time than manual planning. If no feasible solution was found, the model provided feedback on constraint violations.
Results & Benefits
The ILP-based approach brought several improvements over manual scheduling:
- Increased efficiency: The scheduling process was automated, reducing manual work and errors.
- Better resource utilization: Room assignments were optimized, preventing overbooking.
- Student-friendly schedules: Conflicts were minimized, ensuring fair distribution of exams.
- Scalability: The model can handle growing student numbers and adapt to different scheduling rules.
Conclusion
This project demonstrated that Integer Linear Programming is a powerful technique for solving complex scheduling problems. By leveraging Python and PuLP, we successfully automated exam scheduling, leading to a more efficient and fair process for students and faculty. Future enhancements could include integrating a user-friendly interface and extending the model for other scheduling applications.
By sharing this research, I hope to inspire further applications of mathematical optimization in real-world problems. If you're interested in implementing a similar solution or discussing further improvements, feel free to connect!