main.py

#!/usr/bin/env python

# MultiMachine Scheduling Problem
# ToDo: Automate Instance Generation

import sys, pickle, random, math
from collections import Counter

from pulp import LpVariable, LpBinary, lpSum, value, LpProblem, LpMaximize, LpAffineExpression

try:
    import path
except ImportError:
    pass
    
try:
    import dippy
except ImportError:
    try:
        import src.dippy as dippy
    except ImportError:
        import coinor.dippy as dippy
        
debugMode = False

# Automate instance generation here
# Do parsing of data file here

durationHistData = pickle.load(open("task_histogram.pkl", "rb"))
frequency = Counter(durationHistData)
totalEntries = len(durationHistData)

random.seed(2016)

probabilities = {}

for entry in frequency.most_common():
    probabilities[entry[0]] = float(entry[1])/float(totalEntries)

ranges = {}
rangeStart = 0.0

for key, value in probabilities.iteritems():
    ranges[key] = (rangeStart, rangeStart + value)
    rangeStart = rangeStart + value
    
def generateDuration():
    number = random.uniform(0.0, 1.0)
    for key, value in ranges.iteritems():
        if (number > value[0] and number <= value[1]):
            return key

numSensors = 2
timeSteps = 200
categoryOneCountPerSensor = 1
categoryTwoCountPerSensor = timeSteps/20
categoryThreeCount = int(math.ceil(0.09*timeSteps))
sensors = range(numSensors)
numActivities = categoryOneCountPerSensor*numSensors + \
                categoryTwoCountPerSensor*numSensors + \
                categoryThreeCount
activities = range(numActivities)
time = range(timeSteps)

                
# Activity Info: (category_k, duration_k, sensor_k, priority_k, e_k, l_k)
activityInfo = {}
for i in range(numActivities):
    activityInfo[i] = [0, 0, 0, 0.0, 0, 0]

activityCounter = 0
for i in sensors:
    for k in range(categoryOneCountPerSensor):
        activityInfo[activityCounter][0] = 1
        activityInfo[activityCounter][1] = generateDuration()
        activityInfo[activityCounter][2] = i
        activityInfo[activityCounter][3] = 1.0
        activityInfo[activityCounter][4] = 0
        activityInfo[activityCounter][5] = timeSteps
        activityCounter += 1
    for k in range(categoryTwoCountPerSensor):
        activityInfo[activityCounter][0] = 2
        activityInfo[activityCounter][1] = 1
        activityInfo[activityCounter][2] = i
        activityInfo[activityCounter][3] = 0.95
        activityInfo[activityCounter][4] = k*20-1 if k!=0 else 0
        activityInfo[activityCounter][5] = k*20+2
        activityCounter += 1
for k in range(categoryThreeCount):
    activityInfo[activityCounter][0] = 3
    activityInfo[activityCounter][1] = generateDuration()
    activityInfo[activityCounter][2] = 100
    activityInfo[activityCounter][3] = round(random.uniform(0,1),2)
    activityInfo[activityCounter][4] = 0
    activityInfo[activityCounter][5] = timeSteps
    activityCounter += 1

assert numActivities == activityCounter

print ">>> activityInfo generated"

categoryOneIndices = [] # mandatory indices
categoryTwoIndices = [] # category 2 indices
categoryThreeIndices = [] # category 3 indices
for k in range(numActivities):
    if (activityInfo[k][0] == 1):
        categoryOneIndices.append(k)
    else:
        if (activityInfo[k][0] == 2):
            categoryTwoIndices.append(k)
        else:
            categoryThreeIndices.append(k)
# For now, quality just depents on the activity
quality = [round(random.uniform(0,1),2) for _ in range(0, numActivities)]
indexSet = [(i, k, t) for i in sensors for k in activities for t in time]

xVars = []
for i in sensors:
    v = []
    for k in activities:
        w = []
        for t in time:
            w.append(LpVariable("I%d_K%d_T%d" % (i, k, t), cat=LpBinary))
        v.append(w)
    xVars.append(v)

print ">>> Defined xVars"

prob = dippy.DipProblem("Scheduling")

# Objective
prob += lpSum(-xVars[i][k][t] * quality[k] * activityInfo[k][1] * activityInfo[k][3] for i, k, t in indexSet), "min"

print ">>> Created objective"

# Temp variables for each activity
omegaVars = [LpVariable("T%d" % k, lowBound = 0, upBound = 1, cat='Continuous') for k in range(numActivities)]
# assignment constraints

for k in range(numActivities):
    prob += lpSum(xVars[i][k][t] for i in sensors for t in time) == omegaVars[k]
   
for j in categoryOneIndices:
    prob += omegaVars[j] == 1

for j in categoryTwoIndices + categoryThreeIndices:
    prob += omegaVars[j] <= 1

print ">>> Created Assignment Constraints" 

for i in sensors:
    for t in time:
        prob.relaxation[i] += lpSum(xVars[i][k][s] for k in activities for s in range(min(t-activityInfo[k][1]+1, t),t+1)) <= 1
        

print ">>> Created Activity Overlap constraints"

for k in categoryOneIndices:
    for i in sensors:
        for t in time:
            if activityInfo[k][2] != i:
                prob += xVars[i][k][t] == 0

for k in categoryTwoIndices:
    for i in sensors:
        for t in time:
            if activityInfo[k][2] != i:
                prob += xVars[i][k][t] == 0
            if (t < activityInfo[k][4] or t > activityInfo[k][5]):
                prob += xVars[i][k][t] == 0

print ">>> Added trivial constraints"

dippy.Solve(prob, {
    'doPriceCut': '1',
    'CutCGL' : '1',
#    'generateInitVars' : '1',
#    'logLevel': '3', 
})

Multimachine scheduling problem DipPy