Sage incorporates Python as a scripting language from which one can generate objects MixedIntegerLinearProgram objects. Both GLPK and CBC from the COIN-OR project can be installed as optional Sage packages and used as solvers. Coupled with the native features of Python, this approaches provides an interesting alternative to developing models using AMPL/GMPL.

# Dictionary of task durations indexed by (Job, Machine) tuples dur = { ('Paper 1','Blue') : 45, ('Paper 1','Yellow') : 10, ('Paper 2','Blue') : 20, ('Paper 2','Green') : 10, ('Paper 2','Yellow') : 34, ('Paper 3','Blue') : 12, ('Paper 3','Green') : 17, ('Paper 3','Yellow') : 28 } # Task sequencing indicated by pairs of (Job, Machine) tuples order = [ (('Paper 1','Blue'), ('Paper 1','Yellow')), (('Paper 2','Green'), ('Paper 2','Blue')), (('Paper 2','Blue'), ('Paper 2','Yellow')), (('Paper 3','Yellow'),('Paper 3','Blue')), (('Paper 3','Blue'), ('Paper 3','Green')) ] # TASKS are a list of (job,machine) tuples found from the keys for dur{} TASKS = dur.keys() # JOBS and MACHS are unduplicated lists of jobs and machines JOBS = sorted(list(set(zip(*TASKS)[0]))) MACHS = sorted(list(set(zip(*TASKS)[1]))) # Create MILP JobShop = MixedIntegerLinearProgram(maximization=False) # The objective is to minimize Makespan MakeSpan = JobShop.new_variable() JobShop.set_objective(MakeSpan[0]) # MakeSpan is an upper bound on all tasks x = JobShop.new_variable() [JobShop.add_constraint(x[t] + dur[t] - MakeSpan[0], max = 0) for t in TASKS] # Tasks must be complete in the specified order [JobShop.add_constraint(x[s] + dur[s] - x[t], max=0) for s,t in order] # Disjunctive constraints to avoid machine conflicts. This uses a # 'Big M' technique and a binary variable where y[s][t] = 0 implies # task s must finish before task t can start and y[s][t] = 1 implies # task t finishes before task s starts. CONFLICTS = [(s,t) for s in TASKS for t in TASKS if s<t and s[1]==t[1]] y = JobShop.new_variable(dim=2,vtype=JobShop.__BINARY) BigM = sum(dur[t] for t in TASKS) [JobShop.add_constraint(BigM*y[s][t] + x[t] - x[s] - dur[s], min=0) for s,t in CONFLICTS] [JobShop.add_constraint(BigM*(1-y[s][t]) + x[s] - x[t] - dur[t], min=0) for s,t in CONFLICTS] JobShop.solve('Coin')

## No comments:

## Post a Comment