-
Notifications
You must be signed in to change notification settings - Fork 348
MeetingConstraints
This page documents the Automatic Schedule Builder and the constraints for meeting sessions.
The Automatic Schedule Builder creates the most optimal schedule it can find, given the sessions, timeslots and constraints. The constraints define where and how sessions (primarily WGs and BoFs) in meetings should be planned. Different constraints may different priorities, as a conflict-free schedule may not always be possible.
The create_dummy_meeting management command can be helpful for the development of the automatic schedule builder. It creates an IETF 999 meeting based on IETF 106, but with almost all comments translated to proper database constraints. It can be run with the --delete option to delete the dummy meeting. (The attached script-generator.py script was used to generate the initial version.)
The following constraints are part of the business logic of the scheduler, although they will use information from the database, e.g. to determine which sessions are a BoF.
| Constraint | Comment | Weight |
|---|---|---|
| A single room during a single time slot can only have a single session | Absolute requirement | |
| BoFs cannot conflict with any other BoFs | Very strong | |
| BoFs cannot conflict with any other WGs in their area | Very strong | |
| BoFs cannot conflict with PRGs | Very strong | |
| BoFs cannot conflict with any area-wide meetings (of any area) | Strong | |
| Area meetings cannot conflict with anything else in their area | Strong | |
| Area meetings cannot conflict with other area meetings | Medium | |
| WGs overseen by the same Area Director should not conflict | Some ADs also oversee WGs outside of their main area | Weak |
| Sessions should be scheduled in requested order | Strong | |
| Sessions should be scheduled according to requested duration and attendees | Sometimes there is no timeslot available of the requested duration, and the session must be trimmed | Very strong |
An area meeting is any session of any group that has type set to ag, type set to area, or the meeting_seen_as_area flag set.
Per-session constraints are entered by users when requesting their session.
All but the first two have previously been communicated through free-text comments. The possibility of free-text comments will remain, but their usage should be more limited with the support for the constraints listed below.
| Constraint | Name in DB | Comment | Weight |
|---|---|---|---|
| chair conflict | chair_conflict | a chair shouldn't have to be in two different rooms at the same time | Very strong |
| technology overlap | tech_overlap | these groups have enough tech in common that many of the same experts should be able to participate in both of them. | Very strong |
| key participant | key_participant | There is an unnamed key person (or two) that must attend both groups. For example, a presenter known to be needed in each group | Very strong |
| 1st-order conflict | conflict | if these groups conflict, it's not worth either meeting | Very strong |
| 2nd-order conflict | conflic2 | if these groups conflict, it will hurt the quality of each meeting, but it's possible to work around it. | Very strong |
| 3rd-order conflict | conflic3 | it would be better if these groups didn't conflict, but a conflict isn't that damaging. | Very strong |
| Key person | bethere | these explicitly named people need to be present, and musn't be listed as chairs or key persons for other groups at the same time | Very strong |
| Timeslot preference | timerange | WGs may declare mornings and early or late afternoons of each day as "not possible" | Strong |
| Timing between multiple sessions of same WG | time_relation | WGs may declare they want their sessions on consecutive days, or with at least one day in between | Medium |
| Adjacent session with other WG | wg_adjacent | WGs may declare they want their session to be scheduled immediately before/after another WG, same room, no break | Medium |
| Joint meetings | Multiple WGs hosting one session together. | N/A |
Notes:
- For IETF106 through IETF110, the UI was modified to use conflict, conflic2, and conflic3 slugs to represent chair_conflict, key_participant, and tech_overlap constraints, respectively. This was straightened out and the latter slugs were added and used for IETF111. Constraints created using the temporary UI were migrated to use the appropriate slugs.
- key person and key personnel overlap significantly. A future refactor should push towards explicit use of key person and remove the generic key personnel conflict type.
Joint sessions are the most complex case. A session is joint when multiple WGs have one session together, in the same timeslot in the same room. For automatic scheduling, a single Session object in the database should correspond to a single session to be scheduled. There are two types of joint sessions. Joint meetings don't have a weight - they basically consist of merging constraints that have their own weight.
Type A applies when two WGs decide to have one joint session. They do not have any individual sessions. For type A:
- One WG must make the request, listing the constraints of the entire session in their request.
- In the one request, the other WG should be entered as "joint with".
- For the scheduler, no special constraint logic applies: this appears as a single session with a single set of constraints.
Example: the request made by opsawg in IETF 105 and 106: PLEASE NOTE: Combined OpsAWG / OpsAREA (no separate request made for opsarea)
Type B applies when a WG decides to have one session joint with other WGs. The other WGs have sessions of their own. The WG organising the joint session may or may not have their own sessions. For type B:
- The WG organising the joint session makes the request, listing their own constraints in the request.
- In this request, the other WGs should be entered as "joint with", and the requester should specify which of their sessions (if multiple) is a joint session.
- For the scheduler, for the joint session only, all constraints of the request, plus all constraints of all joint WGs (entered in their own requests for their regular sessions) should be considered.
Example: the request made by idr in IETF 106: Please note the 3rd session is for a joint session with security people handling IPSEC tunnels (I2NSF, IPSECME), IDR and BESS. (idr has other sessions too; i2nsf, ipsecme and bess all have a session of their own as well)
The Automatic Schedule Builder (ASB) creates a schedule for a meeting, based on all session requests and timeslots. Note that timeslot refers to the database object meeting.TimeSlot, which consists of a start and end time in a particular room. There are usually multiple timeslots that overlap in time.
The ASB is run with the schedule_generator management command. A meeting parameter must be set to a meeting number. Verbosity is supported, ranging from 0 to 3. Example: $ ietf/manage.py schedule_generator --meeting 999 -v 3
An average run of the ASB takes in the order of 10 minutes, shorter if there if it finds a perfect schedule before that. Each run generates a new schedule, named Auto- followed by a number of random characters. Multiple runs may result in different schedules, because there is some randomness in the algorithm.
The ASB will create a schedule for each Session in the database for the chosen meeting, of type regular, status schedw. If the session does not have a number of attendees set, a warning is emitted and it is assumed any room fits.
These sessions are planned into all TimeSlot objects in the database for the chosen meeting, of type regular, if the room capacity is set (i.e. is not None). Timeslots on a Sunday are ignored.
The purpose of the algorithm is to find the most optimal possible schedule. Evaluating all possible layouts with 140 sessions takes prohibitively long, so the scheduler makes a best effort to find the most optimal possible layout.
"Most optimal" is determined by the schedule cost, which is the cumulative cost of all violated constraints in a schedule. Two costs are calculated internally:
- The fixed cost. This is the cost that is absolutely unavoidable given the information the scheduler has. This mainly applies to session length: if a session requests a length of 2h30m, but the longest timeslot is 2:00, this creates a fixed cost. There is nothing the scheduler could ever do to prevent violating this constraint, and it is pointless to try.
- The dynamic cost. This is the cost of all other constraint violations, that could theoretically be solved by changing the schedule, like a conflict between two sessions, or a !BoF being scheduled during an area meeting. This is the cost the scheduler will try to reduce.
A schedule with a dynamic cost of zero is considered a perfect schedule.
The scheduling happens in a number of steps:
This first step ensures that creating a schedule is actually possible.
First, it verifies that the number of sessions is not greater than the number of timeslots. If it is, the scheduler exits with an error - no schedule can be created.
Second, it compares the capacity and length of each timeslot to the requested capacity and duration, to check whether it is possible to fit all sessions in the given timeslots. If this fit is not possible, the session requests are adjusted and a fixed cost is applied. This is not saved to the database. Example: if two sessions request a length of 2h30m, but there is only one timeslot available with a 2h30m length, one of them is reduced to 2h length for the rest of the process, and this is treated as one constraint violation with a fixed cost.
Initial scheduling means scheduling all sessions, attempting one placement for each session. The process is:
- Sessions are placed in order of complexity, which is calculated as their cumulative cost of affected constraints.
- The least complex sessions are therefore placed last, as they can more easily fill the few remaining timeslots.
- Sessions are placed in the most optimal slot, where optimal means lowest cost first, shortest slot second, smallest room third.
- If multiple slots have the same cost, duration and capacity, a random one is chosen from those slots.
The initial scheduler does not usually generate a perfect schedule, but aims to provide a reasonable starting point for the next step.
The optimiser works with a schedule where all sessions have been placed, and looks for ways to reduce the total cost of the schedule. The process is:
- In each optimiser run:
- For each timeslot, calculate the cost for switching the session with any other timeslot.
- If any of these switches reduces the total cost, make the switch that has the largest cost impact.
- The switch is allowed to create new constraint violations, as long as the total cost is reduced.
- If a run of the optimiser failed to reduce cost by any switch, it means a simple switch can not reduce the cost further. The shuffler is then executed before the next run: all sessions that still have any violations are switched to a random other timeslot. Even if this increases the cost of the schedule. This allows the next runs to be inclined to look for slightly different layouts of the schedule, every time the shuffler is run.
- If at any point the total dynamic cost of the schedule reaches zero, an optimal schedule has been found and the optimiser exits.
- After (currently) 100 runs, the optimiser stops, as it is not likely to find a better schedule. The best schedule the optimiser found after any of its runs is then adopted as the best schedule.
Note that the optimiser only considers the dynamic cost - the fixed cost can not be reduced by the optimiser.
The last step optimises the schedule for room capacity usage.
The optimiser may have left a situation where session A with 50 attendees is scheduled in a 50 person timeslot, and session B with 10 attendees in a 100 person timeslot. The sessions fit, and no cost is applied, but this is not an optimal distribution. The capacity optimisation will switch these sessions.
This step does not change which sessions overlap or when they start and end, so it has no impact on the schedule cost.
Finally, the schedule is saved to the database by creating a new Schedule object along with a number of SchedTimeSessAssignment objects.
Currently processed manually:
- As long as the total amount of time stays the same, unless the groups have expressed a preference otherwise, their session lengths are often swapped. For example, if a group requests two 1.5-hour sessions, they may end up with one 2-hour session and one 1-hour session if that fits in the grid better.
- If a group requests two sessions, it’s more likely that one of them will be on Friday (Friday is generally the least popular day).# Attachments