Docker Container Scheduling as a Knapsack Problem in Julia/JuMP

docker_knapsack.jl

using JuMP
using Cbc

#=
We pass in the variable "pools" in this format that goes through a separate
pre-processing script that pipes JSON to a Julia JSON loader.


{
    "awesome-pool-prod": {
        "quantity": 3,        // Number of containers in the pool
        "memory": 1000,       // Megabytes
        "cpu": 30,            // Average cpu utilization in units of "percentage of a core"
        "inbound": 3.14159,   // MB/s
        "outbound": 2.7182818 // MB/s
    },
    {
        "awesome-pool-stage": {
        "quantity": 1, 
        "memory": 303, 
        "cpu": 11.2,
        "inbound": 3.14159, 
        "outbound": 2.7182818
    }
}

=#


# Build a list of the string keys of the pools. This allows us to identify
# each pool with an integer index, and we can convert that index to the
# pool string id by using i_keys[i]
i_keys = collect(keys(pools))

pool_count = length(pools)

m = Model(
    # CBC solver is open-soucre. Use an MILP solver of your choice.
    solver=CbcSolver(
        threads=Base.CPU_CORES,
    )
)

# Main decision variable
# How many instances from a pool are assigned to each host
@defVar(m, x[1:pool_count, 1:HOST_COUNT] >= 0, Int)
# Secondary decision variable - the max cpu usage across hosts
@defVar(m, cpu_ceil <= HOST_PROCESSOR)

for i in 1:pool_count
    # Constraint one: Assign each container in a pool to a host.
    @addConstraint(m,
        pools[i_keys[i]]["quantity"] == sum{x[i, j], j=1:HOST_COUNT}
    )

    # Constraint 2: Basically "No containers from the same pool on same host",
    # but scaled to pool_count > HOST_COUNT
    ceiling = ceil(pools[i_keys[i]]["quantity"] / HOST_COUNT)
    for j in 1:HOST_COUNT
        setUpper(x[i, j], ceiling)
    end
end

for j in 1:HOST_COUNT
    @addConstraints(m, begin
        # Note: All variable that end with "_LIMIT" are a multiple times the actual
        # host capacity in order to account for fluctuations. I used limit = .6 * capacity.
        
        # Constraint 3: Memory
        sum{pools[i_keys[i]]["memory"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["inbound"] > 0} <= HOST_MEMORY_LIMIT
        # Constraint 4: Inbound bandwidth
        sum{pools[i_keys[i]]["inbound"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["inbound"] > 0} <= HOST_INBOUND_LIMIT
        # Constraint 5: Outbound bandwidth
        sum{pools[i_keys[i]]["outbound"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["outbound"] > 0} <= HOST_OUTBOUND_LIMIT
        # Constraint 5: Total CPU usage. Note that it is less than a variable
        # that we minimize.
        sum{pools[i_keys[i]]["cpu"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["cpu"] > 0} <= cpu_ceil
    end)
end

# Overall goal: Minimize the highest CPU usage across hosts. 
@setObjective(m, Min, cpu_ceil)
status = solve(m)

if status != :Optimal
    println("Infeasible. Try adding more hosts.")
    exit(1)
end

# Format results by calling getValue() on the variables