1
$\begingroup$

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


$\endgroup$
1

1 Answer 1

2
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Thanks Sutanu :) $\endgroup$
    – Jwem93
    Feb 12, 2023 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.