Proposed by Uri Shapen, Roie Zivan, Amnon Meisels

Meeting scheduling is a well-known, recurrent and easily described problem. The meeting scheduling problem (MSP) will be described below as a centralistic constraints satisfaction problem (CSP).

However, one of its most interesting features is the fact that it is a Distributed CSP. Informally, a set of agents want to meet and they search for a feasible meeting time that satisfies the private constraints of each of the agents and in addition satisfies arrival-time constraints (among different meetings of the same agent).

The general definition of the MSP family is as follows:

The table below presents an example of a MSP, including the traveling time in time-units (say, hours) between different meeting locations.

Meeting Location Attending agents
$m_1$ $L_1$ $A_1, A_3$
$m_2$ $L_2$ $A_2, A_3, A_4$
$m_3$ $L_3$ $A_1, A_4$
$m_4$ $L_4$ $A_1, A_2$

The distances (in time-slots) between the meetings are described by the following:

The meeting scheduling problem as described above can be naturally represented as a constraints satisfaction problem (CSP) in the following way:

The arrival-time constraint - given two time-slots $t_i, t_j$ there is a conflict if

$$|\rm{time}(t_i)-\rm{time}(t_j)|- \rm{duration}_i < \rm{TravellingTime}(\rm{location}(m_i), \rm{location}(m_i))$$

Simplifying assumptions:

The Density of the CSP network depends on the number of meetings ($m$), the number of agents ($n$) and the number of meetings per agent ($k$). The Tightness of a constraint depends on the domain size of the meetings and the locations of the two constrained meetings. The Density and Tightness can be calculated in the following way:

Density $(p_1)$ - the ratio of the total number of edges to the maximal number of possible edges.

$$p_1 = \rm{edges in the network}/(m*(m - 1)/2)$$

Tightness $(p_2)$ - the ratio between the total number of eliminated time slots to the number of total tuples ($D^2$). Therefore $p_2$ is defined as

$$p_2 = (D*(2*s + 1) - s^2)/(D*D)$$

where $s$ is the travelling time between the meeting locations.

A Representation of a Meeting Scheduling Problem as CSP is described in Figure 2:

The meeting scheduling problem is naturally described as a Distributed CSP. The representation of the MSP as DisCSP is based on the distributed nature of the problem. The MSP is a distributed negotiation problem between different users. Therefore, the agents are associated with the users and not with the meetings. The meetings are the variables that must be assigned time slots and they are duplicated within all agents that attend the same meeting.

The MSP can be represented as DisCSP in the following way:

A Representation of a Meeting Scheduling Problem as DisCSP is described in Figure 3.

Random Meeting Scheduling Problem (RMSP) specification:

The RMSP can be parameterized in many ways. Parameters can be the number of meetings, locations, number of agents, etc.

Let us first denote the set of all parameters:

The meetings are the set of $m$ variables of the constraints network, each representing a meeting at a specific location. The domains of values are the time-slots $l$. An edge between any pair of variables represents an agent that participates in both meetings. The density of the constraints network is a function of the number of edges in the network. The number of edges in the network depends on the number of agents and the distribution of meetings that each agent attends.

If each agent participates in $k$ meetings, we generate the resulting CSP as follows:

For each of the $n$ agents a clique of $k$ variables (meetings) is selected randomly, such that not all of the edges of the clique are already in the network. All the edges of the generated clique are added to the CSP network, representing the arrival-time constraints between the meetings of each agent. The arrival-time between each two meetings is also randomly generated. Note, that an agent $A_i$ adds an arrival-constraint between meetings $m_j, m_k$ only if there is no other agent that attends both meetings. Two agents or more that participate in $m_j, m_k$ define only one arrival-constraint. The distance between locations of meetings randomly generated according to the given range (between the minimal meeting distance and the maximal one).

Below is an example of a randomly generated Meeting Scheduling Problem:

Meetings are $m_1, m_2, m_3, m_4, m_5$

Agents are $a_1, a_2, a_3$

Agents’ Meetings:

Agent (0): $m_1, m_3, m_5$
Agent (1): $m_1, m_2, m_3$
Agent (2): $m_2, m_3, m_4$

Distances between Meeting Locations:

1 2 3 4 5
1: 0 1 2 1 3
2: 1 0 3 2 2
3: 2 3 0 1 2
4: 1 2 1 0 3
5: 3 2 2 3 0