A Meeting Scheduling System for Global Events on the Internet
AHMED Ashir <firstname.lastname@example.org>
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.
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.
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:
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.
Three basic problems related to group scheduling are being handled by the CalSch-WG. They are as follows:
The architectural principles of the CalSch-WG model are briefly explained below.
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.
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.
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].
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:
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.
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).
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.
The following example explains how the scheduling is carried out.
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).
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.
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.
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.
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.
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).
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.
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.
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.