pyconuk/conferencescheduler

A Python tool to assist the task of scheduling a conference http://conference-scheduler.readthedocs.org

Conference Scheduler

Overview

A Python tool to assist the task of scheduling a conference which:

• Can take an existing schedule and validate it against a set of constraints
• Can calculate a new valid, optimal schedule
• Can calculate a new, valid schedule also optimised to be the minimum change necessary from another given schedule
• Has the resources, constraints and optimisations defined below built in
• Has a simple mechanism for defining new constraints and optimisations
• Is a standalone tool which takes simple data types as input and produces simple data types as output (i.e. does no IO or presentation)

The full documentation can be found at conference-scheduler.readthedocs.org.

Terms

• Slot - a combination of room and period
• Session - an ordered series of slots (e.g. 'the session in room 1 between coffee and lunch on Friday')
• Event - a talk or workshop
• Demand - the predicted size of audience for an event
• Capacity - the capacity of venues

Constraints

• All events must be scheduled
• A slot may only have a maximum of one event scheduled
• An event must not be scheduled in a slot for which it has been marked as unavailable
• An event must not be scheduled at the same time as another event for which it has been marked not to clash
• An event may be tagged and, if so, must be scheduled in a session where it shares at least one tag with all other events in that session

Optimisation

Two options:

• The sum of 'potential disappointments' should be minimised where 'potential disappointments' is defined as the excess of demand over room capacity for every scheduled event
• Minimise the number of changes from a given schedule.

Examples

Some examples of situations which have arisen at previous conferences and could be handled by the unavailability, clashing and tagging constraints:

• A conference organiser says "Talks X and Y are on similar subject matter and likely to appeal to a similar audience. Let's try not to schedule them against each other."
• A conference organiser says "Talks X, Y and Z are likely to appeal to a similar audience. Let's try to schedule them sequentially in the same room so that we minimise the movement of people from one room to another."
• A conference organiser says "The audience for Talk X would benefit greatly from the speech-to-text provision. Let's schedule that one in the main hall."
• A potential session chair says "I'd like to attend workshop X, so please don't schedule me to chair a session that clashes with it."
• A potential session chair says "I'm happy to chair a session but I've never done it before, so please don't schedule me in the main hall."
• A speaker says "I'd like to attend talk X, so please don't schedule my talk in the same slot."
• A first-time speaker is assigned a mentor and requests that the mentor chairs the session in which they are scheduled to give their talk.

Acknowledgements

This repository was inspired by a talk given by David MacIver at PyCon UK 2016: http://2016.pyconuk.org/talks/easy-solutions-to-hard-problems/

conferencescheduler's Issues

Optimise for minimal disappointments

Use datetime rather than string for Slot.starts_at

How-To: Format the scheduler output

Write a How-To on getting the schedule output into various formats - possibly .csv, excel, yaml, json

Unique ID for events and slots

Currently, the scheduler uses the index of an event or slot in the relevant list as the event/slot id.

However, this causes problems over time as the events and slots lists change (e.g. new events are added, rooms become unavailable) and the position of a given event or slot within the lists changes.

Instead, we should accept id codes for both and assign them if missing. For events, this could be a UUID4 code. For slots, a hash of the room, start time and duration.

Optimise for least changes

from an existing schedule

Use bumpversion

In the comments at https://blog.ionelmc.ro/2014/05/25/python-packaging/ Ionel Cristian Mărieș mentions using bumpversion to manage the versioning of libraries and his cookiecutter templates include the configuration of that tool.

There's also a nice write-up of it by Atlassian: https://developer.atlassian.com/blog/2016/02/bumpversion-is-automation-for-semantic-versioning/

I suggest we replace version.py and use this tool instead.

Event Methods

We have created an Event class - largely because we realised that an Event's state needs to change after it has been initialised (its unavailability). However, we are still manipulating its unavailability attribute directly within our code.

I suggest that, instead, we should create getter/setter methods to provide some isolation. My initial thoughts are something like the following:

def set_unavailable_for_slot(self, slot):
    """Sets the event to be unavailable for the given slot"""

