rcs.py

Go to the documentation of this file.

 
"""
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""
from pyscipopt import Model, quicksum, multidict
 
 
def rcs(J, P, R, T, p, c, a, RUB):
    """rcs -- model for the resource constrained scheduling problem
    Parameters:
        - J: set of jobs
        - P: set of precedence constraints between jobs
        - R: set of resources
        - T: number of periods
        - p[j]: processing time of job j
        - c[j,t]: cost incurred when job j starts processing on period t.
        - a[j,r,t]: resource r usage for job j on period t (after job starts)
        - RUB[r,t]: upper bound for resource r on period t
    Returns a model, ready to be solved.
    """
    model = Model("resource constrained scheduling")
 
    s, x = {}, {}  # s - start time variable;  x=1 if job j starts on period t
    for j in J:
        s[j] = model.addVar(vtype="C", name="s(%s)" % j)
        for t in range(1, T - p[j] + 2):
            x[j, t] = model.addVar(vtype="B", name="x(%s,%s)" % (j, t))
 
    for j in J:
        # job execution constraints
        model.addCons(quicksum(x[j, t] for t in range(1, T - p[j] + 2)) == 1, "ConstrJob(%s,%s)" % (j, t))
 
        # start time constraints
        model.addCons(quicksum((t - 1) * x[j, t] for t in range(2, T - p[j] + 2)) == s[j], "ConstrJob(%s,%s)" % (j, t))
 
    # resource upper bound constraints
    for t in range(1, T - p[j] + 2):
        for r in R:
            model.addCons(
                quicksum(a[j, r, t - t_] * x[j, t_] for j in J for t_ in
                         range(max(t - p[j] + 1, 1), min(t + 1, T - p[j] + 2))) \
                <= RUB[r, t], "ResourceUB(%s)" % t)
 
    # time (precedence) constraints, i.e., s[k]-s[j] >= p[j]
    for (j, k) in P:
        model.addCons(s[k] - s[j] >= p[j], "Precedence(%s,%s)" % (j, k))
 
    model.setObjective(quicksum(c[j, t] * x[j, t] for (j, t) in x), "minimize")
 
    model.data = x, s
    return model
 
 
def make_1r():
    """creates example data set 1"""
    J, p = multidict({  # jobs, processing times
        1: 1,
        2: 3,
        3: 2,
        4: 2,
    })
    P = [(1, 2), (1, 3), (2, 4)]
    R = [1]
    T = 6
    c = {}
    for j in J:
        for t in range(1, T - p[j] + 2):
            c[j, t] = 1 * (t - 1 + p[j])
    a = {
        (1, 1, 0): 2,
        (2, 1, 0): 2, (2, 1, 1): 1, (2, 1, 2): 1,
        (3, 1, 0): 1, (3, 1, 1): 1,
        (4, 1, 0): 1, (4, 1, 1): 2,
    }
    RUB = {(1, 1): 2, (1, 2): 2, (1, 3): 1, (1, 4): 2, (1, 5): 2, (1, 6): 2}
    return (J, P, R, T, p, c, a, RUB)
 
 
def make_2r():
    """creates example data set 2"""
    J, p = multidict({  # jobs, processing times
        1: 2,
        2: 2,
        3: 3,
        4: 2,
        5: 5,
    })
    P = [(1, 2), (1, 3), (2, 4)]
    R = [1, 2]
    T = 6
    c = {}
    for j in J:
        for t in range(1, T - p[j] + 2):
            c[j, t] = 1 * (t - 1 + p[j])
    a = {
        # resource 1:
        (1, 1, 0): 2, (1, 1, 1): 2,
        (2, 1, 0): 1, (2, 1, 1): 1,
        (3, 1, 0): 1, (3, 1, 1): 1, (3, 1, 2): 1,
        (4, 1, 0): 1, (4, 1, 1): 1,
        (5, 1, 0): 0, (5, 1, 1): 0, (5, 1, 2): 1, (5, 1, 3): 0, (5, 1, 4): 0,
        # resource 2:
        (1, 2, 0): 1, (1, 2, 1): 0,
        (2, 2, 0): 1, (2, 2, 1): 1,
        (3, 2, 0): 0, (3, 2, 1): 0, (3, 2, 2): 0,
        (4, 2, 0): 1, (4, 2, 1): 2,
        (5, 2, 0): 1, (5, 2, 1): 2, (5, 2, 2): 1, (5, 2, 3): 1, (5, 2, 4): 1,
    }
    RUB = {(1, 1): 2, (1, 2): 2, (1, 3): 2, (1, 4): 2, (1, 5): 2, (1, 6): 2, (1, 7): 2,
           (2, 1): 2, (2, 2): 2, (2, 3): 2, (2, 4): 2, (2, 5): 2, (2, 6): 2, (2, 7): 2}
    return (J, P, R, T, p, c, a, RUB)
 
 
if __name__ == "__main__":
    (J, P, R, T, p, c, a, RUB) = make_2r()
    model = rcs(J, P, R, T, p, c, a, RUB)
    model.optimize()
    x, s = model.data
 
    print("Optimal value:", model.getObjVal())
    for (j, t) in x:
        if model.getVal(x[j, t]) > 0.5:
            print(x[j, t].name, "=", model.getVal(x[j, t]))
 
    for j in s:
        if model.getVal(s[j]) > 0.:
            print(s[j].name, "=", model.getVal(s[j]))