from ortools.linear_solver.pywraplp import Solver
# cost[c][j] = cost for CPU c to run job j
cost = [[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95]]
clusters = [
[0, 2, 4],
[1, 3, 5]
]
num_cpus = len(cost)
num_jobs = len(cost[0])
solver = Solver('mip_debug', Solver.CBC_MIXED_INTEGER_PROGRAMMING)
# x[c, j] if CPU c gets job j
x = {}
for c in range(num_cpus):
for j in range(num_jobs):
x[c, j] = solver.IntVar(0, 1, f'cpu {c} gets job {j}')
# Each cpu gets at most one job
for c in range(num_cpus):
solver.Add(
sum(x[c, j] for j in range(num_jobs)) == 1
)
# Each job gets exactly one CPU
for j in range(num_jobs):
solver.Add(
sum(x[c, j] for c in range(num_cpus)) == 1
)
# Each cluster gets at most two jobs
for cluster in clusters:
solver.Add(
sum(x[c, j] for c in cluster for j in range(num_jobs)) <= 2
)
total_cost = sum(x[c, j] * cost[c][j] for c in range(num_cpus) for j in range(num_jobs))
solver.Minimize(total_cost)
if solver.Solve() == Solver.OPTIMAL:
print([v for v in x.values() if v.solution_value() == 1])
print('Min cost:', total_cost.solution_value())
else:
print('No solution!')