# Optimal to-do list scheduling in Python using Pyomo

I am trying to optimally schedule a series of tasks with fixed durations between 9am and 5pm in the day (I guess kind of like a constrained knapsack problem, or job scheduling problem). I have broken the day into 15 minutes increments, and assumed my working window is 8 hours (32 x 15 minutes increments). Across the columns of the output matrix are the tasks in order from Task 1 to Task4. If a cell is 1, this means the task was scheduled for that particular interval.

My code kind of solves the problem, however it doesn't treat a task as having a fixed duration. So, in my example, Task 4 is running for 3 hours, when in reality it shouldn't run at all as there isn't enough time to fit the full 4 hours in.

I have a whole range of extra constraints I would like to introduce (e.g. tasks priorities, fixing some tasks at specific times, etc), but for now I wanted to keep it simple. I'd also love for any suggestions, or sample code for even better ways I could approach this problem (other options apart from linear programming are also welcome).

from pyomo.environ import *

# Inputs

Intervals = 32

# Construct model variables
model = ConcreteModel()
model.Intervals = range(Intervals)
model.flag = Var( model.Intervals, model.Tasks, within=Integers)
model.x = Var( model.Intervals, model.Tasks, within=Binary )

# Set objective
model.obj = Objective(expr = sum(model.x[n,m] * 0.25 for n in model.Intervals for m in model.Tasks ), sense = maximize )

# Set constraints
model.row_constraint = ConstraintList()
for n in model.Intervals:

model.column_constraint = ConstraintList()
model.column_constraint.add(sum( model.x[n,m] * 0.25 for n in model.Intervals ) <= durations[m])

model.flag_making = ConstraintList()
for n in model.Intervals:
if n == 0:
elif n == Intervals-1:
else:

# Solve the model
solver = SolverFactory('glpk')
results = solver.solve(model)

# Post processing
df = pd.DataFrame(outputMatrix, columns = task_list)

print("\nObjective Value:")
print(model.obj())

df



In addition to the below code

for m in model.Tasks:
model.column_constraint.add(sum( model.x[n,m] * 0.25 for n in model.Intervals ) <= durations[m])


If you want to squeeze all your tasks within 8 hours then it should be like
$$0.25\sum_n\sum_m x_{m,n}d_m \le D$$ where D=8 or whatever in interval of 15 mins. Your task duration $$d_m$$ is in hours also.

If you don't want tasks to be scheduled in fractions in other words no scheduling if the whole task doesn't fit then either add the below constraint:
$$d_mx_{m,n-1}-\sum_{k \lt n-1} x_{m,k} \le d_mx_{m,n}$$

Or for tighter bounds
Have new binary variable $$y_m =1$$ if task $$m$$ is scheduled, else 0. Then your constraints in addition to what you've in your code will be
$$\sum_m y_m d_m \le D$$ and two more constraints below
$$d_my_m \le \sum_nx_{m,n} \le y_m d_m$$

• Thanks Sutanu :) Commented Feb 12, 2023 at 22:34