INET Conferences


Conferences


INET


NDSS

Other Conferences


[INET'98] [ Up ][Prev][Next]

A Meeting Scheduling System for Global Events on the Internet

AHMED Ashir <babu@shiratori.riec.tohoku.ac.jp>
Glenn MANSFIELD<glenn@shiratori.riec.tohoku.ac.jp>
Norio SHIRATORI <norio@shiratori.riec.tohoku.ac.jp>
Tohoku University
Japan

Abstract

The Internet has made remote conferencing a widespread reality. This has added a new and challenging dimension to the problem of scheduling meetings and conferences. The stress on a participant due to the geographical time difference needs to be taken into account while scheduling a meeting.

In this work, a scheduling algorithm for both "open" conferences (which anyone from any part of the globe is free to join) and "closed" conferences (in which the participants are from a closed group) is considered.

The concept of "quorum" is introduced into the scheduling algorithm to make the algorithm more flexible and efficient. To make the system capable of processing multiple meetings concurrently with minimal wastage of timeslots, the bidding method of the traditional contract Net protocol is extended.

A case study has been carried out with actual data from an international conference. It is shown that the proposed algorithm generates schedules that will cause significantly less stress and do so more efficiently and with a higher success rate.

Contents

1. Introduction

The Internet has made remote conferencing a distinct possibility. This has added a new and challenging dimension to the problem of scheduling meetings and conferences on the Internet.

Calendaring and scheduling products are well established for personal or organizational use [Sen97], [Maes], but they usually are limited to exchange of information among users of the same system, usually within the boundaries of a single organization. The scheduling algorithms to date are based on the assumption that all the participants are located in the same time zone. Several problems appear when we breach this boundary, e.g., when we want to schedule meetings in a global scale. Standardization of the calendar, its constituent objects and items, and the related communication protocol is essential. Also, the stress on participants due to the geographical time difference is an important factor that needs to be taken into account while scheduling a meeting.

In a global event, participants may locate in different time zones. People in different parts of the world have different local calendars having different working hours. All participants will naturally prefer a meeting to be scheduled within their working hours. The stress on an attendee due to a meeting is a monotonously increasing function of the deviation. By deviation, we mean the time difference between the proposed meeting hours and normal working hours. The scheduling algorithm needs to take into consideration the implications of the different time-zones and calendars. A time slot from within the working hours of most if not all of the participants is desired. In other words, deviation from working hours needs to be minimized. The same holds for holidays in the respective calendars of potential attendees.

While scheduling a meeting, in general, it is not a necessary requirement that all potential participants do participate. Present scheduling algorithms attempt to find a free time slot for all candidates. This is a constraint that causes many scheduling failures and is avoidable. [Ashir97] The concept of quorum has been introduced to overcome this problem. In this work we have further enhanced the concept of "quorum" by allowing the assignment of different quorum requirements for different groups of participants. This has made the scheduling algorithm more efficient and closer to reality.

A conflict of commitments may appear when multiple meeting requests appear for the same time-slot. This in general narrows the choice of time slots and results in failures in scheduling. And in the worst case scenario time-slots may ultimately remain idle or be wasted despite of the fact that their availability has been denied to one or more schedulers. To avoid this pitfall, in the traditional contract net protocol [ Smith80], we have added an intermediate bid "doubtful" to lessen the wasteful usage of time slots. A slot is in pending state when it has been committed to one meeting but the commitment has not been confirmed. The "doubtful" bid has the effect of wait-listing the schedule and allows time and room for negotiation. This feature does increase the complexity of the scheduling algorithm and related computation but it greatly improves the rate of success.

A case study has been carried out with actual data from an international conference. It is shown that the proposed algorithm generates schedules that will cause significantly less stress, and will do it more efficiently and with a higher success rate.

Outline of paper: In Section 2 , we define the essential objects that will be used in developing the algorithm. In Section 3, we discuss the conventional meeting scheduling approaches and the drawbacks. Our proposal which incorporates three significant improvements for more effective scheduling is presented in Section 4. In Section 5, we show our some results from the proposed algorithm and establish its effectiveness followed by the summary and conclusion in Section 6.

2. Definitions

  • Calendar User: A calendar user interprets objects on a calendar, creates them, and exchanges them with other calendar users. A calendar user may be a person, a group of people, or a resource. From the point of view of other calendar users, groups and resources appear as a single calendar user.
  • Calendar: Calendar users own calendars. A single calendar user may have multiple calendars. However, each calendar must have a unique identifier. A calendar is an information store containing information about events, to-dos, alarms, journals and free time, the objects stored in it. Within the context of a calendar, these objects are called components. Also stored in a calendar are properties that are global to all of the objects in the calendar. An example of a global property is the calscale property that identifies the type of calendar year used by objects in a calendar. Global properties such as this establish the context used to interpret the objects stored in the calendar. When objects or properties of a calendar are exchanged between actors in a calendaring and scheduling network (Calendar User Agents and Calendar Services), they are expressed in the form defined in [iCalendar].
  • Time-Zone: Time-Zone objects encapsulate rules for calculating local time from UTC. Including this object in an event object enables a receiver to calculate the universal time value for time values expressed in the sender's local time. This object is especially useful for expressing the time values of recurring events whose instances span a change in the time reference such as the transition between Standard time and Daylight Savings time. Time values expressed in local time are always interpreted in the receiver's local time. The sender must provide another context using UTC values and Time-zone objects if this is not the interpretation intended by the sender.
  • Calendar-Zones: Keeping in mind the multi-ethnic, multi-cultural and multi-religious constitution of human society and considering the fact that the global span of the Internet has made it possible to have a meeting in a truly global context, it becomes important that the difference in the calendar zones will need to be taken into consideration. Weekends may be holidays in one calendar zone while they may be working days in another.
  • Calendar Object Method: A calendar object method is a set of usage constraints for the calendar object. For example, these methods might define scheduling messages that request an event be scheduled, reply to an event request, send a cancellation notice for an event, modify or replace the definition of an event, provide a counter proposal for an original event request, delegate an event request to another individual, request free or busy time, reply to a free or busy time request, or provide similar scheduling messages for a to-do or journal entry calendar component.
  • Calendar User Agent: A CUA mediates the interaction between a calendar user and his calendar. It represents the information stored in the calendar to the user, and enables the user to manipulate it. This is a particular instance of the interactive process used by a calendar user.
  • Calendar Service: A Calendar Service (CS) stores a collection of calendars and interacts with the Calendar User Agent (CUA) via the Calendar Access Protocol (CAP).

3. Conventional meeting scheduling approach

Basic Problem: In the conventional meeting scheduling approach, the basic goal is to find a common free time slot for prospective participants.

Operational Constraints: The algorithm that will carry out the scheduling has the following operational constraints:

  • the number of negotiations should be as small as possible;
  • the total communication cost among the various entities due to the algorithm should be as small as possible;
  • the algorithm should function without any degradation in a concurrent multi-scheduling environment.

3.1 Drawbacks of the conventional approach

  • Participants are from different time-zones. Participants for global events may be from different parts of the globe. Naturally, they will be having different working hours when looked at in a common time coordinate. It is physically impossible to find a common time slot in the working hours of two of participants residing at the opposite sides of the globe. It is very important to take into account the time difference from normal working hours when drawing up the schedule and in deciding preference.
  • Participants are from different calendar-zones. Participants for global events may be from different parts of the globe. Naturally, they will be having different working hours when looked at on a common time scale.
  • Lack of flexibility. Existing meeting scheduling systems [Sen94] [Omar] attempt to find a common free time slot of all (prospective) participants. When such a free time is slot is not found, the host has to resort to the means of requesting busy participants to change their schedules. Changing a schedule is a complex process requiring a lot of negotiations, and there is no guarantee that the goal will be achieved. In the worst case, the host has to give up on the time slot (which was probably the first choice) and try to schedule the meeting for another time slot (probably a lesser choice). The process will continue till either the scheduling succeeds or there are no more potential time slots. In the latter case, the scheduling would have failed.

    We argue that it is not always necessary for all the prospective participants to attend a meeting. In the real world scenario there are some participants whose presence is mandatory for the meeting. The presence of other participants is optional. The meeting can proceed in the absence of some of the non-mandatory participants. Thus a more flexible and realistic goal for the scheduling algorithm should be to find a common free time slot for the best/largest set of members that satisfies the attendance requirements of that meeting.

  • Concurrent multiple scheduling problems. It is clear that meeting scheduling requests may arrive while previously received meeting scheduling requests are being serviced. The meeting scheduling system should allow multiple meeting scheduling activities to proceed concurrently. The following example shows how a conflict may occur when multiple meeting scheduling processes act concurrently.

    A Host_1 wants to schedule a meeting. Invitee A_1 is one of the prospective attendees. Host_1 proposes four time slots, T_1,T_2,T_3, T_4. Attendee A_1 sends back a "yes ," Fig. 1(a), indicating that all four time slots are free. Out of these four proposed slots, only one slot will be selected. Nevertheless, since attendee A_1 has ensured Host_1 that the four slots are free, all the four slots remain in an undecided state till Host_1 sends a confirmation indicating which slot has been selected. While the scheduling of this meeting is in progress, another host, Host_2, requests A_1 for two time slots, T_1, T_3. As A_1 has already committed these slots, and the slots are in an undecided state, it cannot commit the same slots to Host_2. Thus it rejects the time slots proposed by Host_2, Fig. 1(b). Though the user might have wanted to have the meeting with Host_2, at least one of T_1, T_3 will indeed be free! It is clear that a maximum of (n-1) slots may be wasted out of the n slots proposed during concurrent meetings.


Fig. 1: Concurrent multiple meeting problem and an extended bid

4. System architecture for a global meeting scheduler

Any scheduling algorithm in a global context will be meaningless in the absence of some standard protocols for describing and looking up calendars. The CalSch-WG of the Internet Engineering Task Force (IETF) has been chartered to deal with the related problems and issues. The goal of this group is to create standards that make calendaring and scheduling software significantly more useful and to enable a new class of solutions to be built that are only viable if open standards exist.

4.1 CalSch-WG developments

Three basic problems related to group scheduling are being handled by the CalSch-WG. They are as follows:

  • A standard content type for capturing calendar events, iCalendar
  • A standard peer-to-peer protocol for common calendaring and group scheduling transactions, iCalendar Transport Independent Interoperability Protocol, iTIP
  • A standard access protocol to allow for the management of calendars, Calendar Access Protocol, CAP

The architectural principles of the CalSch-WG model are briefly explained below.


Fig. 2: Simple architecture

A calendar user (CU) views and modifies a calendar using a calendar user agent (CUA). Via a CUA, a CU can modify a calendar by adding or modifying objects stored in the calendar. When a CU creates an object, the CU becomes the owner and organizer for that object. The CU may delegate owner and organizer properties to other CUs by changing the object properties and distributing the object to other CUs. A CUA uses the services of a calendar service (CS) via the calendar access protocol (CAP) to distribute objects from and reconcile changes to the calendar owned by a CU. A CS delivers messages to a CUA containing objects from other calendar users via CAP. A CUA uses the iTIP to deliver objects to a CS to be distributed to other CUAs.

4.2 Our improvements

In view of the ongoing standardization activities at the CalSch-WG, which involve generating standards for communication protocols, access protocols and calendar objects definitions, we have based our proposed architecture on the framework defined in the related Internet-drafts(I-Ds). The components available in the I-Ds are sufficient to meet the requirements of our proposal. All that is needed is an interface for the user to tell the CUA his/her requirements and preferences. The CUA should be intelligent enough to find a time slot that best meets the requirements of the host and the potential participants.

To improve the scheduling efficiency, the following concepts are introduced.

4.2.1 Stress factor

The time deviation (time difference from normal working hours) and/or the resultant stress experienced by an individual is calculated by taking the smallest deviation from working hours, [Fig:3].


Fig. 3: Deviation from working hours

The deviation is computed from the start time or end time of the normal working hours, [whichever is smaller]. Note that it is possible that the deviation from normal working hours may be computed from the start or end of the working hours which may not be on the same day as the meeting. It is clear that if the proposed time is in the working hour, the deviation will be zero. The minimum deviation is taken from the following equation.

The total deviation of all participants is:

4.2.2 Quorum

The goal of introducing this concept is to find out the best set of members for a meeting if the scheduler finds it is impossible to schedule all the participants in a proposed slot.


Fig. 4: Quorum

The initial set of attendees, Fig. 4(a), is grouped into some sub-groups according to their importance and/or relevance to the meeting. Invitees of similar standing will be in the same sub-group, Fig:4(b). A quorum requirement is defined for all the subgroups. Where unspecified, the default is 100%. The quorum condition represents the minimum number of attendees without whom the meeting cannot be held, Fig: 4(c).

4.2.3 Extended bid

The system should allow multiple number meeting schedulers to function concurrently. It is obvious that meetings might arrive while earlier requests are being processed. A calendar time-slot is in pending state when the state has been committed to a host for a meeting (probably with a few more potential time-slots), and no confirmation has been received from the host. With respect to such pending states, the agent can respond with an intermediate Doubtful bid, Fig. 1(d), which is neither Accept nor Refuse but has the effect of wait-listing the schedule and allows time and room for negotiation. Also, while a schedule is being processed by the host agent, attendees are informed of unsatisfactory schedules as and when those are found. This reduces the number of time slots in pending state.

This Doubtful bid allows the system to respond with three types of bids.

Responses (bids)
Accept Definitely Accept Slot is free and acceptable
Refuse Definitely Refuse Slot is Busy or Unacceptable
Doubtful Preferably don't Accept Probably not free or preferably avoid

The scheduling algorithm

The following example explains how the scheduling is carried out.

  1. The CU sends a schedule_request to the CUA.
  2. The CUA converts the schedule_request to iCal standard components (CalSch Reference) and announces the meeting to all the prospective attendees.
  3. An attendee on the other hand receives the contract proposal, and tries to find local solutions by searching acceptable slots in their calendar and sending them back as bids to the CUA organizer.
  4. The CUA evaluates the bids. The unsatisfactory slots are released. Thus pending slots change their states and become empty.
  5. The CUA ranks the remaining considerable slots according to the preference. If a suitable slot is not found, it starts negotiating with the potential attendees in the first group in that slot who have responded with a "doubtful" bid. If the negotiation fails to satisfy the quorum condition, it releases this slot and goes to the next slot. If the negotiation succeeds with the first group, the scheduling proceeds with the members in the next group.
  6. If several satisfactory slots are found, the CUA selects the best slot and requests to mark this meeting on the potential attendees' calendars.

The above steps are repeated until a satisfactory schedule is arrived at, or it is recognized that the meeting cannot be scheduled (due to an overly crowded schedule or due to the fact that the meeting could not be scheduled before its deadline).

5. Implementation and evaluation

The system was implemented in a platform independent language (Java) and is accessible by any Java-enabled browser. We presume that users will be having light clients and their local calendars. For scheduling purposes, the services of corresponding applets will be availed of from applet servers in well known locations.

5.1 Implementation

For implementing the scheduling algorithm of [Section 4 ] we use the protocol elements -- Announce, Bid, Release, Award. It may be noted that the Release protocol element is an addition to the usual contract net protocol. The mapping of these protocol elements to the CalSch definitions are as follows.

Announce: The host as an organizer asks attendees for their freebusy slots with dtstart (July 22, 1998, 9 a.m.) and dtend (July 22, 1998, 5 p.m.) UTC time value for a meeting of one hour duration.

BEGIN:VFREEBUSY
ATTENDEE;ROLE=ORGANIZER:MAILTO:host@domain1
ATTENDEE;EXPECT=REQUEST;ROLE=ATTENDEE:MAILTO:attendee@domain2
LOCATION;VALUE=URI:http://www.isoc.org/inet98.vcf
CATEGORIES:MEETING
DTSTART:19980722T090000Z
DTEND:19980722T170000Z
DTSTAMP:19971028T083000Z
UID:19971028T083000-uid1@domain1
END:VFREEBUSY

Bid: An attendee replies to the organizer's request with its free slots (2 hrs. from 10:00, 1 hr. from 16:00). After bidding, the states of these two slots become pending in attendee's calendar.

BEGIN:VFREEBUSY
ATTENDEE;ROLE=ATTENDEE:MAILTO:attendee@domain
CATEGORIES:MEETING
FREEBUSY;VALUE=PERIOD:19980722T100000Z/PT2H 19980722T160000Z/PT1H
UID:19971028T083000-uid1@domain1
END:VFREEBUSY

Release: The organizer decides the final slot and releases the remaining slots.

Award: The final slot is awarded to the attendee to mark this meeting on its calendar.

BEGIN:VEVENT
ATTENDEE;ROLE=ATTENDEE:MAILTO:attendee@domain
CATEGORIES:MEETING
STATUS=ACCEPTED; VALUE=PERIOD;19980722T100000Z/PT1H
UID:19971028T083000-uid1@domain1
END:VEVENT

5.2 Evaluation

5.2.1 Case study for evaluating the stress

As a case study we have taken the data of an international conference [IJCAI]which was hosted in Nagoya, Japan. We use this data and examine the hypothetical case where the conference was held globally. It is clear that in such cases the convenience of all the participants need to be considered. However, due to practical limitations, we confined ourselves to the task of finding a convenient schedule for all the presenters. Below is the country of origin list of presenters (NP is the number of presenters).

Fig 5: Experimental Result
Country NP Country NP
Japan 11 Germany 2
Australia 2 China 2
UK 2 Sweden 1
USA 11 Rumania 1
France 6 Holland 1
Italy 4 Ireland 3
Brazil 1 Canada 3

We have confined ourselves to finding suitable slots for the first 50 presenters (first author of the paper). And we have assumed that the presenter will make the presentation from his/her country as shown in the affiliation. The presenters were from 14 different countries, 10 different time-zones (a country like the United States has several time-zones, some countries have the same time-zone). The result, Fig. 5, shows that eight o'clock (at UTC Time) in the morning is the best (globally least stressful) slot for the presenters. This slot is in the working hours of Japan, China, France, Italy, Rumania, etc., from where the major portion of the presenters joined.

5.2.2 Flexibility of quorum and the success rate

In this experiment, we have chosen 50 participants having a calendar of 24 timeslots. The calendar states (busy, pending, empty) have been inserted randomly. The participants have been grouped into three different groups [(2+6+42)= 50], according to their importance to the meeting. The results below show the different quorum conditions and the respective success rates in scheduling a meeting under the given requirements.

Quorum Setup
Group Case 1 Case 2 Case 3 Case 4 Case 5 Case 6
G1 2 2 2 2 2 2
G2 6 4 4 3 3 2
G3 42 35 30 30 25 25

Conclusion

We have proposed a scheduling system that takes into consideration the special requirements of global events. The highlights of the system are that it minimizes the stress on participants due to geographical time difference, considers different calendar-zones, uses the concept of quorum to make the scheduling more flexible and introduces the "doubtful" bid mechanism to improve the efficiency of the scheduling algorithm.

A prototype system is being developed in Java based on the architecture and protocols that are being discussed at the IETF-CalSch-Wag. Case studies have been carried out using real data from international conferences. The results establish the efficacy of the proposed scheduling algorithm.

References

  1. Ahmed Ashore et al., "Multi-Agent Based Decision Mechanism for Distributed Meeting Scheduling System," International Conference on Parallel and Distributed Systems , ICPADS'97, Seoul, Korea. http://www.shiratori.riec.tohoku.ac.jp/~babu/icpads.ps
  2. Sandip Sen and Edmund H. Durfee, "A Contracting Model for Flexible Distributed Scheduling," Annals of Operations Research, volume 65, pages 195-222, 1996. http://euler.mcs.utulsa.edu/~sandip/aor.ps
  3. Omar Belakhdar "Meeting Scheduling: An Application for Protocols Driven Cooperation," The first international Conference and Exhibition on "The Practical Application of Intelligent Agents and Multi-Agent Technology" '96
  4. Sandip Sen, Thomas Haynes, and Neeraj Arora, "Satisfying User Preferences While Negotiating Meetings," http://ksi.cpsc.ucalgary.ca:80/IJHCS/
  5. Reid G. Smith, "The Contract Net Protocol: High-level Communication and Control in a Distributed Problem Solver." IEEE Transitions on Computers, C-29(12):1104-1113, December 1980
  6. IETF CALSCH Working Group, "Internet Drafts: Calendaring and Scheduling," draft-ietf-calsch
  7. IJCAI'97 15th International Joint Conference on Artificial Intelligence, Nagoya, Japan, August 23-29, 1997
  8. Kozierok R. and Maes P., 1992A, Learning Interface for Scheduling Meetings, ACM SIGCHI International Workshop on Intelligent User Interface, ACM, Orlando, Florida, January 1993

[INET'98] [ Up ][Prev][Next]