Class Scheduling with AI: Using Google OR-Tools for Constraint Satisfaction Problem

Creating a Python script with Google OR-Tools to help solve class scheduling problem

Is ChatGPT capable of scheduling classes for me? My brother posed this question, and my immediate response was, “Absolutely!” All we need to do is input the class schedule and specify our requirements, and it should generate a list of suitable classes.

So I tried prompting ChatGPT, and the initial version was something like this:

This is how lazy I have become knowing that ChatGPT can understand wrong spellings because of contextual knowledge. LOL ;)

After a few tries of those basic prompts and not getting the result. I realized it wasn’t as straightforward as I initially thought.

Here’s how I navigated the process and ultimately succeeded:

Exploring Prompt Engineering with ChatGPT

I began using basic prompts, but they didn’t yield the desired results. This led me to experiment with Instruction-Following Prompting.

What is Instruction-Following Prompting?

In the context of large language models (LLMs), this technique involves giving clear, detailed instructions to guide the AI in producing the desired output while adhering to specific constraints.

In the context of AI and large language models (LLMs), this technique involves giving clear, detailed instructions to guide the AI in producing the desired output while adhering to specific constraints.

Here’s the approach I used:

1. Inputs: Provided two Excel files containing the class schedules.
2. Instructions: Included target courses, ensured minimum time between classes, etc.
3. Constraints: Specified time slots to avoid.
4. Desired Output: An Excel file with separate sheets for each schedule option.

Here’s how I applied the technique:

But for some reason, the prompt returned timeouts:

Determined to find a solution, I wrote my own Python scripts to handle the scheduling process. I started by diagramming the schedule creation process. 

The plan was to build something like this.

Python Code:

However, as I ran the code, it took longer than expected.

The reason behind this is the find_schedules. The function is recursive and can potentially explore all combinations of courses. The time complexity can be approximated as O(K^T). If the number of target courses (k) increases, the number of potential schedules grows rapidly, leading to longer execution times.

P.S. If you are unfamiliar with the Big O, read it here.

Now, it could be the reason why ChatGPT was timing out. It was possibly running a code with  O(K^T) time complexity.

O(K^T) Workaround

I made the code work by tweaking the code and limiting the number of results.

Here’s the code:

AI theories

After some research, I found a better way to solve the issue. How? By using AI theories, specifically Constraint Satisfaction Problems (CSP).

What is CSP?

Imagine you are planning a small dinner party with three friends: Alice, Bob, and Carol. You need to seat them around a table, but there are a few rules:

1. Alice doesn’t want to sit next to Bob.
2. Bob wants to sit next to Carol.
3. Carol doesn’t want to sit at the head of the table.

In this example:

• The variables are the seats at the table.

• The possible values are Alice, Bob, and Carol.

• The constraints are the seating preferences of your friends.

A Constraint Satisfaction Problem (CSP) would help you find a seating arrangement that satisfies all these rules. For instance, you might end up with Alice, Carol, and Bob sitting in that order around the table, ensuring that all preferences are respected.

CSP requires three components:

1. Variables: In the context of a class scheduling problem, the variables are the classes that need to be scheduled. Each variable (class) is associated with specific attributes, such as course name, instructor, and number of students.

2. Domains: Each variable's domain represents the possible values that can be assigned to it. The domain includes time slots, days of the week, and available rooms for class scheduling. For example, the domain of a class variable could consist of all possible time slots and room combinations.

3. Constraints: Constraints are the rules that must be followed when assigning variable values. In the class scheduling problem, typical constraints include:

• Time Constraints: Ensuring that classes do not overlap for students or instructors.

• Room Constraints: Assigning classes to rooms that accommodate the expected number of students and have the necessary equipment.

• Instructor Constraints: Ensuring an instructor is not scheduled to teach two classes simultaneously and respecting their availability.

• Student Preferences: Accommodating preferences or requirements for specific time slots.

• Departmental Requirements: Meeting specific scheduling needs, such as required courses being available at particular times.

The goal of CSP is to find an assignment of values to the variables (class scheduling) that satisfies all the constraints (requirements for each class).

Note: Need more information on how the CSP algorithm works? You can view this Stanford lecture series.

How do you implement CSP? 

There’s actually a library built by Google to help you resolve the CSP problem. Google OR-Tools is specifically used to solve constraint satisfaction problems (CSPs) and other combinatorial optimization problems.

Implementing the solution

Question: Can I create a custom CSP (Constraint Satisfaction Problem) solution, or can I just use ChatGPT to handle it?

If latency isn’t a significant concern, the critical factor here is cost.

ChatGPT’s pricing is based on the number of tokens processed, both input and output. As of writing this, the GPT-4 model costs around $0.03 per 1,000 tokens for the standard version.

After running some cost estimates with ChatGPT, handling a single scheduling problem comes to about $0.075.

For a scheduling service like Calendly, which charges $10 per month, using ChatGPT to handle scheduling tasks would allow only about 133 requests per user each month ($10 / $0.075). This is in addition to their regular server costs. The company will lose money if a user exceeds or approaches 133 requests.

In conclusion, leveraging ChatGPT can simplify development and offer powerful AI capabilities, but the cost per request could become a limiting factor. Building a custom CSP solution might involve more upfront work but could provide a more cost-effective approach in the long run.

Hope you learned something! Happy coding!

P.S. The complete code here: https://github.com/iamademar/class_schedule_problem