Abstract:

The use of Information and Communication Technologies (ICT) at various levels of education (primary, secondary, higher) has significantly contributed to both extending the scope and improving the quality of services provided. Usually, the use of ICT in education is associated with the educational process and, in particular, with the support of teaching, learning and training activities. However, ICT can also be exploited to support processes related to the management of the available human and financial resources and infrastructures.

Educational visits are part of the educational process at almost all levels of education. Visits are usually arranged to places of cultural, scientific and technological interest. The choice of the place of visit is usually made on the basis of criteria such as distance, costs involved, availability, suitability in terms of the number of visitors, the intended learning outcome, etc. These criteria are evaluated differently by each educational unit. In addition, the entities managing the points of interest (e.g., museums, exhibitios, galleries, institutes, etc.) select which groups to accept for a visit based on criteria such as population of visiting groups, visibility improvement, revenue, etc. These criteria are also evaluated differently by each institution managing points of interest. Ideally, the aim would be to schedule educational visits so as to maximize the satisfaction of both the educational units and the institutions managing points of interest.

In terms of Graph Theory, marriage is expressed as a matching problem in graphs where edges represent compatibility, i.e., two vertices connected by an edge can be matched or "married". A matching in a given graph is a subgraph of this graph in which every vertex has degree 1. When all vertices of the graph are invloved in the matching, the matching is called perfect matching. The goal of matching problems is to generate the maximum number of matching pairs. The Stable Marriage Problem (SMP) is a special matching problem. In its basic version, we are given N boys and N girls, boys can only be paired to girls and vice versa, each boy (respectively girl) has his own ranked preference list of all the girls (respectively boys). Lists are complete and there are no ties. Preferences are not necessarily symmetric and cannot change over time. The goal is to find a perfect matching that is stable. A matching is stable when it does not contain pairs whose members prefer each other to their mates in the matching. The Stable Marriage Problem has been extensively studied in the literature, mainly due to its remarkable variations and its wide application in several areas for assignment and resource allocation, load balancing, cryptography and data security even for finding compatible kidney donors. The algorithm suggested by Gale and Shapley brought about significant changes especially in the fields of Economics, Health and Computer Science.

In this work, we propose a web-based system for scheduling educational visits. In particular, we state the problem of scheduling educational visits as an instance of the Stable Marriage Problem. Then, we use the algorithm suggested by Gale and Shapley for computing stable matchings. These matchings indicate schedules for educational visit which serve in the best possible way the inerests and objectives of both the educational units and the institutions managing points of interest.

Keywords:

Educational visits, scheduling, stable matchings, algorithm by Gale and Shapley, web-based application, wordpress.