scheduling_linear_ordering: model for the one machine total weighted tardiness problem

    Model for the one machine total weighted tardiness problem
    using the linear ordering formulation

    Parameters:
        - J: set of jobs
        - p[j]: processing time of job j
        - d[j]: latest non-tardy time for job j
        - w[j]: weighted of job j; the objective is the sum of the weighted completion time

    Returns a model, ready to be solved.

def scheduling_linear_ordering(J,p,d,w):
    """
    scheduling_linear_ordering: model for the one machine total weighted tardiness problem

    Model for the one machine total weighted tardiness problem
    using the linear ordering formulation

    Parameters:
        - J: set of jobs
        - p[j]: processing time of job j
        - d[j]: latest non-tardy time for job j
        - w[j]: weighted of job j; the objective is the sum of the weighted completion time

    Returns a model, ready to be solved.
    """
    model = Model("scheduling: linear ordering")

    T,x = {},{} # tardiness variable; x[j,k] =1 if job j precedes job k, =0 otherwise
    for j in J:
        T[j] = model.addVar(vtype="C", name="T(%s)"%(j))
        for k in J:
            if j != k:
                x[j,k] = model.addVar(vtype="B", name="x(%s,%s)"%(j,k))

    for j in J:
        model.addCons(quicksum(p[k]*x[k,j] for k in J if k != j) - T[j] <= d[j]-p[j], "Tardiness(%r)"%(j))

        for k in J:
            if k <= j:
                continue
            model.addCons(x[j,k] + x[k,j] == 1, "Disjunctive(%s,%s)"%(j,k))

            for ell in J:
                if ell > k:
                    model.addCons(x[j,k] + x[k,ell] + x[ell,j] <= 2, "Triangle(%s,%s,%s)"%(j,k,ell))

    model.setObjective(quicksum(w[j]*T[j] for j in J), "minimize")


    model.data = x,T
    return model