Cracking the Scheduling Puzzle: Solving Scheduling Problems with Operations Research

Intro:
In today's fast-paced world, effective scheduling is crucial for optimizing resources, improving efficiency, and meeting business objectives.In this blog, we will explore two powerful tools for solving scheduling problems: Excel and Python. Both offer distinct advantages and approaches to tackle complex scheduling challenges. We will dive into the benefits and limitations of each method, showcasing how Excel's intuitive interface and Python's flexibility and automation capabilities can help you conquer even the most intricate scheduling puzzles

Scenario:
Consider that we have to create a scheduling for a Hospital. The aim is to design doctors schedule for every week. Once a doctor is allocated to a working day then he/she works for the 3 consecutive days and then takes the remaining 4 days off. It is required that atleast half of the weekday scheduled should have weekends off. The weekly demand is as below

Day	Mo	Tu	We	Th	Fr	Sa	Su
Demand	16	12	18	13	15	9	7

Building solution:

Mathematical Model:

1.Objective Function: To minimize the total number of doctors to be scheduled for the working week.

$$Min(\sum_{i=0}^{i=7}Doctor(i))$$

2.Decision Variables: No of Doctors needed for every working day of the week (Should be positive integer)

$$Doctor_{i}$$

where i - individual day of the week

3.Constraints:
The first constraint is to ensure that total number of doctors working on a single day of the week should be able to atleast meet the demand for that day

$$\sum_{i=0}^{i=7}Doctor(i) \geqslant Demand(i) \vdots \psi where Doctor(i) > 0$$

The second constraint is to ensure that more people who work in weekdays should get weekend off.

$$\sum_{i=0}^{i=n}Doctor(i)wkday \geqslant \sum_{i=0}^{i=n}Doctor(i)wkend$$

Method 1 : Excel Solver

• The Decision variable are # of doctors needed for each Day. (Highlighted in Yellow cells)

• The object function is to minimise the total number of doctors

• The constraint 1: is sum of doctor on weekdays > weekends (SUM(D5:D7) > SUM(D8:D11)
  The constraint 2: Total count of doctor for a day should be greater than the daily demand. Have used SUMPRODUCT
  Eg. For a weekday SUMPRODUCT($D$5:$D$11,E5:E11) > Demand for that Day.

Result of Solver:
Objective Functions: 31

Day	Mo	Tu	We	Th	Fr	Sa	Su
Doctor#	11	0	10	3	2	4	1

Method 2 : Python Pulp.

from pulp import *

# Create the problem
prob = LpProblem("Hospital Staffing", LpMinimize)

# Create a list of doctors
doctors = [i for i in range(50)]  # Choosing value big enough

# Create a list of days
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]

# Define the demand for each day of the week
req_doctors = {"Monday": 16, "Tuesday": 12, "Wednesday": 18, "Thursday": 13, "Friday": 15, "Saturday": 9, "Sunday": 7}

# Create the decision variables
# Each doctor i starts their 3-day shift on day j
x = LpVariable.dicts("Doctors", (range(len(doctors)), range(7)), 0, 1, LpBinary)

# Set the objective function
prob += lpSum(x[i][j] for i in range(len(doctors)) for j in range(7))

# Minimum number of doctors for each day
# For each day of the week, we count doctor as available not only on the start day of their shift but also on the two next days
for j in range(7):
    prob += lpSum(x[i][(j-k)%7] for i in range(len(doctors)) for k in range(3)) >= req_doctors[days[j]]

# Doctor can only start their 3-day work shift once in a week
for i in range(len(doctors)):
    prob += lpSum(x[i][j] for j in range(7)) <= 1

# Solve the problem
prob.solve()

print("Status:", LpStatus[prob.status])

work_schedule = {day: [] for day in days}

for i in range(len(doctors)):
    for j in range(7):
        if x[i][j].varValue > 0:
            for k in range(3):
                work_day = days[(j + k) % 7]
                work_schedule[work_day].append("Doctor " + str(i))

for day in days:
    print(day + ":")
    for doctor in work_schedule[day]:
        print(doctor)
    print()

print("Total number of doctors = ", value(prob.objective))

Result of Python Execution:
Objective Functions: 31

Day Mo Tu We Th Fr Sa Su
Doctor# 16 12 18 13 15 12 7

Note: PuLP does'nt have SUMPRODUCT and we have another minima for the same problem. Hence Solver would have said the schedule with #new doctors needed for the day. Where as PuLP output is just count on any given day

Conclusion:
Excel's familiar interface and powerful formulas make it accessible to a wide range of users, enabling them to create efficient schedules with ease. On the other hand, Python provides a robust programming framework, allowing for automation, optimization, and scalability in solving complex scheduling problems. Whether you prefer the simplicity of spreadsheets or the versatility of coding, you now have the knowledge and tools to excel in scheduling problem.

Further Reads:
Excel Solver Add-In