Optimal to-do list scheduling in Python using Pyomo

Question

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
task_list      = ['Task 1', 'Task 2', 'Task 3', 'Task 4']
task_durations = [2,1,2,4]

Intervals = 32
Tasks = len(durations)

# Construct model variables
model = ConcreteModel()
model.Intervals = range(Intervals)
model.Tasks = range(Tasks)
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.row_constraint.add(sum( model.x[n,m] * 0.25 for m in model.Tasks) <= 0.25)

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

model.flag_making = ConstraintList()
for m in model.Tasks:
    for n in model.Intervals:
        if n == 0:
           model.flag_making.add(model.x[n,m] - 0 == model.flag[n,m]) 
        elif n == Intervals-1:
            model.flag_making.add(0 - model.x[n,m] == model.flag[n,m])
        else:
            model.flag_making.add(model.x[n,m] - model.x[n-1,m] == model.flag[n,m])

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

# Post processing
outputMatrix = [[value(model.x[Intervals,Tasks]) for Tasks in model.Tasks] for Intervals in model.Intervals]
df = pd.DataFrame(outputMatrix, columns = task_list)

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

df

Answer 1

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$