def set_unavailable_at(self, unavailable_from, unavailable_until):
    """Sets the event to be unavailable for a period of time"""

def set_to_avoid(self, event):
    """Sets the event's unavailability so as to avoid a clash with the given event"""

def is_unavailable_for(self, slot):
    """A boolean returning true if the event is unavailable for the given slot, false otherwise"""

Possible bug in constraint

As noted by @alexwlchan in #54

L45 conference_scheduler/lp_problem/constraints.py

    if events[event].tags is not []:

Did you mean to test identity here, or just equality? Since the second half of the comparison will be created every time, I think this always returns True:

>>> [] is not []
True
>>> x = []
>>> x is not []
True

Sort out the return type of solution

We have two types of solution at the moment:

1. the numpy arrays that we pass into the constraint functions
2. the content of the generator that's returned by scheduler.solution

We also have a function to convert between type 1 solutions and a schedule (scheduler.schedule_to_solution and scheduler.solution_to_schedule), and another to convert type 2 solutions to a schedule (scheduler.schedule)

This needs tidying up and making consistent.

Have sessions in slots

In a similar vain to unavailability etc... The problem is fundamentally one of events and slots. As sessions are collections of slots we could just include a session attribute in the slot class. This just means that the only variables that get passed to the mathematical problem are events and slots (which makes things clean).

