Implementing a scheduler with linear programming

Linear and integer programming — the bread and butter of every student that went through the Engineering Systems and Design curriculum in Singapore University of Technology and Design. I always found it too theoretical and impractical and never grasped how powerful this tool could be. In the Spring of 2021, I took the advanced course and saw for myself how an infinitely complex problem with innumerable constraints, bounds and exceptions could be formulated and solved with relative ease.

Problem Archetype

Now scheduling has always been a challenging task. I have seen first-hand during my time as a consultant the absolute horrors if not managed properly.

Picture this — a massive excel, a session (to-be-scheduled) in each row, the time periods of each day as the columns and a few more sheets mapping the intricacies and relationships: Students/instructors/venue to specific sessions and specific sessions to certain modules. Sessions are then scheduled manually line-by-line while keeping track of the students/instructor/module/ venue constraints.

You can already imagine the inequitable effort to quality ratio this implementation entails. Alternatively, linear programming makes for not only an error-free output, free of nasty double-bookings and clashes, but also one that allows you optimize your schedule based on criterias that are important to you and those stakeholders implicated by this schedule. This brings us to the main focus of this article: To employ linear programming to design a favourable weekly schedule for student and faculty while respecting various conflicting requirements.

P.S. Implementation is a little rough around the edges. I’m considering polishing it when I find the time.

Import Requisite Libraries

A few libraries will be employed in this endeavour: Gurobi, Pandas, Numpy and xlrd to manipulate excel spreadsheets

Data Preparation

Two sheets are prepared in advanced to be fed into the model

1. Indexed sessions-to-be-scheduled with their associated characteristics. These session characteristics helps us split these sessions strategically should some constraints are built around these characteristics. For example, if our constraint is to prevent the double-booking of a venue, we will split the dataset into “sessions that share the venue” and formulate this constraint logic for these sessions. Similarly, if any other characteristic of the sessions plays into how we may want to schedule these sessions, we should input them accordingly.
2. Index sheet to map each characteristic to an index. Although the code may only understand the instructor characteristic as “Professor 1, Professor 2”, we will need to somehow map “Professor 1” back to “Professor Charles Xavier”.

Building the model

Every linear program consists of 4 main components:

• Variables
• Parameters
• Objective function
• Constraints

In order, we first define the necessary variables and parameters. We use session-time-indexed binary variables which are set to 1 if a session starts at a certain time. If there are 10 possible start times and 2 sessions to be scheduled, this brings it up to a total of (10*2) = 20 binary variables. This may sound alarming but may I allay your fears by saying that my implementation exceeding 3000 variables and 5000 constraints took mere seconds to solve.

Binary variable (2,15) is set to 1 if session 2 starts at 1500h

For our objective function, we identified 3 (possibly) conflicting preferably features of a “perfect timetable” and weighted them in accordance to how many stakeholders are interested in this feature. A simplified version of this function looks a little like this:

Objective = 30 A + 70 B + 50 C

where A is the number of days where the latest session end after 10pm and 30% of the stakeholders are interested in this feature.

While our constraints are innumerable, they most fall under 2 categories. Either for all or a specific set of sessions,

• No clashes (Double booking)
• Must start/end by a specified time

Now, we are ready to optimize, visualize the results, understand the breakdown of the contributions of (A, B ,C) in our objective function and how we can tweak our model to achieve that “perfect” timetable. Due to the highly problem-specific nature of this analysis, I have omitted this segment.

Exporting the results

Now a schedule is pointless if we can’t democratize and distribute it to all implicated stakeholders. I wrote an additional function that exports the outputs into Google calendar.

Takeaways

What really took my breath away was the efficiency of this optimization. Scheduling is a highly complex problem with parts that are interlinked in ways the human mind struggles to work with. Forget optimizing for a certain objective criteria — simply finding a feasible solution is a challenge in itself. I can already picture the excel with countless checksum cells and conditional formatting to ensure no constraints are violated. In comparison, linear programming provides a clean, effective and reliable method for scheduling problems.

This also represents the first time I’ve implemented linear programming in Python (Gurobi). It was far more intuitive than I would’ve imagined. I am excited to formulate the next scheduling problem, hopefully in a totally different context ie job shop, flow shop and etc.

Credits:

• Online references
• Teammates: Tan Yun Xuan, Amanda Lee, Andrea Chong, Choo Yan Guang
• Professor: Wang Xing Yin