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