(We could keep the sessions class as they are in case they're useful further down the line and ensure through preprocessing that the sessions instances are all correctly in the slot sessions attribute.)

Use lpsum function in place of plain addition

Similar to #55 the lpsum function could be used in place of plain addition for the the remaining constraint functions and also the optimisation functions

Issue with Slot times and datetime while running tutorial code

Hi,

I am running the tutorial code, and I am getting an error when I get to the following lines.

schedule = scheduler.schedule(events, slots)

The issue originates from line 104 in the utils.py file:

startdate = datetime.datetime.strptime(slot.starts_at, '%d-%b-%Y %H:%M')

And the error says: TypeError: strptime() argument 1 must be str, not datetime.datetime

Here is all the code I am running:

`from datetime import datetime
from conference_scheduler.resources import Slot, Event
from conference_scheduler.resources import Slot, Event

talk_slots = [Slot(venue='Big', starts_at=datetime(2016, 9, 15, 9, 30), duration=30, session="A", capacity=200),
Slot(venue='Big', starts_at=datetime(2016, 9, 15, 10, 0), duration=30, session="A", capacity=200),
Slot(venue='Small', starts_at=datetime(2016, 9, 15, 9, 30), duration=30, session="B", capacity=50),
Slot(venue='Small', starts_at=datetime(2016, 9, 15, 10, 0), duration=30, session="B", capacity=50),
Slot(venue='Big', starts_at=datetime(2016, 9, 15, 12, 30), duration=30, session="C", capacity=200),
Slot(venue='Big', starts_at=datetime(2016, 9, 15, 13, 0), duration=30, session="C", capacity=200),
Slot(venue='Small', starts_at=datetime(2016, 9, 15, 12, 30), duration=30, session="D", capacity=50),
Slot(venue='Small', starts_at=datetime(2016, 9, 15, 13, 0), duration=30, session="D", capacity=50),
Slot(venue='Big', starts_at=datetime(2016, 9, 16, 9, 30), duration=30, session="E", capacity=50),
Slot(venue='Big', starts_at=datetime(2016, 9, 16, 10, 00), duration=30, session="E", capacity=50),
Slot(venue='Big', starts_at=datetime(2016, 9, 16, 12, 30), duration=30, session="F", capacity=50),
Slot(venue='Big', starts_at=datetime(2016, 9, 16, 13, 0), duration=30, session="F", capacity=50)]

workshop_slots = [Slot(venue='Small', starts_at=datetime(2016, 9, 16, 9, 30), duration=60, session="G", capacity=50),
Slot(venue='Small', starts_at=datetime(2016, 9, 16, 13, 0), duration=60, session="H", capacity=50)]
outside_slots = [Slot(venue='Outside', starts_at=datetime(2016, 9, 16, 12, 30), duration=90, session="I", capacity=1000),
Slot(venue='Outside', starts_at=datetime(2016, 9, 16, 13, 0), duration=90, session="J", capacity=1000)]
slots = talk_slots + workshop_slots + outside_slots

events = [Event(name='Talk 1', duration=30, tags=['beginner'], unavailability=outside_slots[:], demand=50),
Event(name='Talk 2', duration=30, tags=['beginner'], unavailability=outside_slots[:], demand=130),
Event(name='Talk 3', duration=30, tags=['beginner'], unavailability=outside_slots[:], demand=200),
Event(name='Talk 4', duration=30, tags=['beginner'], unavailability=outside_slots[:], demand=30),
Event(name='Talk 5', duration=30, tags=['intermediate'], unavailability=outside_slots[:], demand=60),
Event(name='Talk 6', duration=30, tags=['intermediate'], unavailability=outside_slots[:], demand=30),
Event(name='Talk 7', duration=30, tags=['intermediate', 'advanced'], unavailability=outside_slots[:], demand=60),
Event(name='Talk 8', duration=30, tags=['intermediate', 'advanced'], unavailability=outside_slots[:], demand=60),
Event(name='Talk 9', duration=30, tags=['advanced'], unavailability=outside_slots[:], demand=60),
Event(name='Talk 10', duration=30, tags=['advanced'], unavailability=outside_slots[:], demand=30),
Event(name='Talk 11', duration=30, tags=['advanced'], unavailability=outside_slots[:], demand=30),
Event(name='Talk 12', duration=30, tags=['advanced'], unavailability=outside_slots[:], demand=30),
Event(name='Workshop 1', duration=60, tags=['testing'], unavailability=outside_slots[:], demand=40),
Event(name='Workshop 2', duration=60, tags=['testing'], unavailability=outside_slots[:], demand=40),
Event(name='City tour', duration=90, tags=[], unavailability=talk_slots[:] + workshop_slots[:], demand=100),
Event(name='Boardgames', duration=90, tags=[], unavailability=talk_slots[:] + workshop_slots[:], demand=20)]

events[0].add_unavailability(events[6])

events[13].add_unavailability(events[-1])

from conference_scheduler import scheduler
schedule = scheduler.schedule(events, slots)`

This is straight from the code on the tutorial: http://conference-scheduler.readthedocs.io/en/latest/tutorial/index.html#inputting-the-data

Can someone help me with this issue?

Thanks

Write landing page

Write some welcoming content on first page of docs ./docs/index.rst.

Return constraint violations for invalid solutions

When validating an existing solution, for those that fail, it might be helpful to know which constraints were violated and for which event/slot.

This will require the constraint generator functions to produce some form of meaningful label in addition to the constraint itself. The label can then be used to report any constraints which evaluate to False

Bug with pip installed version

>>> from conference_scheduler import scheduler
---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
<ipython-input-120-74aea00c250d> in <module>()
----> 1 import conference_scheduler.lp_problem
      2 from conference_scheduler import scheduler
      3 schedule = scheduler.schedule(events, slots)

ModuleNotFoundError: No module named 'conference_scheduler.lp_problem'

I think this might be because something is not included in the setup.py but I'm not sure. (Works fine using an install from source.)

(Side note: this could also indicate that we should perhaps move to a root/src/conference_scheduler and root/tests directory setup so that we also test an installed version of the library? (Using python setup.py test) I did this for Nashpy after reading about the advantages.)

Equation label placement

Equation labels in the docs are in the wrong place. This appears to be a bug in the rtd theme.

There's a PR to fix that bug at readthedocs/sphinx_rtd_theme#383

Write a how to for the different formats of a solution/array/schedule.

Doing this right now.

Write How To Define a Conference

Write a How-To showing how to define a conference. It should use a variety of methods to hold the necessary data (e.g. YAML/JSON) data.

Pass solver and kwargs to scheduler.array

We are missing the solver and kwargs parameters in the scheduler.array function.

Both the solution and schedule functions have those arguments but, if we want to compute the array form using an external solver, we have to use one of the conversion functions.

Instructions in CONTRIBUTING.rst for running tests have an undocumented YAML dependency

I ran the following steps, based on instructions in CONTRIBUTING.rst:

$ git clone [email protected]:PyconUK/ConferenceScheduler.git
$ cd ConferenceScheduler/

$ python3 -m venv env
$ source env/bin/activate
$ pip install -r requirements.txt

$ vi pytest.ini
$ cat pytest.ini
[pytest]
testpaths = tests docs
python_files =
    test_*.py
    *_test.py
    tests.py
pep8ignore =
    resources.py E701
addopts = --pep8 --doctest-glob='*.rst'

$ python setup.py test
zip_safe flag not set; analyzing archive contents...

Installed /Users/chana/repos/ConferenceScheduler/.eggs/pytest_runner-2.11.1-py3.6.egg
running pytest
running egg_info
creating src/conference_scheduler.egg-info
writing src/conference_scheduler.egg-info/PKG-INFO
writing dependency_links to src/conference_scheduler.egg-info/dependency_links.txt
writing requirements to src/conference_scheduler.egg-info/requires.txt
writing top-level names to src/conference_scheduler.egg-info/top_level.txt
writing manifest file 'src/conference_scheduler.egg-info/SOURCES.txt'
reading manifest file 'src/conference_scheduler.egg-info/SOURCES.txt'
writing manifest file 'src/conference_scheduler.egg-info/SOURCES.txt'
running build_ext
===================================================================== test session starts =====================================================================
platform darwin -- Python 3.6.1, pytest-3.0.7, py-1.4.33, pluggy-0.4.0
rootdir: /Users/chana/repos/ConferenceScheduler, inifile: pytest.ini
plugins: pep8-1.0.6
collected 91 items

tests/conftest.py .
tests/test_resources.py .............
tests/test_scheduler.py ..........................
tests/test_validator.py ..............
tests/lp_problem/test_constraints.py .................
tests/lp_problem/test_objective_functions.py ....
tests/lp_problem/test_utils.py ..........
docs/conf.py .
docs/howto/define_a_conference.rst F
docs/howto/modify_tags_and_unavailability.rst .
docs/howto/obtain_mathematical_representation.rst .
docs/howto/use_different_solver.rst s
docs/tutorial/index.rst .

========================================================================== FAILURES ===========================================================================
______________________________________________________________ [doctest] define_a_conference.rst ______________________________________________________________
186                                                             'plenary',
187                                                             'workshop']}}
188
189 We can load the YAML document containing the 'session times' information in a
190 similar fashion. Again, the data is loaded into a Python dictionary with each
191 event type as a key mapping to a further dictionary with the session name as
192 key and a list of slot times as its values. The start times are converted to an
193 integer representing the number of seconds since midnight::
194
195     >>> import yaml
UNEXPECTED EXCEPTION: ModuleNotFoundError("No module named 'yaml'",)
Traceback (most recent call last):

  File "/usr/local/Cellar/python3/3.6.1/Frameworks/Python.framework/Versions/3.6/lib/python3.6/doctest.py", line 1330, in __run
    compileflags, 1), test.globs)

  File "<doctest define_a_conference.rst[13]>", line 1, in <module>

