""" permutationflowshop.py: model for the permutation flow shop problem 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 gurobipy import * 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)) model.update() for j in range(1,n+1): model.addConstr(quicksum(x[j,k] for k in range(1,n+1)) == 1, "Assign1(%s)"%(j)) model.addConstr(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.addConstr(f[i,k] <= s[i,k+1], "FinishStart(%s,%s)"%(i,k)) if i != m: model.addConstr(f[i,k] <= s[i+1,k], "Machine(%s,%s)"%(i,k)) model.addConstr(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], GRB.MINIMIZE) model.update() 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(): 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 "Opt.value=",model.ObjVal ### for (j,k) in sorted(x): ### if x[j,k].X > 0.5: ### print x[j,k].VarName,x[j,k].X ### ### for i in sorted(s): ### print s[i].VarName,s[i].X ### ### for i in sorted(f): ### print f[i].VarName,f[i].X # 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 x[j,k].X > 0.5])] print "optimal job permutation:",seq