summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLars-Dominik Braun <lars@6xq.net>2017-03-06 14:10:17 +0100
committerLars-Dominik Braun <lars@6xq.net>2017-03-06 14:10:17 +0100
commit17ce2f1f0ffd199c7f7d73bfaefd7846b792fecd (patch)
tree3c645f67f8a9c3e7103640c41aaa803ebfdc080b
downloadilp-scheduling-17ce2f1f0ffd199c7f7d73bfaefd7846b792fecd.tar.gz
ilp-scheduling-17ce2f1f0ffd199c7f7d73bfaefd7846b792fecd.tar.bz2
ilp-scheduling-17ce2f1f0ffd199c7f7d73bfaefd7846b792fecd.zip
Initial import
-rw-r--r--.gitignore6
-rw-r--r--README.rst25
-rw-r--r--ilpscheduling/__init__.py27
-rw-r--r--ilpscheduling/convert.py32
-rw-r--r--ilpscheduling/generate.py34
-rw-r--r--ilpscheduling/model.py56
-rw-r--r--ilpscheduling/scheduler.py157
-rw-r--r--setup.py30
8 files changed, 367 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..19f46f5
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,6 @@
+*.py[co]
+*.sw?
+*.egg-info/
+gurobi.log
+gurobi.lic
+sandbox/
diff --git a/README.rst b/README.rst
new file mode 100644
index 0000000..cd1afdd
--- /dev/null
+++ b/README.rst
@@ -0,0 +1,25 @@
+Generic worker/slot scheduling using ILP
+========================================
+
+Assigns workers to slots with the following constraints:
+
+1. Number of slots and workers per slots
+2. Slots per worker
+3. Workers preferences (using priorities)
+
+Optimization is using these targets:
+
+a. Evenly distributed workers across slots
+b. Respect worker’s priorities
+
+Dependencies
+------------
+
+ilpscheduling depends on python and gurobi_.
+
+Using a custom licence path for gurobi is possible using::
+
+ export GRB_LICENSE_FILE=`pwd`/gurobi.lic
+
+.. _gurobi: http://www.gurobi.com/
+
diff --git a/ilpscheduling/__init__.py b/ilpscheduling/__init__.py
new file mode 100644
index 0000000..bd6693f
--- /dev/null
+++ b/ilpscheduling/__init__.py
@@ -0,0 +1,27 @@
+# vim: set fileencoding=utf-8 :
+
+"""
+Simple, ILP-based worker-slot-scheduling that optimizes for similar group sizes
+and worker’s priorities.
+
+Depends on gurobipy.
+"""
+
+import argparse
+import scheduler
+import generate
+from .convert import *
+
+def main ():
+ parser = argparse.ArgumentParser(description='ILP worker scheduling.')
+ subparsers = parser.add_subparsers ()
+
+ scheduler.addParser (subparsers)
+ importekvvParser = subparsers.add_parser ('importekvv', help='Import XML files from ekvv')
+ importekvvParser.add_argument('files', nargs='+', help='input file')
+ importekvvParser.set_defaults (func=mainImportEkvv)
+ generate.addParser (subparsers)
+
+ args = parser.parse_args()
+ args.func (args)
+
diff --git a/ilpscheduling/convert.py b/ilpscheduling/convert.py
new file mode 100644
index 0000000..f95dabf
--- /dev/null
+++ b/ilpscheduling/convert.py
@@ -0,0 +1,32 @@
+# vim: set fileencoding=utf-8 :
+
+import sys, yaml
+from lxml import etree
+from lxml import objectify
+
+def mainImportEkvv (args):
+ """
+ Parse ekvv participant management lists
+ XXX: priorities are not properly imported yet and need to be “normalized”
+
+ See http://ekvv.uni-bielefeld.de/wiki/en/Export_von_Anmeldelisten_für_Platzvergabeverfahren_im_XML_Format
+ """
+
+ worker = {}
+ limit = {}
+
+ for f in args.files:
+ with open (f, 'r') as fd:
+ tree = objectify.parse (fd)
+ root = tree.getroot ()
+ slotid = root.get ('id')
+ workerlist = root.teilnehmerliste
+ limit[slotid] = int (workerlist.get ('teilnehmerbegrenzung'))
+ for t in workerlist.teilnehmer:
+ wid = t.get ('matrikelnummer')
+ worker.setdefault (wid, {})
+ worker[wid][slotid] = int (t.get ('prioritaet'))
+
+ yaml.dump ({'worker': worker, 'slots': limit, 'env': {'minSlots': len (limit), 'maxSlots': len (limit)}}, sys.stdout)
+
+
diff --git a/ilpscheduling/generate.py b/ilpscheduling/generate.py
new file mode 100644
index 0000000..b9d1cef
--- /dev/null
+++ b/ilpscheduling/generate.py
@@ -0,0 +1,34 @@
+# vim: set fileencoding=utf-8 :
+
+import random, yaml, sys
+from model import WorkerSlotModel
+
+def main (args):
+ numSlots = args.slots
+ numWorker = args.worker
+ minDatesPerStudent = 1
+ maxDatesPerStudent = 3
+
+ worker = {}
+ slots = {}
+
+ for i in range (numSlots):
+ slots[i] = {'max': args.slotLimit, 'min': 0}
+
+ prio = list (range (1, numSlots+1))
+ for i in range (numWorker):
+ keys = slots.keys ()
+ random.shuffle (keys)
+ s = random.randint (minDatesPerStudent, maxDatesPerStudent)
+ worker[i] = {'prio': dict (zip (keys[:s], prio[:s])), 'slots': {'min': 1, 'max': 1}}
+
+ data = WorkerSlotModel (slots, worker, {'minSlots': 0, 'maxSlots': len (slots)})
+ data.dump (sys.stdout)
+
+def addParser (subparsers):
+ parser = subparsers.add_parser ('generate', help='Generate random testcase')
+ parser.add_argument('--slots', '-s', type=int, default=5)
+ parser.add_argument('--worker', '-w', type=int, default=60)
+ parser.add_argument('--slot-limit', '-l', dest='slotLimit', type=int, default=12, help='Max number of worker per slot')
+ parser.set_defaults (func=main)
+
diff --git a/ilpscheduling/model.py b/ilpscheduling/model.py
new file mode 100644
index 0000000..baa02d1
--- /dev/null
+++ b/ilpscheduling/model.py
@@ -0,0 +1,56 @@
+# vim: set fileencoding=utf-8 :
+
+import yaml
+
+class WorkerSlotModel:
+ def __init__ (self, slots, worker, env):
+ self._slots = slots
+ self._worker = worker
+ self._env = env
+
+ # generated properties, public, read-only
+ self.slotNames = set (slots.keys ())
+ assert len (self.slotNames) == len (slots.keys ()), "slot names must be unique"
+ self.workerNames = set (worker.keys ())
+ assert len (self.workerNames) == len (worker.keys ()), "worker names must be unique"
+ self.minTotalSlots = self._env.get ('minSlots', 0)
+ self.maxTotalSlots = self._env.get ('maxSlots', len (self.slotNames))
+
+ @classmethod
+ def fromYaml (obj, fd):
+ """
+ Import from YAML file. Structured like this:
+
+ """
+ data = yaml.load (fd)
+ o = obj (data['slots'], data['worker'], data.get ('env', {}))
+ return o
+
+ def available (self, worker, slot):
+ """
+ Is worker available for slot?
+ """
+ return self.priority (worker, slot) is not None
+
+ def priority (self, worker, slot):
+ """
+ Get worker’s preferences/priority for slot, priority is higher for
+ smaller numbers and must be >= 1
+ """
+ return self._worker[worker]['prio'].get (slot, None)
+
+ def maxSlots (self, worker):
+ return self._worker[worker]['slots']['max']
+
+ def minSlots (self, worker):
+ return self._worker[worker]['slots']['min']
+
+ def maxWorker (self, slot):
+ return self._slots[slot]['max']
+
+ def minWorker (self, slot):
+ return self._slots[slot]['min']
+
+ def dump (self, fd):
+ yaml.dump ({'worker': self._worker, 'slots': self._slots, 'env': self._env}, fd)
+
diff --git a/ilpscheduling/scheduler.py b/ilpscheduling/scheduler.py
new file mode 100644
index 0000000..c854be5
--- /dev/null
+++ b/ilpscheduling/scheduler.py
@@ -0,0 +1,157 @@
+# vim: set fileencoding=utf-8 :
+
+from gurobipy import *
+
+class ILPUnsolvable (Exception):
+ pass
+
+class ILPScheduler:
+ def __init__ (self, data):
+ """
+ :param data: WorkerSlotModel
+ """
+ self.data = data
+ self.model = Model("scheduling")
+
+ def optimize (self):
+ """
+ Run optimization pass
+ """
+ data = self.data
+ slotNames = data.slotNames
+ workerNames = data.workerNames
+
+ availability = { (w, s) : data.available (w, s) for w in workerNames for s in slotNames }
+
+ model = self.model
+
+ # x[(w,s)] == 1 if worker w is assigned to slot s
+ x = model.addVars(availability.keys(), ub=availability, vtype=GRB.BINARY, name='x')
+
+ # every worker needs slots
+ slotsPerWorker = model.addVars (workerNames, vtype=GRB.INTEGER, name='slotsPerWorker')
+ model.addConstrs((x.sum(w, '*') == slotsPerWorker[w] for w in workerNames), name='slotsPerWorkerConstr')
+
+ model.addConstrs((slotsPerWorker[w] >= data.minSlots (w) for w in workerNames), name='minSlotsPerWorkerConstr')
+ model.addConstrs((slotsPerWorker[w] <= data.maxSlots (w) for w in workerNames), name='maxSlotsPerWorkerConstr')
+
+ # but the number of worker per slot is limited
+ workerPerSlot = model.addVars (slotNames, vtype=GRB.INTEGER, name='workerPerSlot')
+ model.addConstrs ((x.sum('*', s) == workerPerSlot[s] for s in slotNames), name='workerPerSlotAssign')
+
+ model.addConstrs ((workerPerSlot[s] <= data.maxWorker (s) for s in slotNames), name='maxWorkerPerSlotConstr')
+ model.addConstrs ((workerPerSlot[s] >= data.minWorker (s) for s in slotNames), name='minWorkerPerSlotConstr')
+
+ # also the number of slots is limited
+ slotUsed = model.addVars (slotNames, vtype=GRB.BINARY, name='slotUsed')
+ for s in slotNames:
+ # slotUsed[s] is True iff there is at least one worker per slot
+ model.addGenConstrOr (slotUsed[s], [x[(w, s)] for w in workerNames], name='slotUsedConstr')
+ totalSlotsUsed = model.addVar (vtype=GRB.INTEGER)
+ model.addConstr (totalSlotsUsed == slotUsed.sum ('*'), name='totalSlotsUsedConstr')
+
+ model.addConstr(totalSlotsUsed >= data.minTotalSlots, name='minTotalSlotsUsedConstr')
+ model.addConstr(totalSlotsUsed <= data.maxTotalSlots, name='maxTotalSlotsUsedConstr')
+
+ # optimize for these constraints, more important first
+ # - similar-sized slots: minimize diff of each workerPerSlot and
+ # maxWorkerPerSlot. minimizing maxWorkerPerSlot is not sufficient,
+ # because solution 4/4/1 and 3/4/2 are the same
+ maxWorkerPerSlot = model.addVar (vtype=GRB.INTEGER)
+ # maxWorkerPerSlot=max(workerPerSlot)
+ model.addGenConstrMax (maxWorkerPerSlot, workerPerSlot, name='maxWorkerPerSlotConstr')
+ workerMaxDiff = model.addVars (slotNames, vtype=GRB.INTEGER, name='workerMaxDiff')
+ model.addConstrs ((workerMaxDiff[s] == maxWorkerPerSlot-workerPerSlot[s] for s in slotNames), name='workerMaxDiffConstr')
+ cost1 = model.addVar (vtype=GRB.INTEGER)
+ model.addGenConstrMax (cost1, workerMaxDiff, name='cost1Constr')
+
+ # - prefer solutions that fulfil most people’s wishes (everyone gets what he
+ # wants) by minimizing sum of priority.
+ totalPriority = model.addVar (vtype=GRB.INTEGER)
+ maxTotalPriority = 0
+ terms = []
+ for w in workerNames:
+ for s in slotNames:
+ p = data.priority (w, s)
+ if p is not None:
+ terms.append (x[w,s]*p)
+ maxTotalPriority += p
+ model.addConstr (totalPriority == quicksum(terms), 'totalPriority')
+
+ # - try to keep worker pairs together
+# pairs = [(self.workers[0], self.workers[1])]
+# terms = []
+# for a, b in pairs:
+# for j, s in enumerate (slotNames):
+# terms.append (
+ # XXX: todo
+
+ # combine everything into a single cost function, because multi-objective
+ # solving sucks
+ totalCost = model.addVar (vtype=GRB.INTEGER)
+ # worker per slot is more important, so multiply with max sum of priority
+ model.addConstr (totalCost == cost1*maxTotalPriority + totalPriority, 'totalCost')
+ model.ModelSense = GRB.MINIMIZE
+ model.setObjective (totalCost)
+
+ model.optimize ()
+ status = model.Status
+ if status in (GRB.Status.INF_OR_UNBD, GRB.Status.INFEASIBLE, GRB.Status.UNBOUNDED):
+ raise ILPUnsolvable ()
+ if status != GRB.Status.OPTIMAL:
+ print ('not optimal')
+
+ print ('total priority is', totalPriority.X)
+ print ('max worker per slot is', maxWorkerPerSlot.X)
+ print ('cost1 is', cost1.X)
+ print ('total cost is', totalCost.X)
+ for s in slotNames:
+ print ('slotUsed', s, slotUsed[s].X)
+ print ('totalSlotsUsed', totalSlotsUsed.X)
+ return x, workerPerSlot
+
+def firstNonNull (l):
+ for i in range (len (l)):
+ if l[i]:
+ return i
+
+def mainOptimize (args):
+ import sys
+ from tabulate import tabulate
+ from model import WorkerSlotModel
+
+ # read data
+ with open (args.file, 'r') as fd:
+ data = WorkerSlotModel.fromYaml (fd)
+
+ sched = ILPScheduler (data)
+ try:
+ x, groupSize = sched.optimize ()
+ except ILPUnsolvable:
+ print ('unsolvable')
+ return
+
+ tbl = []
+ for w in data.workerNames:
+ r = [w]
+ for s in data.slotNames:
+ if groupSize[s].X > 0:
+ if x[w,s].X == 1:
+ r.append (data.priority (w, s))
+ else:
+ r.append ('')
+ tbl.append (r)
+ # skip row description, thus [1:]
+ tbl.sort (key=lambda x: firstNonNull (x[1:]))
+ hdr = []
+ for s in data.slotNames:
+ if groupSize[s].X > 0:
+ hdr.append ('{} ({})'.format (s, groupSize[s].X))
+
+ print (tabulate (tbl, headers=hdr))
+
+def addParser (subparsers):
+ parser = subparsers.add_parser ('optimize', help='Optimize schedule')
+ parser.add_argument('file', help='input file')
+ parser.set_defaults (func=mainOptimize)
+
diff --git a/setup.py b/setup.py
new file mode 100644
index 0000000..fbada48
--- /dev/null
+++ b/setup.py
@@ -0,0 +1,30 @@
+# Always prefer setuptools over distutils
+from setuptools import setup, find_packages
+# To use a consistent encoding
+from codecs import open
+from os import path
+
+here = path.abspath(path.dirname(__file__))
+
+# Get the long description from the README file
+with open(path.join(here, 'README.rst'), encoding='utf-8') as f:
+ long_description = f.read()
+
+setup(
+ name='ilpscheduling',
+ version='0.1',
+ description='ILP scheduling using gurobipy',
+ long_description=long_description,
+ #url='https://github.com/pypa/sampleproject',
+ # Author details
+ author='Lars-Dominik Braun',
+ author_email='lars@6xq.net',
+ license='MIT',
+ packages=find_packages(exclude=['contrib', 'docs', 'tests']),
+ #install_requires=['gurobipy'],
+ entry_points={
+ 'console_scripts': [
+ 'ilpsched=ilpscheduling:main',
+ ],
+ },
+)