ModuleNotFoundError: No module named 'yaml'

/Users/chana/repos/ConferenceScheduler/docs/howto/define_a_conference.rst:195: UnexpectedException
======================================================= 1 failed, 89 passed, 1 skipped in 1.96 seconds ========================================================

Write Database How-To

Write a How-To on storing the input data and the resulting schedule in a database.

Validation of schedule

At the moment, we can test that whether a mathematical solution (in the form of a numpy array) is valid, but we need to do so for a list of scheduled events.

This will need some form of translation of that list into an array which can then be tested.

Use autodoc for reference docs

At the moment, the reference docs are built locally (using a monkey patched autodoc function) and the resulting .rst files are placed in the main docs folder.

Once ReadTheDocs is able to support Python 3.6, we should remove that facility and use autodoc directly within the the docs.

readthedocs/readthedocs.org#2584

Write how tos

Write clear and to the point how tos under the assumption that the reader has gone through or is comfortable with the tutorial.

Add a how-to for the setter methods for the event unavailability and tags.

I'll knock something up for this now.

Move to flake8

Once again, inspired by https://blog.ionelmc.ro/2014/05/25/python-packaging/, I suggest we move from pep8 checking to using flake8 as it covers everything that pep8 will pick up plus additional style and code quality checks.

Passing ad-hoc constraints

