From 17ce2f1f0ffd199c7f7d73bfaefd7846b792fecd Mon Sep 17 00:00:00 2001 From: Lars-Dominik Braun Date: Mon, 6 Mar 2017 14:10:17 +0100 Subject: Initial import --- .gitignore | 6 ++ README.rst | 25 ++++++++ ilpscheduling/__init__.py | 27 ++++++++ ilpscheduling/convert.py | 32 +++++++++ ilpscheduling/generate.py | 34 ++++++++++ ilpscheduling/model.py | 56 ++++++++++++++++ ilpscheduling/scheduler.py | 157 +++++++++++++++++++++++++++++++++++++++++++++ setup.py | 30 +++++++++ 8 files changed, 367 insertions(+) create mode 100644 .gitignore create mode 100644 README.rst create mode 100644 ilpscheduling/__init__.py create mode 100644 ilpscheduling/convert.py create mode 100644 ilpscheduling/generate.py create mode 100644 ilpscheduling/model.py create mode 100644 ilpscheduling/scheduler.py create mode 100644 setup.py 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', + ], + }, +) -- cgit v1.2.3