I’m working on optimising the makespan of a set of scheduled parallel tasks using PuLP. We define a world with J CPUs, I tasks and following constraints:

1. A task will only be executed once its dependencies have finished executing
2. A task can be executed “in parallel” with another, meaning it needs to begin and end at exactly the same time
3. Task executions only overlap if assigned to different CPUs
4. Tasks execute in order on the same CPU

This is a pretty standard formulation of parallel task scheduling, and the code below generates an optimal schedule with the given constraints.

I now want to constrain the duration of the task i on CPU j to a discrete value of runtime[(i, j)], but can’t quite figure how. I’ve tried to relate task duration d[i], to runtime k of i on j z[(i, j, k)] like this:

{(i, j): (sum(z[(i, j, k)] * k for k in range(1, max_duration + 1)) == d[i], f"eqX_{i}{j}") for i, j in it.product(I, J)}

however this does not take CPU assignment r[i] into consideration.

Is this the right approach to take? I’m fairly new to PuLP, and certainly not an optimisation expert, so perhaps I’m just missing something.

N_CPUS = 4
N_TASKS = 5

# World dimensions
I = range(N_TASKS)
J = range(N_CPUS)

# Runtime of task i on CPU j
runtime = {
    (0, 0): 5, (0, 1): 3, (0, 2): 1, (0, 3): 2,
    (1, 0): 5, (1, 1): 8, (1, 2): 2, (1, 3): 6,
    (2, 0): 5, (2, 1): 8, (2, 2): 2, (2, 3): 6,
    (3, 0): 2, (3, 1): 4, (3, 2): 5, (3, 3): 1,
    (4, 0): 4, (4, 1): 6, (4, 2): 8, (4, 3): 5,
}

# Maximum possible circuit duration
max_duration = max(runtime.values())

# Ballpark estimate of the maximum makespan
max_makespan = max_duration * len(I)

# Task dependencies
#      0
# 1 ------- 2
#      3
#      4
sequential_deps = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
parallel_deps = [(1, 2)]

# Create the problem variable
m = op.LpProblem("TaskScheduling", op.LpMinimize)

# Assigned CPU for task i
r = {i: op.LpVariable(f"r{i}", 0, len(J), op.LpInteger) for i in I}
# Scheduled start time of task i
t = {i: op.LpVariable(f"t{i}", 0, max_makespan, op.LpInteger) for i in I}
# Duration of task i
d = {i: op.LpVariable(f"d{i}", 1, max_duration, op.LpInteger) for i in I}
# Whether task i scheduled on CPU j has duration k
z = {(i, j, k): op.LpVariable(f"duration{i}{j}{k}", cat=op.LpBinary) for i, j, k in it.product(I, J, range(1, max_duration + 1))}
# Whether task i finishes before task j starts
sigma = {(i, j): op.LpVariable(f"sigma{i}{j}", cat=op.LpBinary) for i, j in it.product(I, I)}
# Whether CPU of task i (r_i) is less than that of task j
theta = {(i, j): op.LpVariable(f"theta{i}{j}", cat=op.LpBinary) for i, j in it.product(I, I)}
# Makespan
W = op.LpVariable("makespan", 0, max_makespan, op.LpInteger)

cons = [
    # Total makespan constraint
    {i: (t[i] + d[i] <= W, f"eq0_{i}") for i in I},
    # CPU assignment constraints
    {(i, j): (sigma[(i, j)] + sigma[(j, i)] <= 1, f"eq2_{i}{j}") for i, j in it.product(I, I) if i != j},
    {(i, j): (theta[(i, j)] + theta[(j, i)] <= 1, f"eq3_{i}{j}") for i, j in it.product(I, I) if i != j},
    {(i, j): (sigma[(i, j)] + sigma[(j, i)] + theta[(i, j)] + theta[(j, i)] >= 1, f"eq4_{i}{j}") for i, j in it.product(I, I) if i != j},
    # Relate time to CPU assignment
    {(i, j): (r[j] - r[i] - 1 - (theta[(i, j)] - 1) * len(J) >= 0, f"eq5_{i}{j}") for i, j in it.product(I, I) if i != j},
    {(i, j): (r[j] - r[i] - theta[(i, j)] * len(J) <= 0, f"eq6_{i}{j}") for i, j in it.product(I, I) if i != j},
    {(i, j): (t[i] + d[i] + (sigma[(i, j)] - 1) * max_makespan <= t[j], f"eq7_{i}{j}") for i, j in it.product(I, I) if i != j},
    # Sequential scheduling constraints
    {(i, j): (t[i] + d[i] <= t[j], f"eq8_{i}{j}") for (i, j) in sequential_deps},
    {(i, j): (sigma[(i, j)] == 1, f"eq9_{i}{j}") for (i, j) in sequential_deps},
    # Parallel scheduling constraints
    {(i, j): (t[i] == t[j], f"eq10_{i}{j}") for (i, j) in parallel_deps},
    {(i, j): (d[i] == d[j], f"eq11_{i}{j}") for (i, j) in parallel_deps},
    {(i, j): (r[i] != r[j], f"eq12_{i}{j}") for (i, j) in parallel_deps},
    {(i, j): (theta[(i, j)] + theta[(j, i)] >= 1, f"eq16_{i}{j}") for (i, j) in parallel_deps},
    # Associate task i, cpu j with duration k 
    {(i, j, k): (z[(i, j, k)] == (1 if runtime[(i, j)] == k else 0), f"eq17_{i}{j}{k}") for i, j, k in it.product(I, J, range(1, max_duration + 1))},
    {(i, j): (sum(z[(i, j, k)] for k in range(1, max_duration + 1)) == 1, f"eq18_{i}{j}") for i, j in it.product(I, J)},
]

# Add equations to the problem
m += W

for c in cons:
    for i in c:
        m += c[i]

# Solve the problem
m.solve()

# Print the optimized values
for v in m.variables():
    print(v.name, "=", v.varValue)

print("Optimal makespan:", W.varValue)

I’ve described the problem and my approach so far in the post above.