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