pfs.py

Go to the documentation of this file.

 
"""
Use a position index formulation for modeling the permutation flow
shop problem, with the objective of minimizing the makespan (maximum
completion time).
 
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""
import math
import random
from pyscipopt import Model, quicksum, multidict
 
def permutation_flow_shop(n,m,p):
    """gpp -- model for the graph partitioning problem
    Parameters:
        - n: number of jobs
        - m: number of machines
        - p[i,j]: processing time of job i on machine j
    Returns a model, ready to be solved.
    """
    model = Model("permutation flow shop")
 
    x,s,f = {},{},{}
    for j in range(1,n+1):
        for k in range(1,n+1):
            x[j,k] = model.addVar(vtype="B", name="x(%s,%s)"%(j,k))
 
    for i in range(1,m+1):
        for k in range(1,n+1):
            s[i,k] = model.addVar(vtype="C", name="start(%s,%s)"%(i,k))
            f[i,k] = model.addVar(vtype="C", name="finish(%s,%s)"%(i,k))
 
    for j in range(1,n+1):
        model.addCons(quicksum(x[j,k] for k in range(1,n+1)) == 1, "Assign1(%s)"%(j))
        model.addCons(quicksum(x[k,j] for k in range(1,n+1)) == 1, "Assign2(%s)"%(j))
 
    for i in range(1,m+1):
        for k in range(1,n+1):
            if k != n:
                model.addCons(f[i,k] <= s[i,k+1], "FinishStart(%s,%s)"%(i,k))
            if i != m:
                model.addCons(f[i,k] <= s[i+1,k], "Machine(%s,%s)"%(i,k))
 
            model.addCons(s[i,k] + quicksum(p[i,j]*x[j,k] for j in range(1,n+1)) <= f[i,k],
                            "StartFinish(%s,%s)"%(i,k))
 
    model.setObjective(f[m,n], "minimize")
 
    model.data = x,s,f
    return model
 
 
def make_data(n,m):
    """make_data: prepare matrix of m times n random processing times"""
    p = {}
    for i in range(1,m+1):
        for j in range(1,n+1):
            p[i,j] = random.randint(1,10)
    return p
 
 
def example():
    """creates example data set"""
    proc = [[2,3,1],[4,2,3],[1,4,1]]
    p = {}
    for i in range(3):
        for j in range(3):
            p[i+1,j+1] = proc[j][i]
    return p
 
 
if __name__ == "__main__":
    random.seed(1)
    n = 15
    m = 10
    p = make_data(n,m)
 
    # n = 3
    # m = 3
    # p = example()
    print("processing times (%s jobs, %s machines):" % (n,m))
    for i in range(1,m+1):
        for j in range(1,n+1):
            print(p[i,j],)
        print
 
    model = permutation_flow_shop(n,m,p)
    # model.write("permflow.lp")
    model.optimize()
    x,s,f = model.data
    print("Optimal value:", model.getObjVal())
 
    
 
    # x[j,k] = 1 if j is the k-th job; extract job sequence:
    seq = [j for (k,j) in sorted([(k,j) for (j,k) in x if model.getVal(x[j,k]) > 0.5])]
    print("optimal job permutation:",seq)