We need some tests for this to ensure it actually behaves as expected (and to get coverage to 100%)!

Get a diff between two schedules

If I’ve made a change to an existing schedule using #4, it would be useful to be able to see a diff of the changes – e.g., so I can notify any speakers who’ve moved, and attendees can tweak their plans without having to re-read the entire schedule.

I don’t think this has to be provided when you recompute the schedule, but a way to compare two schedules would probably be useful.

Maybe the diff function generates tuples of the form (event, old_slot, new_slot)?

If you assume events stay the same, something like this:

class ChangedScheduledItem(NamedTuple):
    event: Event
    old_slot: Slot
    new_slot: Slot


def diff_schedules(old_schedule, new_schedule):
    old_schedule = sorted(old_schedule, key=lambda item: item.event)
    new_schedule = sorted(new_schedule, key=lambda item: item.event)
    for (event, old_slot), (_, new_slot) in zip(old_schedule, new_schedule):
        if old_slot != new_slot:
            yield ChangedScheduledItem(event, old_slot, new_slot)

Although in practice, I think you'd want some extra logic to cope with events being added or removed, in which case maybe you put None as the old/new slot?

can we use this to schedule meetings?

Hi

Can this library useful to get non overlapping meeting timings if we give busy slots and free slots of the person?
i.e i have group of people their event list from google calendar and their all slots. on give time period. can use this data to get all possible free slots

Code optimisation - use pulp summation?

The constraints and objective functions use python summation to gather the variables.

Apparently this is not efficient and it's better to use pulp.LpAffineExpression.addInPlace as explained here: https://gist.github.com/DRMacIver/4b6561c8e4776597bf7568ccac52742f#file-fullrigger-py-L7

Validation of Existing Schedule

A function to validate an existing schedule against the built-in constraints and, optionally, any constraints passed in as an argument.

Use integers rather than floats in array format

The scheduler.array function and the conversions to array format are producing arrays of floats. We should change this to be integers.

Coverage?

Should we plug coveralls in to this?

Add Remaining built-in constraints

• tags - not scheduling events in the same session unless they share a tag
• duration - only scheduling events in slots with a matching duration
• suitability - not scheduling events in rooms which are unsuitable for that type of event
• unavailability - not scheduling talks when a required person is unavailable or against other events with which it clashes

Documentation

Within the documentation we can include a section on the mathematical model behind it :)

Reference Section

Write the reference documentation - as much as possible based on autodoc from the library docstrings.

Move the tags from a constraint to an objective function.

When used in practice, having even a small number of tags seems to over constrain the solver.

We should move them to an objective function with the goal being to minimise the number of tagged talks that share a session with a non tagged tag.

To be able to combine this with other objective functions we need to be able to added weighted versions of each objective function together to create a new objective function (this gets messy and ends up with users having to choose appropriate weights).

Return the final solution as a list (currently a generator)

Perhaps as a sorted list by the starts_at values?

sorted(schedule, key=lambda item: item.slot.starts_at)

EDIT: My reasoning for this is that it might well take ours for a solution to come back for some set of constraints etc... It feels like things should be a bit more permanent in those cases. (Perhaps I worry too much...)

Add ability to pass specific solvers to solution

pulp is a library that builds an optimisation model that is passed to an external solver, be default it comes packaged with https://projects.coin-or.org/Cbc (I believe).

There are other solvers that can be more efficient. The default behaviour should be kept the same but I suggest we add the ability to pass a variable solver=pulp.GLPK() to scheduler.schedule.

This is not a high priority.

Set defaults for `tags` and `unavailability`

In resources.py set tags=[] and unavailability=[] as defaults. After that we can clear up some of the documentation.